QIS Quantum Information Science MIT

2008 - 2009 (academic year)




:: Wed 9/3/08, 3:00 pm in Mallinckrodt M213 (12 Oxford st, across from science center) (special seminar)

Alexandra Olaya-Castro
Energy Transfer in a photosynthetic core complex: Exploiting quantum coherence and static disorder

Photosynthetic structures are finely tuned to capture solar light efficiently and transfer it to molecular reaction centres for conversion into chemical energy with 950r more efficiency. How photosynthetic structures achieve such a high-efficiency is still a long-standing question in science. Fundamental breakthroughs towards answering this question have recently been achieved. In particular, direct evidence of long-lasting electronic coherence during excitation transfer in photosynthetic complexes has been obtained. In this talk I will discuss our recent work on the energy transfer efficiency in a photosynthetic core where a light harvesting antenna is connected to a reaction centre as in purple bacteria. By using a quantum jump approach, we demonstrate that in the presence of quantum coherent energy transfer and energetic disorder, the transfer efficiency from the antenna to the reaction centre depends intimately on the quantum superposition properties of the initial state. This indicates that initial state properties could be used as an efficiency control parameter. Our results open up experimental possibilities to investigate and exploit such coherent phenomena in artificial and natural systems capable of harvesting light.

:: Thu 9/4/08, 3:00 pm in 24-307 (special seminar)

Paola Cappellaro (Harvard)
Coherent Control of Quantum Information Devices

The development of new technologies at scales approaching the quantum regime is driving new theoretical and experimental research on control in quantum systems. The implementation of quantum control would have an enormous impact on a wide range of fields, in particular in quantum information processing and precision metrology. In this talk Dr. Cappellaro will present the application of coherent control techniques to the electronic and nuclear spins associated with Nitrogen-Vacancy (NV) centers in diamond. These systems have emerged as excellent candidates for quantum information processing, since they can be optically polarized and detected, and present good coherence properties even at room temperature. She will first show how this solid state system can be used as the building block of a scalable architecture for quantum computation or communication,then present a novel approach to magnetometry, based on NV centers, that takes advantage of coherent control techniques and the confinement of the sensing spins into a sample of nanometer dimensions. The resulting magnetic sensor is projected to yield an unprecedented combination of ultra-high sensitivity and spatial resolution, with the potential of exciting applications in bioscience, materials science, and single electronic and nuclear spin detection.

:: Mon 9/8/08, 4:15 pm in 36-428 (QIP seminar)

Sergey Bravyi (IBM)
Additive quantum codes with geometrically local generators
(Link To Video)

We study properties of additive quantum error-correcting codes (QECC) that permit a local description on a regular D-dimensional lattice. Specifically, we assume that the stabilizer group of a code has a set of local generators such that support of any generator can be bounded by a rectangular box of size $r=O(1)$. Our first result concerns the optimal scaling of the distance $d$ with the linear size of the lattice $L$. We establish an upper bound $dle r L^{D-1}$ which is tight for $D=1,2$. We also prove a bound $d=O(1)$ for one-dimensional subsystem codes assuming that the gauge group of a code has a set of local generators. Secondly we analyze suitability of various QECCs for building a self-correcting quantum memory. Any additive QECC with geometrically local generators can be naturally converted to a local Hamiltonian that penalizes states violating the stabilizer conditions. A degenerate ground state of this Hamiltonian corresponds to the logical subspace of a code. We prove that for $D=1,2$ the height of an energy barrier separating different logical states is upper bounded by a constant independent of the lattice size $L$. This result demonstrates that a self-correcting quantum memory cannot be build using additive QECC in dimensions $D=1,2$.

:: Mon 10/6/08, 4:15 pm in 36-428 (QIP seminar)

Hassidim,Avinatan (MIT)
Quantum Multi Prover Interactive Proofs with Communicating Provers
(Link To Video)

Quantum Multi Prover Interactive Proofs (QMIP) can provide us with important insights to the capabilities of entanglement. The talk will present some known models and insights they give. We introduce a variant of the model, where the provers do not share entanglement, the communication between the verifier and the provers is quantum, but the provers are unlimited in the classical communication between them. At first, this model may seem very weak, as provers who exchange information seem to be equivalent in power to a simple prover. This in fact is not the case - we show that any language in NEXP can be recognized in this model efficiently, with just two provers and two rounds of communication, with a constant completeness-soundness gap. The main idea is not to bound the information the provers exchange with each other, as in the classical case, but rather to prove that any ``cheating'' strategy employed by the provers has constant probability to diminish the entanglement between the verifier and the provers by a constant amount. Detecting such reduction gives us the soundness proof. Similar ideas and techniques may help help with other models of Quantum MIP, including the dual question, of non communicating provers with unlimited entanglement.

