|
![[photo of a speaker] (c) D.Nagaj](img/photos/speaker.jpg)
other seminars:
|
|
|
|
2012 - 2013 (academic year) |
|
:: Fri 10/19/12, in Vladan Vuletic (MIT)
Entanglement and atomic clocks below the standard quantum limit
:: Fri 10/26/12, 2:00 PM in 6C-442 Daniel Gottesman (Perimeter)
General Principles of Fault-Tolerant Quantum Computation
:: Fri 11/9/12, 2:00 PM in 6C-442 Mario Szegedy (Rutgers)
Symmetric Garden Hose Constructions
The Garden Hose complexity is a new communication complexity introduced by H. Buhrman, S. Fehr, C. Schaffner and F. Speelman to analyze position-based cryptography protocols in the quantum setting. We focus on the garden hose complexity of the equality function, and improve on the bounds of Buhrman at all. With the help of of a new approach and of our handmade simulated annealing based solver, we have out-performed the commercial set solvers used by Buhrman at all. We have also found beautiful symmetries of the solutions that have lead us to develop the notion of "garden hose permutation groups." Then, exploiting this new concept, we get even farther, although several interesting open problems remain. In our talk we explain the background, our algorithmic efforts, and give a pictorial presentation of the symmetries.
:: Fri 11/16/12, 2:00 PM in 6C-442 Graeme Smith (IBM Research)
Nailing Down the Capacity of Bosonic Channels
:: Fri 11/30/12, 2:00 PM in 6C-442 Richard Cleve (Waterloo)
Characterization of binary system game
I define a class of non-local games (in other words, Bell inequality frameworks) that naturally generalizes Mermin's so-called "magic square" game, and then consider the problem of determining the entangled value of such a game.
:: Fri 12/7/12, 2:00 PM in 6C-442 Keye Martin (Naval Research Laboratory)
Algebraic Information Theory
:: Fri 2/22/13, 2:00 PM in 6C-442 Gil Kalai (Hebrew University of Jerusalem and Yale University)
Why quantum computers cannot work, and how
Quantum computers are hypothetical devices based on quantum physics that can out-perform classical computers. A famous algorithm by Peter Shor shows that quantum computers can factor an integer n in C(log n)^3 steps. The question if quantum computer are realistic is one of the most fascinating and clear-cut scientific problems of our time, and my work is geared toward a negative answer. The main concern from the start was that quantum systems are inherently noisy; we cannot accurately control them, and we cannot accurately describe them. To overcome this difficulty, a fascinating notion of quantum error-correction and a remarkable theory of quantum fault-tolerance were developed.
What makes it still hard to believe that superior quantum computers can be built is that building universal quantum computers represents a completely new reality in terms of controlled and observed quantum evolutions, and also a new computational complexity reality. What makes it hard to believe that quantum computers cannot be built is that this may require profoundly new insights in the understanding quantum mechanical systems (including in regimes where people do not expect such new insights.)
Here is my explanation for why (fault-tolerant) quantum computers cannot be built: Quantum systems based on special-purpose quantum devices are subject to noise which systematically depends on the quantum evolution of the system; this dependence reflects dependence of the noise on the quantum device, and the dependence of the quantum device on the quantum evolution it is performing. (Here, " a quantum device" refers both to human-made and to natural devices.) This systematic dependence causes general-purpose quantum computers to fail. The challenge is to understand the systematic laws for this dependence. (Of course, within the framework of quantum probability.)
In the lecture I will start with an argument for why implementations of topological quantum computing leading to highly stable qubits that "shortcuts" the need for traditional quantum fault-tolerance cannot work. I will continue to describe the distinctions between noisy quantum systems that enact quantum fault tolerance and those that do not, and concentrate on two formal distinctions. To this end I will describe my model of "smoothed Lindblad evolutions." I will also mention some highlights in a recent debate with Aram Harrow on the matter.
:: Fri 4/26/13, 2:00 PM in 6C-442 Toby Cubitt (University of Cambridge)
Undecidability of the spectral gap question
The spectral gap of a quantum many-body Hamiltonian -- the difference between the ground state energy (lowest eigenvalue) and lowest excited state (next-lowest eigenvalue, ignoring degeneracies) in the thermodynamic limit (limit of arbitrarily large system size) -- plays an important role in determining the physical properties of a many-body system. In particular, it determines the phase diagram of the system, with quantum phase transitions occurring at critical points where the spectral gap vanishes.
A number of famous open problems in mathematical physics concern whether or not particular many-body models are gapped. For example, the "Haldane conjecture" states that Heisenberg spin chains are gapped for integer spin, and gapless for half-integer spin. The seminal result by Lieb-Schultz-Mattis proves the half-integer case. But, whilst there exists strong numerical evidence, the integer case remains unproven. In 2-dimensions, there is a longstanding conjecture that the 2D AKLT model is gapped. In the related setting of quantum field theories, determining if Yang-Mills theory is gapped is one of the Millennium Prize Problems, with a $1 million prize attached.
I will show that the general spectral gap problem is unsolvable. Specifically, there exist translationally-invariant Hamiltonians on a 2D square lattice of finite-dimensional spins, with two-body nearest-neighbour interactions, for which the spectral gap problem is undecidable. This means that there exist gapless Hamiltonians for which the absence of a gap cannot be proven in any consistent framework of mathematics.
The proof is (of course!) by reduction from the Halting Problem. But the argument is quite complex, and draws on a wide variety of techniques, ranging from quantum algorithms and quantum computing, to classical tiling problems, to recent Hamiltonian complexity results, to an even more recent construction of gapless PEPS parent Hamiltonians. I will explain the result, sketch the techniques involved in the proof, and discuss what implications this might have for physics.
Based on ongoing work with David Perez-Garcia and Michael Wolf.
:: Wed 5/8/13, 4:30 PM in 6C-442 Matthias Troyer (ETH Zurich, Institute for Theoretical Physics)
Experiments on the D-WAVE devices: quantum annealing on more than 500 qubits?
:: Fri 5/10/13, 2:00 PM in 6C-442 Thomas Vidick (MIT)
Fully device-independent quantum key distribution
The laws of quantum mechanics allow unconditionally secure key distribution protocols. Nevertheless, security proofs of traditional quantum key distribution (QKD) protocols rely on a crucial assumption, the trustworthiness of the quantum devices used in the protocol. In device-independent QKD, even this last assumption is relaxed: the devices used in the protocol may have been adversarially prepared, and there is no a priori guarantee that they perform according to specification. Proving security in this setting had been a central open problem in quantum cryptography.
We give the first device-independent proof of security of a protocol for quantum key distribution that guarantees the extraction of a linear amount of key even when the devices are subject to a constant rate of noise.The only assumptions required are that the laboratories in which each party holds his or her own device are spatially isolated, and that both devices as well as the eavesdropper, are bound by the laws of quantum mechanics. At the heart of the security proof lie novel tools for the manipulation of a fundamental limitation of quantum entanglement, its monogamy. I will present the intuition relating monogamy and security and give an overview of our security proof.
Based on joint work with U. Vazirani
|
