whaley group

Berkeley Quantum Information and Computation Seminar

Fortnightly on Tuesdays, 2:00 pm 410 Hearst Mining Building (map)

If you're interested in joining the seminar mailing list, presenting a talk, or just more information, contact Mohan Sarovar : msarovar (-at-) berkeley (-dot-) edu

Spring 2009

2/25/2009 Special time and day: 1pm, 410HMB
Alberto Grunbaum (UC Berkeley)
Quantum Random Walks(QRWs) and orthogonal polynomials
For classical random walks (more precisely for classical birth-and-death processes) there is a well known and useful relation with orthogonal polynomials on the real line. We show that a similar connection can be made in the case of QRWs both on the nonnegative integers as well as in all the integers. This time one is dealing with (Laurent) polynomials on the unit circle.
One benefit of this association is that we show, that in contrast with the classical case when all states are either recurrent or transient this is no longer the case in the quantum case. The key to this observation is the study of the orthogonality measure going along with the polynomials in question.
This is joint work with MJ Cantero,L Moral and L Velazquez from Zaragoza, Spain.
1/20/2009 Special time and place: 2:30-4pm, Wozniak Lounge--430 Soda Hall
Elad Eban (Hebrew University)
Interactive Proofs for Quantum Computation
The widely held belief that BQP strictly contains BPP raises fundamental questions: Upcoming generations of1 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, Crepeau, 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.
Joint work with Dorit Aharonov and Michael Ben-Or

Fall 2008

11/25/2008 Special time and place: 12:30-2pm, 180 Tan Hall
Hartmut Haffner (UC Berkeley)
Quantum computing with trapped ions
This lecture will cover the experimental basics of ion trap quantum computers: For this we will discuss how to initialize quantum registers, how to implement universal sets of quantum gates, and how to measure the density matrix of the ion trap register. Finally, we will cover applications of these techniques, namely the generation and analysis of entangled states and an implementation of the Deutsch algorithm.
11/25/2008 Special time 10-11am
Daniel Lidar (USC)
Preserving and extending quantum coherence: from the spin echo effect to fault tolerant quantum computation
Dynamical decoupling pulse sequences have been used to extend coherence times in quantum systems ever since the discovery of the spin-echo effect. But while for good reasons the nuclear magnetic resonance (NMR) community has typically been content with moderate line narrowing, in quantum computing extremely high levels of coherence are required in order to perform meaningful computational tasks. In this talk I will describe a method of recursively concatenated dynamical decoupling pulses, designed to overcome both decoherence and operational errors [1]. For bounded-strength, non-Markovian environments, such as for the spin-bath that arises in electron- and nuclear-spin based solid-state quantum computer proposals, it is strictly advantageous to use concatenated, as opposed to standard periodic dynamical decoupling pulse sequences. Namely, the concatenated scheme is both fault-tolerant and super-polynomially more efficient, at equal cost [2,3]. Preliminary experimental results on NMR of 13C in adamantene (due to Dieter Suter, Dortmund), and NMR of the 31P donor in Si (due to Steve Lyon, Princeton), demonstrating the advantages of concatenated decoupling, will also be presented. Time permitting, I will describe our recent results on the construction of a universal set of quantum logic gates whose fidelity can be kept arbitrarily high for essentially arbitrarily long times in the presence of coupling to a spin bath, by use of concatenated decoupling.