:: Mon 10/20/08, 4:15 in 36-428 (QIP seminar)

Kenneth Brown (Georgia Institute of Technology)
Quantum Simulations and Errors
(Link To Video)

A quantum simulation is a map of the dynamics of a target quantum system onto a control quantum system. A quantum computer is a control quantum system that can simulate any target quantum system. In this talk, we describe two cases of quantum simulations in the presence of errors. In the first case, we examine a control quantum system that simulates the target system in an interaction picture. Although the control system simulates the dynamics, it does not simulate the thermodynamics of the target system. This is an important distinction when the target system represents a Hamiltonian with proposed error-correcting properties. In the second case, we use a model of a fault-tolerant quantum architecture to evaluate the resource cost of evaluating the ground state energy of the target quantum system. The resources are compared to performing Shor's algorithm on the same model. Simulations of modest accuracy on 10's of qubits are found to have comparable cost, in the product of computational time and space (KQ), to the factoring of 1024 bit numbers.

:: Wed 10/22/08, 3:00 in 36-428 (special seminar)

William Oliver (MIT Lincoln Laboratory)
Quantum Computation with Superconducting Artificial Atoms
(Link To Video)

In this talk, we will present an overview of our superconductive quantum computing effort. In collaboration with Lincoln�s Solid State Division (Division 8) and the MIT campus, we have fabricated superconductive artificial atoms, actively cooled them to near absolute zero, and demonstrated new broadband spectroscopy techniques along with the more conventional Rabi, Ramsey, and spin-echo metrics to characterize their coherence. These artificial atoms form the fundamental building blocks, �qubits,� of a quantum information processor. We have developed and simulated a universal set of gate operations capable of low error rates to control these qubits. Today, we are working to improve single-qubit coherence while coupling these qubits into more complicated circuit elements. The talk will present a review of our progress and future work.

:: Mon 11/17/08, 4:15 in 36-428 (QIP seminar)

Aliferis,Panos (IBM)
Fault-tolerant quantum computing against highly biased noise
(Link To Video)

Experimentalists in quantum computing observe that in many of their systems noise is biased---i.e., loss of phase coherence in the computational basis occurs faster than relaxation to the lowest energy eigenstate or leakage outside the computational subspace. I will discuss a scheme for fault-tolerant quantum computation that is especially designed to protect against biased noise. The scheme is particularly effective when the noise bias is very high, with dephasing dominating other types of noise by three orders of magnitude or more. To illustrate how this scheme could be relevant for future experiments, I will discuss the design of a universal set of biased-noise operations for the superconducting flux qubit investigated at the IBM labs.

:: Mon 11/24/08, 4:15 in 36-428 (QIP seminar)

Verstraete,Frank
The complexity of simulating quantum many-body systems
(Link To Video)

The theory of entanglement and of quantum computational complexity is providing valuable new insights into the problem of simulating strongly correlated quantum many-body systems. We will discuss recent progress in that field.

:: Mon 12/1/08, 4:15 in 36-428 (QIP seminar)

Wootters,William (Williams College)
The Entanglement Cost of a Nonlocal Measurement
(Link To Video)

For a joint measurement on a pair of spatially separated quantum objects, one can ask how much entanglement is needed to carry out the measurement using only local operations and classical communication. In this talk I focus on a particular orthogonal measurement on two qubits with partially entangled eigenstates, for which we can find upper and lower bounds on the entanglement cost. The lower bound implies that the entanglement required to perform the measurement is strictly greater than the average entanglement of the eigenstates. I also consider other examples, including a simple two-qubit product- state measurement that cannot be performed locally.

:: Mon 12/8/08, 4:15 in 36-428 (QIP seminar)

Zeng,Bei (MIT)
Quantum Error Correction via Codes Over GF(3)
(Link To Video)

