Transcript document

Quantum Information Science
John Preskill
DoE Review
24 July 2007
Research focusing on the foundations of the subject:
1) Algorithms/Complexity: Quantum algorithms that achieve speedups
relative to classical algorithms, and limits on such algorithms.
2) Entanglement: Quantum entanglement and the theory of transformations
among quantum states.
3) Cryptography/Communication: Security of quantum cryptographic
protocols, and other types of communication using quantum states.
4) Error Correction/Fault Tolerance/Control: Protection of quantum
information, and using quantum error-correcting codes, fault-tolerant
protocols, and quantum feedback for quantum information processing.
5) Implementation/Experiment: Physical implementations of quantum
information processing.
6) Fundamental physics: Connections between quantum information
science and other aspects of fundamental science.
2007 Ph.D.s
Panos Aliferis
“Level reduction and the quantum threshold theorem”
 IBM, Yorktown Heights
Parsa Bonderson
“Nonabelian anyons and interferometry”
 Microsoft Station Q, Santa Barbara
Michael Zwolak
“Dynamics and simulation of open quantum systems”
 Los Alamos National Lab
Other Students
Ersen Bilgin, Using “belief propagation’’ algorithms for efficient simulation of
many-body quantum systems.
Kovid Goyal, Fault-tolerant quantum computation based on “resource states”
and topological coding.
Prabha Mandayam, Formulating necessary and sufficient conditions for
approximate quantum error correction.
Hui Khoon Ng, Applying the effective field theory method to quantum noise.
Greg ver Steeg, Characterizing the computational power of systems with
continuous quantum variables, including quantum field theory.
Note: My students are not financially supported by DoE (except for
Kovid Goyal, the theory group computer system administrator). DoE
contributes 9% of my salary.
Quantum nonlocality, communication, cryptography (2006-07)
• quant-ph/0610203 (Lo, Preskill) Security of quantum key distribution using weak
coherent states with nonrandom phases. Security proof that applies when key
information is encoded in the relative phase of a coherent-state reference pulse and a
weak coherent-state signal pulse. The proof works even if the reference pulse is bright
and has a phase known by the adversary.
• arXiv:0705.4282 (Blume-Kohout, Ng, Poulin, Viola) The structure of preserved
information in quantum processes. Introduced a general characterization of informationpreserving structures. Proved that the fixed states and observables of an arbitrary
process are linearly isomorphic to a matrix algebra. Found an efficient algorithm for
finding all noiseless subsystems.
• quant-ph/0611001 (Toner, Verstraete) Monogamy of Bell correlations and Tsirelson’s
bound. Study of Bell inequality violation in a tripartite system ABC, characterizing the
trade-off between the nonlocality of the Bell correlations observed by AB and of those
observed by AC.
• quant-ph/0704.2903 (Kempe, Kobayashi, Matsumoto, Toner, Vidickl) On the power of
entangled provers: immunizing games agains entanglement. Two generic ways to make
multi-prover classical games resistant against entangled provers.
Fault-tolerant (and topological) quantum computing (2006-07)
• quant-ph/0703264 (Aliferis, Gottesman, Preskill) Accuracy threshold for postselected
quantum computation. Proof applies to a scheme where states prepared offline are
protected by an error-detecting code. Established lower bound on the accuracy
threshold, 1.04  10-3, the highest proved so far.
• quant-ph/0610063 (Aliferis, Cross) Subsystem fault tolerance with the Bacon-Shor
code. Codes with an unfixed gauge freedom lead to a highly efficient method for faulttolerant error correction that can be implemented using only nearest-neighbor two-qubit
measurements.
• quant-ph/0703143 (Raussendorf, Harrington, Goyal) Topological fault-tolerance in
cluster state quantum computation. Topologically protected quantum gates are realized
by performing measurements that impose appropriate boundary conditions on a threedimensional “cluster state.” (The spatial dimensionality can be reduced to two by
converting one spatial axis of the cluster into time.)
• quant-ph/0608119 (Bonderson, Shtengel, Slingerland) Decoherence of anyonic charge
in interferometry measurements. Measuring anyonic charge using a Mach-Zehnder
interferometer. Visibility of the interference is related to the topological S-matrix of the
anyon model.
• cond-mat/0611412 (Zwolak) Numerical ansatz for solving integro-differential equation
with increasingly smooth memory kernels: spin-boson model and beyond. New method
for studying real-time dynamics of systems that are strongly coupled to the environment;
reduces computational cost of simulation.
Subsystem codes
Hilbert space decomposes as:
H=
syndrome
(s)
(s)
H

H
T
 L