References:
[1] K. Khodjasteh and D.A. Lidar, "Fault-Tolerant Quantum Dynamical Decoupling", Phys. Rev. Lett. 95, 180501 (2005).
[2] K. Khodjasteh and D.A. Lidar, "Performance of Deterministic Dynamical Decoupling Schemes: Concatenated and Periodic Pulse Sequences", Phys. Rev. A 75, 062310 (2007).
[3] K. Khodjasteh and D.A. Lidar, "Rigorous Bounds on the Performance of a Hybrid Dynamical Decoupling-Quantum Computing Scheme", Phys. Rev. A 78, 012355 (2008).
11/18/2008
Neil Na (Stanford University)
Polaritonic quantum phase transition and applications
I will present two experimental proposals to observe the superfluid to Mott-insulator quantum phase transition via polaritons in semiconductor nanostructures. Photons are confinded in the cavity array and strongly interact with each other via the strong coupling to either impurity bound-excitons or quantum well excitons. In particular, I will show how to extract high-quality nonclassical photons using quantum phase transition in the latter case.
10/28/2008
Dave Bacon (University of Washington)
Doubling the Toric Code
One of the most important stabilizer subspaces codes in quantum error correction is the toric code discovered by Kitaev in 1996. Here I will discuss a new code derived from Kitaev' code which is a stabilizer subsystem code. This code shares some of the remarkable fault-tolerance properties of the stabilizer subsystem code derived from the quantum compass model. Further I will show how puncturing this code can be used to create encoded qubits.
10/21/2008 Postponed. New date: TBA
Matthew Grace (Sandia National Laboratories)
Protecting Quantum Information with Optimal Control
Methods of optimal control are applied to elements of a quantum information processor (QIP), providing solutions for the generation of logical operations and the suppression of undesired environmental effects. The results illustrate how practical quantum computing can be greatly facilitated by optimal control theory and reveal interesting physical insights through the discovery of effective control mechanisms. Optimization algorithms are developed which generate controls that protect the QIP from the effects of the environment, and simultaneously achieve a target objective, e.g., a state-to-state transition or unitary quantum operation. For the optimal control of quantum operations, a novel state-independent distance measure is developed to evaluate operation fidelity. We considered different types of environments producing either reversible or irreversible dynamics. The resulting optimal controls cleverly identify and use various properties of the composite system to effectively attain the desired objectives. Controls obtained for systems with reversible dynamics utilize induced coherence revivals and are robust to random variations in system-environment coupling strengths. For irreversible dynamics, the controls employ decoherence-free states and are practically insensitive to the structure of random environments.

Spring 2008

2/5/2008
Zeph Landau (City University of New York (City College), Department of Mathematics)
That's what a quantum computer does?
I'll present a geometric view of quantum computation as the approximation of tensor networks. This point of view yields algorithms for additive approximations of statistical mechanical models, and clarifies the quantum algorithms for the approximation of the Jones and Tutte polynomial.
No prior knowledge of any of the words in the abstract will be needed (joint work with I. Arad).
2/19/2008
Hui Deng (Caltech, Department of Physics)
-
-
2/26/2008
Thaddeus Ladd (E. L. Ginzton Laboratory, Stanford University & National Institute of Informatics, Tokyo)
Scalable Semiconductor-based Quantum Computers
Large-scale quantum computers offer exciting possibilities for simulation of quantum systems and other computational tasks, but they are far from being a technological reality. Early proposals for quantum computers based on silicon have been supported by multiple experiments demonstrating the promise of silicon for long-lived quantum memory and atomic-scale fabrication. However, these proposals do not support a computer architecture consistent with the requirements of fault-tolerant operation, which is needed to truly allow scalability. Such an architecture is better approached via integrated semiconductor nanophotonics. I will present new proposals for semiconductor-based quantum computers and quantum communication networks based on emerging nanophotonics technologies and cavity QED, as well as prospects for developing a complete fault-tolerant architecture. Finally, I will discuss the promise of silicon in comparison to other semiconductors for the experimental realization of such an architecture.
3/4/2008
Matthew Hastings (Los Alamos National Laboratory -- T13)
Classical and Quantum Expanders
Expander graphs are graphs which have only a small number of edges connecting to each node but which mix rapidly. They appear in many places in classical computer science. They are used to de-randomize algorithms, in communication networks, in error-correcting codes, and many other places. Quantum expanders are a recently developed quantum extension of these ideas. I will introduce classical expanders, then introduce quantum expanders through their application to constructing certain highly entangled states with few correlations. Then, I will present randomized constructions of quantum expanders, and use ideas from quantum chromodynamics, the theory of the strong force, to analyze this random construction. I will finally discuss future applications of quantum expanders.
4/29/2008
Nemanja Isailovic & Mark Whitney (UC Berkeley, Department of Computer Science)
Tools for designing fault tolerant devices for large scale quantum applications
Our work focuses on bridging the gap between quantum algorithm development and the fabrication of quantum computing devices. We present a computer-aided design flow for quantum devices in trapped ion technology. The tool flow takes a logical application circuit and synthesizes an encoded, error-corrected spatial ion trap layout with the necessary fault tolerance properties. Insertion of error correction is automated and accounts for qubit decoherence due to computation, communication and idleness.
Our layout heuristics are targeted toward minimizing both communication and idleness on the critical path of execution. To this end, we have designed and simulated two key support infrastructures for our quantum layout: ancilla factories and a qubit teleportation network for long distance communication. The tool flow uses these basic modules to construct a customized layout for a given quantum circuit, along with the resulting error property analysis.