``Quantum Error Correction via Codes Over GF(4)" is one of the seminal papers in quantum coding theory. This 1996 work transforms the problem of finding binary quantum-error-correcting codes into the problem of finding additive codes over the field GF(4) which are self-orthogonal with respect to a certain trace inner product. Ever since then, these codes, called additive codes or stabilizer codes, have dominated the research on quantum coding theory. There is now a rich theory of stabilizer codes, and a thorough understanding of their properties. Nevertheless, there are a few known examples of nonadditive codes which outperform any possible stabilzer code. In previous work, my colleagues and I introduced the codeword stabilized quantum codes framework for understanding additive and nonadditive codes. This has allowed us to find, using exhaustive or random search, good new nonadditive codes. However, these new codes have no obvious structure to generalize to other cases. A systematical understanding of constructing nonadditive quantum codes is still lacking. In this talk, we introduce the idea of constructing binary quantum- error-correcting codes via classical codes over the field GF(3). Quantum codes directly constructed this way are nonadditive codes adapted to the amplitude damping channel. These codes have higher performance than all the previous codes for the amplitude damping channel. We then further generalize this GF(3) idea to the case of constructing 'usual' binary quantum codes for the depolarizing channel, which leads to a systematical way of constructing good nonadditive codes that outperform best additive codes. Using this method, many good new codes are found. Particularly, we construct families of good nonadditive codes which not only ourperform any additive codes, but also asymptotically achieve the quantum Hamming bound. Generalization to nonbinary case is straightforward and families of good nonadditive nonbinary quantum codes are found. What is more, our new method can also be used to construct additive codes, and additive codes with better parameters than previous known are found. Based on joint work with Markus Grassl, Peter Shor, Graeme Smith, and John Smolin.

:: Thu 1/8/09, 4:15 in 36-428 (QIP seminar)

Eban,Elad (Hebrew University)
Interactive Proofs for Quantum Computation

The widely held belief that BQP strictly contains BPP raises fundamental questions: Upcoming generations of quantum computers might already be too large to be simulated classically. Is it possible to experimentally test that these systems perform as they should, if we cannot efficiently compute predictions for their behavior? Vazirani has asked [Vaz07]: If computing predictions for Quantum Mechanics requires exponential resources, is Quantum Mechanics a falsifiable theory? In cryptographic settings, an untrusted future company wants to sell a quantum computer or perform a delegated quantum computation. Can the customer be convinced of correctness without the ability to compare results to predictions? To provide answers to these questions, we define Quantum Prover Interactive Proofs (QPIP).Whereas in standard Interactive Proofs [GMR85] the prover is computationally unbounded, here our prover is in BQP, representing a quantum computer. The verifier models our current computational capabilities: it is a BPP machine, with access to few qubits. Our main theorem can be roughly stated as: "Any language in BQP has a QPIP, and moreover, a fault tolerant one". We provide two proofs. The simpler one uses a new (possibly of independent interest) quantum authentication scheme (QAS) based on random Clifford elements. This QPIP however, is not fault tolerant. Our second protocol uses polynomial codes QAS due to Ben-Or, CrŽepeau, Gottesman, Hassidim, and Smith [BOCG+06],combined with quantum fault tolerance and secure multiparty quantum computation techniques. A slight modification of our constructions makes the protocol "blind": the quantum computation and input remain unknown to the prover. After we have derived the results, we have learnt that Broadbent, Fitzsimons, and Kashefi [BFK08] have independently derived "universal blind quantum computation" using completely different methods (measurement based quantum computation). Their construction implicitly implies similar implications.

:: Tue 1/20/09, 4:15 in 36-428 (QIP seminar)

Sattath,Or (Hebrew University)
The Pursuit For Uniqueness: Extending Valiant-Vazirani Theorem to the Probabilistic and Quantum Settings

In 1985, Valiant-Vazirani showed [VV85] that solving NP with the promise that "yes" instances have only one witness, is powerful enough to solve the entire NP class (under randomized reductions).We are interested in extending this result to the quantum setting. We prove extensions to the classes Merlin-Arthur (MA) and Quantum- Classical-Merlin-Arthur (QCMA) [AN02].Our results have implications on the complexity of approximating the ground state energy of a quantum local Hamiltonian with a unique ground state and an inverse polynomial spectral gap. We show that the estimation, within polynomial accuracy, of the ground state energy of poly-gapped 1-D local Hamiltonians is QCMA-hard, under randomized reductions. This is in strong contrast to the case of constant gapped 1-D Hamiltonians, which is in NP [Has07]. Moreover, it shows that unless QCMA can be reduced to NP by randomized reductions, there is no classical description of the ground state of every poly-gapped local Hamiltonian which allows the efficient calculation of expectation values.Finally, we conjecture that an analogous result to the class Quantum Merlin-Arthur(QMA) is impossible. This is formulated by separating between the two relavant classes, QMA and its "unique" version UQMA, using the definition by Aaronson and Kuperberg [AK06] of quantum oracles.

:: Mon 2/2/09, 11:45 in 4-331

Guifre Vidal (University of Queensland)
Recent Progress in Entanglement Renormalization