s
“logical”
subsystem
“gauge”
subsystem
• A subsystem code becomes a standard stabilizer code when the gauge
subsystem is trivial (e.g., if we “fix the gauge”).
• But there is no need to fix the gauge, as errors acting on gauge qubits
do not damage the protected information.
• Maintaining the gauge freedom reduces the number of check operators.
• Syndrome information can be extracted by measuring the gauge qubits,
and for some codes the gauge-qubit operators have lower weight than
the stabilizer generators, so it is easier to measure the gauge operators
fault tolerantly.
3  3 “Bacon-Shor code”
Shor (1995)
Bacon (2005)
check
operators:
logical
operators:
ZZ
XX
X
ZZ
XX
ZZ
XX
ZZ
corrects
one error
ZZ
XX
XX
Z
XX
ZZ
These weight-two gauge Pauli operators
commute with the logical operations, and
measuring them determines the check operators
in the stabilizer. Because only weight-two
operators are measured, error correction is
efficient and easily made fault tolerant.
3  3 “Bacon-Shor code”
Shor (1995)
Bacon (2005)
check
operators:
logical
operators:
ZZ
XX
X
ZZ
XX
ZZ
XX
ZZ
corrects
one error
ZZ
XX
XX
Z
XX
ZZ
The optimal threshold estimate is found using the
5 X 5 Bacon-Shor code (which corrects two errors):
 0  1.9 104
Aliferis, Cross (2006)
Accuracy threshold using error-detecting codes
Using Bacon-Shor codes, we obtain a lower bound on the accuracy
threshold (for adversarial local stochastic noise, nonlocal gates)
0 > 1.9  10-4
We can improve the threshold further if we can simulate gates with eff <
using gates with  > 0 .
Knill’s idea (2004):
gate to be
simulated
encoded
data in
Bell
meas.
entangled
encoded encoded
ancilla
data out
Protect the ancilla-preparation
circuit using a (recursive) errordetecting code and accept the
ancilla only if no errors are
detected. Errors occurring during
decoding are independent.
0
Prepare suitable ancillas offline
and teleport gates. Encoded error
rate eff < 0 can be achieved if
the errors in the ancilla are nearly
independent and have error rate
below e.g. 5%.
error detect
time
decode
Threshold for postselected quantum computation
We can boost the reliability by building a hierarchy
of gadgets within gadgets --- the fault-tolerant circuit
simulates the ideal circuit if the faults are sparse.
However … to assess the reliability of the
postselected circuit, we must estimate the
probability that it fails conditioned on global
acceptance --- i.e., acceptance by every error
detection in the entire circuit.
circuit fails here
Devil turns off faults elsewhere to
enhance probability of failure
conditioned on global acceptance.
To obtain a threshold theorem
for postselected computation,
we must disallow correlations in
the noise that could be tolerated
if error correction were used
instead. Otherwise, the devil
could enhance greatly the
conditional probability of failure
in one part of the circuit by
turning off faults elsewhere.
Threshold for postselected quantum computation
The bad gadgets in the postselected circuit form connected clusters, surrounded by
error detections with no faults. Thus the clusters (which typically contain just one or a
small number of bad gadgets) are isolated from one another, enabling us to relate the
probability of failure of a gadget conditioned on local acceptance (within the cluster)
to its probability of failure conditioned on global acceptance. This means that error
detection and (global) postselection improves reliability, and we can show by an
inductive step that the probability of failure in a recursive simulation gets arbitrarily
small if the noise is sufficiently weak..
bad
bad
bad
good
bad
bad
Counting the ways for error-detecting gadgets to fail, we find 0,ED
> 1.04  10-3
(Aliferis-Gottesman-Preskill 2007, Reichardt 2006). This is the best rigorously
established lower bound on the accuracy threshold so far, but still a factor of 30 below
Knill’s estimate based on simulations. (Overhead cost of the simulation can be
improved by using the error-detecting codes to correct errors at known locations).
Are black holes quantum cloners?
Reconciling the viewpoints of “inside” and “outside” observers is very
subtle, but no observer should be able to detect a violation of the principles
of quantum mechanics. Disturbingly, if Alice’s qubits are absorbed by the
black hole and re-emitted in the Hawking radiation, these qubits seem to be
in two places at once, a violation of the “no-cloning” principle. Can the
cloning be verified?
Suppose Bob recovers Alice’s
qubits, which have become
encoded in the Hawking
radiation, after Schwarschild
time t, and then jumps into the
black hole to compare notes
with Alice. If
t = O(M log M)
then Alice must send her
message to Bob within proper
time tPlanck after horizon
crossing.
singularity
Bob
Alice
How fast does information escape from a black hole?
Hayden,
Preskill
Modeling the internal dynamics by a
random local quantum circuit, we
estimate the mixing time as
t = O(M log M)
Therefore Alice’s qubits escape on
this time scale --- “black hole
complementarity” just scrapes by!
radiation
Once Alice’s k qubits are thoroughly mixed with the black hole’s internal
degrees of freedom, the information escapes quickly --- as soon as
k+constant qubits are emitted
(assuming that evaporation is
Bob decodes
already past the half-way point, so
that the black hole has become
maximally entangled with the
black
previously emitted radiation).
hole
strongly
mixing
unitary
black
hole
maximal
entanglement
Alice’s
qubits