---------------------------------------------------------------------------------

Fall 2007

9/4/2007
Eun-Ah Kim (Stanford University, Department of Physics)
Hearing non-abelian statistics from a Moore-Read double point contact interferometer
Experimental confirmation of the non-abelian nature of the $\nu\!=\!5/2$ quantum Hall state is crucial for the realization of the enticing idea of topological quantum computation. We propose noise oscillation measurements in a double point contact, accessible with current technology, to seek for such evidence. Calculating the voltage and temperature dependence of the current and noise oscillations, we predict two possible outcome for the nonzero interference {\it noise} in the Moore-Read state due to its non-abelian nature. Comparison between our predictions for the Moore-Read state with experiments on $\nu\!=\!5/2$ will serve as a much needed test for the nature of $\nu\!=\!5/2$ state.
9/18/2007
Lin Tian (Stanford University, Department of Physics)
Cavity QED of the low-frequency fluctuators in the Josephson junction tunnel barrier
The microscopic behavior of the amorphous two-level fluctuators in Josephson junction devices and their coupling mechanism with the quantum phase variables of the junctions have long been an interesting question that puzzles the mesoscopic physics community. New interest on this question has been aroused recently by the progress in studying the superconducting qubits. Previous experiments have indicated that the two-level fluctuators can be a very serious source of decoherence for the superconducting qubits, generating the low-frequency noise. The understanding and control of such fluctuations are hence crucial for realizing high fidelity quantum logic gates with superconducting quantum devices. In this talk, we present a practical scheme that can probe the two-level fluctuators microscopically using a cavity QED approach.