Entanglement Renormalization (ER) has been proposed as a real space renormalization group transformation for quantum lattice systems in D spatial dimensions [Phys. Rev. Lett. 99, 220405 (2007)]. Its main novelty is the use of disentanglers, namely unitary transformations that act accross a spin block boundary, to remove short-range entanglement from the system's ground state. In this talk I will first review the basic concepts underlying ER and then present a summary of the most recent results. Specifically, I intend to describe the simulation of lattice systems at a quantum critical point by exploiting scale invariance; and the simulation of two dimensional lattice systems that are beyond the reach of Monte Carlo sampling techniques, including spin models of frustrated antiferromagnets.

:: Mon 2/9/09, 4:30 in 4-237 (QIP seminar)

Matthew Hastings (Los Alamos National Laboratory)
A counter-example to additivity: using entanglement to boost communication capacity

Suppose Alice is using a noisy quantum channel to send classical information to Bob. For example, she might send single photons over a fiber optic line. How should she do this? In particular, should she use entanglement or should she send unentangled input states? The additivity conjecture in quantum information theory states that it is never useful for her to use entanglement. In fact, there are several related additivity conjectures, depending on the use of entanglement for different tasks. I will present a counter-example to one of these conjectures, the minimum output entropy conjecture, implying that all of these conjectures are false, and that in some circumstances Alice can increase the communication capacity by using entangled states.

:: Tue 2/17/09, 4:15 in 36-428 (QIP seminar)

Roland,Jeremie (NEC Laboratories America)
The communication complexity of non-signaling distributions

We study a model of communication complexity that encompasses many well-studied problems, including classical and quantum communication complexity, the complexity of simulating distributions arising from bipartite measurements of shared quantum states, and XOR games. In this model, Alice gets an input x, Bob gets an input y, and their goal is to each produce an output a,b distributed according to some pre-specified joint distribution p(a,b|x,y). Our results apply to any non-signaling distribution, that is, those where Alice's marginal distribution does not depend on Bob's input, and vice versa, therefore our techniques apply to any communication problem that can be reduced to a non-signaling distribution, including quantum distributions, Boolean and non-Boolean functions, most relations, partial (promise) problems, in the two-player and multipartite settings. We give elementary proofs and very intuitive interpretations of the recent lower bounds of Linial and Shraibman, which we generalize to the problem of simulating any non-signaling distribution. The lower bounds we obtain are also expressed as linear programs (or SDPs for quantum communication). We show that the dual formulations have a striking interpretation, since they coincide with maximum violations of Bell and Tsirelson inequalities. The dual expressions are closely related to the winning probability of XOR games. We show that as in the case of Boolean functions, the gap between the quantum and classical lower bounds is at most linear in size of the support of the distribution, and does not depend on the size of the inputs. This translates into a bound on the gap between maximal Bell and Tsirelson inequalities, which was previously known only for the case of Boolean outcomes with uniform marginals. Finally, we give an exponential upper bound on quantum and classical communication complexity in the simultaneous messages model, for any non-signaling distribution. One consequence of this is a simple proof that any quantum distribution can be approximated with a constant number of bits of communication. Joint work with:Julien Degorre, Marc Kaplan and Sophie Laplante

:: Mon 3/16/09, 4:15 in 36-428 (QIP seminar)

Aaronson,Scott (MIT)
The Power of Quantum Advice

I'll describe a powerful new result about quantum advice: namely, given any state rho on n qubits, there exists a local Hamiltonian H on poly(n) qubits (e.g., a sum of two-qubit interactions), such that *any* ground state of H can be used to simulate rho on all circuits of a fixed polynomial size. In terms of complexity classes, this implies that BQP/qpoly is contained in QMA/poly, superseding the previous result that BQP/qpoly is contained in PP/poly. Indeed, we can exactly characterize the /qpoly operator, as equivalent in power to *untrusted* quantum advice combined with trusted *classical* advice. The proof of this theorem relies on my previous result about the learnability of quantum states, as well as a new combinatorial result called the "majority-certificates lemma" that might be of independent interest. Joint work with Andrew Drucker.

:: Mon 3/30/09, 4:15 in 36-428 (QIP seminar)

Frederick Strauch (Williams College)
Quantum walks in the wild: perfect quantum state transfer with superconducting qubits

Superconducting quantum bits are artificial atoms that can be wired up into complex structures. I will present a theoretical proposal to implement perfect quantum state transfer between any two nodes of a hypercube network. This example of novel quantum transport in an artificial solid has many applications for quantum computing. It would also provide an experimental simulation of a continuous-time quantum walk with exponential speedup over the corresponding classical walk. This speedup is found to be remarkably robust to both decoherence and diagonal disorder, but only for certain (inefficient) representations of the hypercube.

