Transcript Quantum Computation and Statistical Physics

Exactly solvable models of
statistical physics: applications for
quantum computing
Sergey Bravyi, IBM Watson Center
Robert Raussendorf, Perimeter Institute
Perugia July 16, 2007
Outline
• Measurement-based quantum computation (MQC)
• Classical simulation of MQC
• Kitaev’s toric code model and the planar code states
• Reduction from MQC with the planar code states to the Ising
model on a planar graph (doubling trick)
• Barahona’s Pfaffian formula for planar and
non-planar graphs
Measurement-based QC: resource state
• Step 1:
2: prepare
measurenqubits
qubit resource
of the resource
state state one by
oneThe
using
projective
measurement.
resource
statenon-destructive
is algorithm-independent
The measurement pattern is algorithm specific
Example: cluster state (universal resource)
Measurement-based QC: measurement pattern
• Step 2 (algorithm specific):
for j=1 to n do
Measure qubit q(j) projectively using orthonormal basis
The outcome is a random bit
A choice of
and q(j) may depend on the outcomes
of all earlier measurements
end do
Measurement-based QC:
1
4
7
2
5
8
3
6
9
Measurement-based QC
• Step 3: extract the answer by classical postprocessing
of the random bit string
Theorem (Briegel & Raussendorf 01)
Any problem that can be solved on a quantum computer in
polynomial time can be solved by MQC with the cluster state
in polynomial time.
Advantages of MQC:
• Entangling operations = nearest neighbors Ising interactions
• Noisy resource state can be efficiently purified
• Can be made fault-tolerant with very high threshold in 3D
Classical simulation of MQC
Output of MQC is a random bit string
with a probability distribution
Classical simulator must be able to reproduce statistics
of the measurement outcomes
Definition:
MQC is classically simulatible if there exists a classical algorithm
with a running time poly(n) that computes conditional probabilities
For which resource states MQC is classically simulatable?
• Graph states with a treewidth
(Markov & Shi 05).
Includes 1D and quasi-1D cluster states
• States with a entanglement width
(Briegel, Vidal, et al. 06)
Includes matrix product states
• Our result: planar code states and surface code states of
genus
. These states have treewidth and
entanglement width
The planar code state: planar version of Kitaev’s toric code
Plaquette operators:
Vertex operators:
The planar code state is uniquely defined by equations
Hamiltonian:
The planar code state is the unique ground state of H
Planar code state = superposition of 1-cycles
A basis vector = subset of edges labeled by ‘1’ = 1-chain
is a set of 1-cycles on the lattice (a linear space mod 2)
1-cycle is a 1-chain that has even number of edges incident
to every vertex
Duality between 1-cycles and cuts
1-cycle
cut
of cuts
and
1-cycles
are dual
to each
other:
A Linear
1-chainspaces
y is called
a cut
iff one
can color
the set
of vertices
using blue and green colors such that every edge of y has blue
and green endpoints
Let
be a set of all cuts on the lattice (a linear space mod 2)
Duality between 1-cycles and cuts:
Hadamard gate:
Conclusion: the planar code state is a uniform superposition
of all cuts on the lattice (after a local change of basis)
The states
and
are equivalent for MQC
Computing probabilities for complete measurements:
- Probability of the outcome
for a complete measurement
(every qubit is measured)
Introduce local “temperature” :
a cut
= Ising spin
Computing probabilities for complete measurements:
Barahona (1982):
on a planar graph can be
computed in time poly(n) for arbitrary (complex) weights
2D cluster state: computing the probabilities for complete
measurements is quantum-NP hard
Corollary: the planar code state can not be converted to the 2D cluster
state by performing one-qubit measurements on a subset of qubits
(even with exp. small success probability)
Computing conditional probabilities
Conclusion: we need to compute probabilities of
incomplete measurements
E is the subset of measured qubits and
Incomplete overlap
Computing conditional probabilities
Measured qubits
Unmeasured qubits
E
Relative 1-cycle
Boundary
Given
a 1-chain
a boundary such
as that
a set of vertices
A
relative
1-cyclexisdefine
a 1-chain
that are incident to odd number of edges from x
= set of relative 1-cycles
Computing conditional probabilities
Measured qubits
Unmeasured qubits
E
For any
Then
define a relative planar code state
Computing conditional probabilities: doubling trick
We need to compute an incomplete overlap:
Key idea: the state
is the planar
code state for a planar graph obtained from two copies of E
by identifying vertices of
Computing conditional probabilities: doubling trick
Now we can efficiently compute probability of any outcome
for incomplete measurement:
Disclaimer: the doubling trick works only if the set of
measured qubits E is simply connected (no holes)
Intermediate result: MQC with the planar code state is
classically simulatable if at every step of MQC the set
of measured qubits is simply connected
Extension to arbitrary measurement patterns:
Let x be a relative 1-cycle on E
obtained by restricting a 1-cycle
on the complete lattice to E
has even number of vertices
on every connected part of
If
E = measured qubits
has more than one connected component,
Extension to arbitrary measurement patterns:
Suppose the doubled graph
a surface of genus g. Then
can be drawn on
is the Lagrangian subspace
Barahona’s reduction to the dimer model:
G can be arbitrary graph
The graph
is obtained from
by
adding O(n) vertices and edges
= set of dimer configurations
Dimer configuration
Pfaffian formula for planar graphs
is Kasteleyn orientation (a
any plaquette is 1)
flux through
Extension to arbitrary measurement patterns:
Applying Barahona’s construction we get
is a fixed dimer configuration
is a 1-cycle
Summation over spin structures
Definition:
Properties:
Pfaffian formula for non-planar graphs
(Cimasoni and Reshetikhin 07)
is efficiently computable
is Kasteleyn orientation associated with
a spin structure f
Extension to arbitrary measurement patterns:
The sum contains
terms
g = genus of the doubled graph obtained by gluing
together two copies of E
can be efficiently computed if
Simulating quantum computation on a classical computer:
do we already know all cases when it is possible ?
Quadratically Signed Weight
Enumerators, Knill & Laflamme
Evaluation of Jones
polynomials and TQFT
invariants, Freedman et al.
Contraction of tensor
networks, Markov & Shi
Adiabatic evolution algorithm
(simulated annealing), Farhi et al.
Quantum walks (diffusion),
Ambainis et al.
Simulation of “fermionic linear optics”
Valiant, DiVincenzo et al.
Main goal: find a family of quantum algorithms that can be efficiently simulated
classically via a mapping to exactly solvable models of statistical physics (we shall
consider the Ising model on planar and “almost planar” graphs).