(1) L. Tian and R. W. Simmonds, accepted by PRL, (2007).
(2) L. Tian, Phys. Rev. Lett. 98, 153602 (2007).
10/2/2007
Travis Hime (UC Berkeley, Department of Physics)
Current-Controlled Coupling of Flux Qubits
The ability to switch the coupling between quantum bits (qubits) on and off is essential for implementing many quantum computing algorithms. We have demonstrated such control with two, three-junction flux qubits coupled together via their mutual inductances and via the dc SQUID (Superconducting Quantum Interference Device) that reads out their magnetic flux states. With the qubits biased at the same frequency, the interaction produced an avoided crossing in their energy spectrum. At the avoided crossing transitions to the first excited state were suppressed and transitions to the second excited state enhanced, indicating formation of singlet and triplet states in the coupled-qubit system. The observed peak amplitudes were consistent with calculated matrix elements. When both qubits were biased at their degeneracy points, a level repulsion was observed in the energy spectrum. A bias current applied to the SQUID in the zero-voltage state prior to measurement induced a change in its dynamic inductance, reducing the coupling energy controllably to zero and even reversing its sign. The dependence of the splitting on the bias current was in good agreement with predictions. Coherent oscillations were observed on individual qubits and on the coupled system, and decoherence was characterized as a function of flux bias.
10/9/2007
Jiri Vala (National University of Ireland, Department of Mathematical Physics)
Numerical experiments with the Kitaev honeycomb lattice model
Topological order in two-dimensional quantum systems is manifested in their low energy spectral properties by finite ground state degeneracy and by presence of an excitation gap at the thermodynamic limit. This suggests that the low-energy spectrum can be used to probe topological order in these systems. I will discuss low-energy spectral properties of the Kitaev honeycomb quantum lattice model on torus with special emphasis on finite-size effects.
10/16/2007
Vadim Smelyanskiy (NASA Ames, Center for Nanotechnology)
POSTPONED to 11/27/07
-
10/30/2007
Alioscia Hamma (University of Southern California, Department of Chemistry)
Entanglement in Topological Order
Topological order is a novel subject in theoretical condensed matter. It describes those states of the matter, like the fractional quantum Hall liquids, that defy the description in terms of breaking of symmetry and local order parameters. Topological order is based instead on topological symmetries. In quantum information science topologically ordered states are important because robust against perturbations and decoherence. Entanglement, on the other hand, is the fundamental resource of quantum information. How much entanglement can be stored in a bipartite system with topological order? How does it behave for a critical system? How fast can we produce topological order? Does entanglement reveal topological order? How does entanglement resist to temperature? Can entanglement explain topological order? The talk will address all these questions.
11/13/2007
Alexander Korotkov (UC Riverside, Department of Electrical Engineering)
Continuous quantum measurement of solid-state qubits
The starting point of the talk is a simple question: what happens to a solid-state qubit in the process of its continuous measurement by a detector? While for ensemble of qubits the measurement simply leads to decoherence, the evolution of a single qubit is significantly different: it depends on the detector output and may be fully coherent, though non-unitary. The theory describing such evolution has been developed relatively recently and provides a number of experimentally testable predictions, including nondecaying Rabi oscillations maintained by a quantum feedback loop, qubit entanglement by measurement, quantum nondemolition squeezing of a nanoresonator, undoing of a weak measurement (quantum undemolition), etc. The first experiment verifying the coherent non-unitary evolution of a superconducting qubit due to partial measurement has been realized last year at UCSB, followed by recent demonstration of the quantum undemolition.
11/27/2007
Vadim Smelyanskiy (NASA Ames, Center for Nanotechnology)
Long -range elastic coupling and decoherence-free subspaces for spin and orbital excitations of lithium donors in silicon
Electron spins of shallow lithium donors in silicon hundreds of nanometers apart can be strongly can be strongly coupled to each other via the exchange of virtual acoustic phonons much similar to the electric dipole interaction formed by an exchange of virtual longitudinal photons. We will describe the nature of this interaction due to the charge-to spin conversion mechanism in a lithium electron ground state manifold and effects of external stress and magnetic field that can change both the magnitude and the sign of the interaction. Electronic states of an interstitial lithium donor in silicon possesses a number of unique properties originating from its location at the interstitial tetrahedral symmetry cite in silicon lattice. We will describe symmetry-based selection rules that define certain dechoherence- free subspaces within the 12-dimensional ground state manifold of a lithium donor electron. These selection rules lead to anomalously long lifetimes of spin and orbital excitations of a lithium donor electron. We will discuss a spin-glass nature of the system of strongly coupled Li spins in silicon as well as possible realization of quantum adiabatic algorithm in this system.

---------------------------------------------------------------------------------

Spring 2007

2/20/2007
Karoline Wiesner (UC Davis, Computational Science and Engineering)
Intrinsic Quantum Computation
We consider a quantum process as a quantum information source. I will introduce ways to measure information storage in quantum processes, using a recently introduced computation-theoretic representation that accounts for measurement effects. Correlations in the generated sequences show that measured quantum systems store and process information in their behavior. We analyze this form of intrinsic computation by means of various information-theoretic quantities: entropy rate, excess entropy and transient information. I will present examples of simple spin-systems. The results encourage a new perspective on information storage and processing as being intrinsic to behavior of even simple quantum systems.