:: Mon 4/13/09, 4:15 in 36-428 (QIP seminar)

Debbie Leung (University of Waterloo)
Continuity of quantum channel capacities

Many capacities of a quantum channel are given by expressions that involve asymptotically large number of uses of the channel, thus, there is no a priori reason for the capacities to be continuous. In this talk, we prove that the ability to transmit classical data, private classical data, quantum data are all continuous.

:: Mon 4/27/09, 4:15 in 34-401B (QIP seminar)

Smith,Graeme (IBM)
Quantum Communication With Zero-Quantum-Capacity Channels

Besides transmitting ordinary classical information, some quantum channels can faithfully transmit intact quantum states. A channel's capacity for such coherent transmission, its quantum capacity, is of central importance in quantum information theory as it measures the optimum performance of quantum error-correcting codes. I will show that two quantum channels, each of zero quantum capacity, can nevertheless achieve a positive quantum capacity when used together. This result contrasts sharply with the classical setting, where the capacity of a channel is independent of what other channels are available. This uniquely quantum effect unveils a rich structure in the theory of quantum communications and shows that there are several kinds of quantum information, the ability to transmit each of which is necessary but not sufficient for faithful quantum communication.

:: Mon 5/4/09, 4:15 in 36-428 (QIP seminar)

Broadbent,Anne (IQC)
Universal Blind Quantum Computation

We present a protocol which allows a client to have a server carry out a quantum computation for her such that the client's inputs, outputs and computation remain perfectly private, and where she does not require any quantum computational power or memory. The client only needs to be able to prepare single qubits randomly chosen from a finite set and send them to the server, who has the balance of the required quantum computational resources. Our protocol is interactive: after the initial preparation of quantum states, the client and server use two-way classical communication which enables the client to drive the computation, giving single- qubit measurement instructions to the server, depending on previous measurement outcomes. Our protocol works for inputs and outputs that are either classical or quantum. We give an authentication protocol that allows the client to detect an interfering server; our scheme can also be made fault-tolerant.

:: Tue 5/5/09, 4:00 in 26-214

Girvin,Steven (Yale)
Demonstration of entanglement on demand and two-qubit quantum algorithms in circuit QED

The 'circuit QED' architecture consists of Josephson junction qubits placed inside a coplanar waveguide microwave resonator. This talk will present an introduction to the quantum optics of these novel electrical circuits and describe recent experiments in the Schoelkopf lab at Yale. With the help of a controlled phase gate based on precision control and shaping of microwave pulses, it is now possible to achieve two-qubit entanglement on demand with concurrence up to 94% and to run the Grover search and Deutsch-Josza quantum algorithms with fidelities exceeding 80%. This success is based on a qubit design with long coherence times and the ability to simultaneously readout the state of two qubits (so far still with low fidelity).

:: Mon 5/11/09, 4:15 in 36-428 (QIP seminar)

Jordan,Stephen (Caltech)
Permutational Quantum Computation

In topological quantum computation the geometric details of a particle trajectory are irrelevant; only the topology matters. This is one reason for the inherent fault tolerance of topological quantum computation. I will describe a model in which this idea is taken one step further. Even the topology is irrelevant. The computation is determined solely by the permutation of the particles. Unlike topological quantum computation, which requires anyons, permutational quantum computations can in principle be performed by permuting ordinary spin-1/2 particles. It seems possible that permutational quantum computation is less powerful than standard quantum computation (BQP). Nevertheless I will present algorithms for this model which provide apparent exponential speedup over classical algorithms.

:: Mon 5/18/09, 4:15 in 36-428 (QIP seminar)

Navascues,Miguel (Imperial College London)
The power of symmetric extensions for entanglement detection

In this talk, I will analyze the speed of convergence of algorithms for entanglement detection based on PPT (Positive Partial Transpose) symmetric extensions, as conceived by Doherty et al. [1]. I will show that the states defined in [1] can be made separable just by partially depolarizing one of the parts. While the amount of necessary noise to induce separability on states that admit a plain N-symmetric extension decreases as O(1/N), the corresponding perturbation for states arising from PPT N-symmetric extensions decreases at least as O(1/N^2). I will use these results to estimate and compare the time and space complexity of both algorithms. Finally, I will consider the power of the PPT criterion alone: I will show how to derive upper bounds on the maximum possible distance between a PPT entangled state and the set of separable states by means of a simple construction. [1] A. C. Doherty, P. A. Parrilo and F. M. Spedalieri, Phys. Rev. A 69, 022308 (2004).