References:
"Computation in finitary quantum processes", K. Wiesner and J. P. Crutchfield. http://arxiv.org/abs/quant-ph/0608206, 2006.
"Intrinsic quantum computation", J. P. Crutchfield and K. Wiesner. http://arxiv.org/abs/quant-ph/0611202, 2006.
3/13/2007
Layla Hormozi (Florida State University, Department of Physics)
Topological Quantum Compiling
It has been shown that certain two-dimensional systems with non-Abelian quasiparticle excitations can be used for topological quantum computing (TQC). In TQC quantum information is stored in exotic states of matter which are intrinsically protected from decoherence, and quantum computation is carried out by dragging particle-like excitations (quasiparticles) around one another in two space dimensions. The resulting quasiparticle trajectories define worldlines in three-dimensional space-time, and the corresponding computation depends only on the topology of the braids formed by the world-lines. A variety of proposed fractional quantum Hall states are believed to possess quasiparticles that can be used for TQC -- among them the so-called "Fibonacci anyons". For purposes of quantum computing, Fibonacci anyons are essentially equivalent to quasiparticles of the Read-Rezayi states at level k = 3. These states are conjectured to exist in the experimentally observed \nu = 12/5 fractional quantum Hall state. I will review the basic ideas behind TQC, and describe our work showing explicitly how to translate (compile) arbitrary quantum algorithms into specific braiding patterns for Fibonacci anyons. Time permitting, I will also describe our recent work that generalizes previous results to quasiparticles of all Read-Rezayi states with k > 4.
3/20/2007
Ramon van Handel (Caltech, Control and Dynamical Systems)
(Not-so-)Quantum Filtering
The technique of quantum filtering has been developed during the last decade, using various approaches and under various names (stochastic master equations, quantum trajectories, ...) The goal is to try to estimate--on the fly--what is going on with a quantum system (e.g., an atom), which we can only observe indirectly (e.g., by observing the scattered light from a laser). In this talk I take the point of view that there is hardly anything quantum about quantum filtering: very little is needed beyond standard classical tools, which have been available for almost four decades and have been applied in the space program, in radar tracking, and in innumerable other applications. Far from being a disappointment, the ``classicality'' of quantum filtering provides a particularly clean framework in which the theory can be understood and applied. I will discuss the fundamental connection with problems of feedback control and statistical sequential analysis. I will finally briefly highlight the problem of robustness, where making things as classical as possible highly simplifies the analysis.
4/10/2007
CANCELLED
-
-
4/17/2007
Raisa Karasik (UC Berkeley, Applied Science and Technology)
Decoherence-free subspaces
A decoherence-free subspace (DFS) is a collection of states that is immune to the dominant noise effects created by the environment. DFS is usually studied for states involving two or more particles and is considered a prominent candidate for quantum memory and quantum information processing. We analyze similarities and differences between various approaches to DFSs present in the literature and show that an excessively restrictive assumption on immunity from decoherence for an arbitrary initial environment state can be relaxed for practical DFS cases. We discuss necessary and sufficient conditions for the existence of a dynamically stable DFS in the important class of systems whose dynamics is described by Markovian master equations.
We prove that a perfect physical DFS requires co-located particles, i.e., the Dicke limit. The assumptions made are very general and invoke a homogeneous environment with energy-conserving coupling to the particles. We indicate when a DFS outside the Dicke limit may be possible; this includes molecular and confined systems.
4/24/2007
Vito Scarola (University of Maryland, Department of Physics)
Proposals to Observe Topological Order in Cold Atom Optical Lattices
Cold atom optical lattices offer the potential to effectively simulate lattice models of intrinsic mathematical interest using laboratory experiments. These clean and tunable systems have been proposed to realize several novel many-body phases of matter including topological phases. Excitations of certain topological phases have been proposed as the basis for topological quantum computers. I will discuss recent theoretical proposals to identify, measure, and manipulate excitations in topological phases of matter in the optical lattice setting.
5/1/2007
Travis Beals (UC Berkeley, Department of Physics)
Making Quantum Key Distribution Practical as a Replacement for Public-key Encryption
Quantum key distribution must overcome two major challenges before it can become a viable replacement for public key encryption: transmission distance limitations, and impersonation (man-in-the- middle) attacks. Current approaches for solving these two problems either scale poorly with network size or require the unrealistic assumption that all nodes in a network are perfectly trustworthy. We demonstrate techniques for solving both problems that require only partially trustworthy nodes (i.e., a certain fraction of the nodes can be dishonest). Our techniques could be used to build large QKD networks with hardware that is commercially available today.

---------------------------------------------------------------------------------

Fall 2006

10/03/2006
Robert Kosut (SC Solutions, Sunnyvale, CA)
Design of quantum systems via convex optimization
A number of problems in the design of quantum systems for quantum computing can be formulated as a convex optimization either directly or indirectly by relaxation. After a brief review of convex optimization, applications will be presented for state tomography, process tomography, Hamiltonian parameter estimation, quantum state detection, and quantum error correction.
10/17/2006
Irfan Siddiqi (UC Berkeley, Physics Department)
Dispersive Measurements of Superconducting Qubits
I will review the operation of superconducting qubits which involve the manipulation of quantum states by coupling to the flux, charge, and phase degrees of freedom. In particular, I will describe measurement strategies in which the qubit is coupled to a harmonic oscillator to implement a dispersive, non-demolition state readout. Such readout schemes can also be realized with non-linear elements which both boost sensitivity and also provide an avenue to probe the limits of macroscopic quantum coherence.
10/31/2006
Mikko Möttönen (Helsinki University of Technology, Finland)
Suppression of decoherence and 1/f noise in one-qubit operations
Noise and decoherence are the main concerns in building a large scale physical realization of a quantum computer. In the first part of my talk, I will present an analytical master equation describing the average qubit dynamics under classical Markovian noise. To motivate the use of this equation also as a model for the noise arising from the environment of the qubits mediaded by quantum mechanicl coupling, I show that in the case of random telegraph noise (RTN) equivalent qubit dynamics arise from two different couplings to the environment. In the second part of the talk, I discuss how 1/f noise can arise from either a sum of independent RTN fluctuators or from a single multi-level Markovian fluctuator. The 1/f noise is interesting since it is encountered in various physical systems, and especially has been claimed to be the most essential source of decoherence in solid state qubit systems. Finally, I show how the errors due to 1/f noise in one-qubit operations can be suppressed using pulse optimization methods.
11/14/2006
Robert Spalek (UC Berkeley, EECS Department)
Quantum Random Walk Algorithms
Quantum computers can search an unsorted database of size N in time sqrt(N) [Grover, 1996]. This search algorithm is very universal and one can use it as a subroutine for solving a number of other problems, for example element distinctness, that is testing whether all number in a sequence of length N are distinct, in time N^{3/4}. Ambainis [2004] published a very elegant algorithm based on quantum random walks solving this problem in time N^{2/3}, which is optimal. Szegedy [2004] generalized his quantum walk technique to all symmetric Markov chains and simplified the proof. The resulting algorithm is almost as universal as unsorted search, and it was successfully applied to triangle finding in time N^{1.3} [Magniez, Santha, Szegedy, 2005], group commutativity testing in time N^{2/3} [Magniez, Nayak, 2005], and verification of matrix products [Buhrman, Spalek, 2006].
I am going to review the basics of quantum walks and show how to apply them in these quantum search algorithms.
11/28/2006
Jan Korsbakken (UC Berkeley, Physics Department)
Lions or kittens? Defining a measure of "size" for Schrödinger cat states
Ongoing experiments claim to push the frontiers of quantum mechanics ever closer to the macroscopic realm by realizing "Schrödinger cat"-like superposition states in larger and larger systems. This has raised the question of how to define whether or not a quantum superposition state can be called a "large" cat state, and how to compare the macroscopicness of such states in different physical systems. In this talk I will discuss one such measure, based on what measurements are sufficient to collapse a superposition into one of its branches. I will give a brief overview over experiments which claim to have realized larger-than-miniscule cat states, and describe a test case (bosons with attractive interactions trapped in a double-well potential) for which we have studied the behavior of our measure analytically and numerically.
12/12/2006
Greg Kuperberg (UC Davis, Mathematics Department)
Quantum proofs and quantum oracle separations
In the general quest to find new algorithms, theoretical computer scientists are familiar with two important fellow travellers: complexity classes and oracles. These fellow travellers are also related to each other, because we do not know how to separate most of the interesting complexity classes except with the aid of oracles. Complexity classes and oracle are particularly significant in quantum computation, for several reasons.
The most important classical complexity classes are P and NP. The quantum anologue of P is BQP, but there are at least two natural analogues of NP: QMA and QCMA. In both classes, a BQP "Arthur" checks a proof supplied by "Merlin". In QCMA, the proof is a classical message, while in QMA, it is a quantum state. The natural question of comparing QMA to QCMA amounts to asking whether a quantum proof can better persuade a quantum audience than a classical proof can.
I will discuss the result, due to Scott Aaronson and myself, that there is an oracle that separates QMA from QCMA. Indeed, relative to a suitable oracle, some assertations may require an exponentially longer classical proof than quantum proof. However, the oracle itself is quantum; our result introduces the technique of quantum oracle separations. A classical oracle separation is still not known. If time permits, I will discuss the side result that a well-known oracular problem that was shown by Watrous to be in QMA (but not classical MA) is probably in QCMA, and is therefore unlikely to show that quantum proofs are powerful.
Past seminars