Transcript Superactivation of the Zero-Error Capacity of a Quantum

Preparing Topological States on a
Quantum Computer
Martin Schwarz(1), Kristan Temme(1),
Frank Verstraete(1)
Toby Cubitt(2), David Perez-Garcia(2)
(1)University
of Vienna
(2)Complutense University, Madrid
STV, Phys. Rev. Lett. 108, 110502 (2012)
STVCP-G, (QIP 2012; paper in preparation)
Talk Outline
• Crash course on PEPS
• Growing PEPS in your Back Garden
• The Trouble with Tribbles Topological States
• Crash course on G-injective PEPS
• Growing Topological Quantum States
Crash Course on PEPS!
• Projected Entangled Pair State
Crash Course on PEPS!
• Projected Entangled Pair State
Obtain PEPS
by applying maps
entangled pairs
to maximally
Crash Course on PEPS!
• Parent Hamiltonian
2-local Hamiltonian
ground state.
• Injectivity
PEPS is “injective” if
with PEPS as
are left-invertible
(perhaps only after blocking together sites)
• Uniqueness
An injective PEPS is the unique ground state of its
parent Hamiltonian
Are PEPS Physical?
• PEPS accurately approximate ground states of gapped
local Hamiltonians.
– Proven in 1D (= MPS) [Hastings 2007]
– Conjectured for higher dim (analytic & numerical
evidence)
• PEPS preparation would be an extremely powerful
computational resource:
– as powerful as contracting tensor networks
– PP-complete (for general PEPS as classical input)
 Cannot efficiently prepare all PEPS, even using a
universal quantum computer (unless BQP = PP!)
Are PEPS Physical?
• Is it possible to prepare PEPS on a quantum computer
(under mild conditions on PEPS)?
• Which subclass of PEPS are physical?
[V, Wolf, P-G, Cirac 2006]
Talk Outline
• Crash course on PEPS
• Growing PEPS in your Back Garden
• The Trouble with Tribbles Topological States
• Crash course on G-injective PEPS
• Growing Topological Quantum States
Growing PEPS in your Back Garden
•
Start with maximally entangled pairs at every edge, and
convert this into target PEPS.
Growing PEPS in your Back Garden
•
Start with maximally entangled pairs at every edge, and
convert this into target PEPS.
•
Sequence of partial PEPS |ti are ground states of
sequence of parent Hamiltonians Ht :
Growing PEPS in your Back Garden
•
Start with maximally entangled pairs at every edge, and
convert this into target PEPS.
•
Sequence of partial PEPS |ti are ground states of
sequence of parent Hamiltonians Ht :
Growing PEPS in your Back Garden
•
Start with maximally entangled pairs at every edge, and
convert this into target PEPS.
•
Sequence of partial PEPS |ti are ground states of
sequence of parent Hamiltonians Ht :
Growing PEPS in your Back Garden
•
Start with maximally entangled pairs at every edge, and
convert this into target PEPS.
•
Sequence of partial PEPS |ti are ground states of
sequence of parent Hamiltonians Ht :
Growing PEPS in your Back Garden
•
Start with maximally entangled pairs at every edge, and
convert this into target PEPS.
•
Sequence of partial PEPS |ti are ground states of
sequence of parent Hamiltonians Ht :
Growing PEPS in your Back Garden
•
Start with maximally entangled pairs at every edge, and
convert this into target PEPS.
•
Sequence of partial PEPS |ti are ground states of
sequence of parent Hamiltonians Ht :
Growing PEPS in your Back Garden
Algorithm
1. t = 0
2. Prepare max-entangled pairs (= ground state of H0)
3. Grow the PEPS vertex by vertex:
1. Project onto ground state of Ht+1
2. t = t + 1
Growing PEPS in your Back Garden
Algorithm
1. t = 0
2. Prepare max-entangled pairs (= ground state of H0)
3. Grow the PEPS vertex by vertex:
1. Project onto ground state of Ht+1
2. t = t + 1
Growing PEPS in your Back Garden
Algorithm
1. t = 0
2. Prepare max-entangled pairs (= ground state of H0)
3. Grow the PEPS vertex by vertex:
1. Project onto ground state of Ht+1
2. t = t + 1
Growing PEPS in your Back Garden
Algorithm
1. t = 0
2. Prepare max-entangled pairs (= ground state of H0)
3. Grow the PEPS vertex by vertex:
1. Project onto ground state of Ht+1
2. t = t + 1
Growing PEPS in your Back Garden
Algorithm
1. t = 0
2. Prepare max-entangled pairs (= ground state of H0)
3. Grow the PEPS vertex by vertex:
1. Project onto ground state of Ht+1
2. t = t + 1
Growing PEPS in your Back Garden
Algorithm
1. t = 0
2. Prepare max-entangled pairs (= ground state of H0)
3. Grow the PEPS vertex by vertex:
1. Project onto ground state of Ht+1
2. t = t + 1
Growing PEPS in your Back Garden
Algorithm
1. t = 0
2. Prepare max-entangled pairs (= ground state of H0)
3. Grow the PEPS vertex by vertex:
1. Project onto ground state of Ht+1
2. t = t + 1
Growing PEPS in your Back Garden
Algorithm
1. t = 0
2. Prepare max-entangled pairs (= ground state of H0)
3. Grow the PEPS vertex by vertex:
1. Project onto ground state of Ht+1
2. t = t + 1
Growing PEPS in your Back Garden
Algorithm
1. t = 0
2. Prepare max-entangled pairs (= ground state of H0)
3. Grow the PEPS vertex by vertex:
1. Project onto ground state of Ht+1
2. t = t + 1
Growing PEPS in your Back Garden
Algorithm
1. t = 0
2. Prepare max-entangled pairs (= ground state of H0)
3. Grow the PEPS vertex by vertex:
1. Project onto ground state of Ht+1
2. t = t + 1
Growing PEPS in your Back Garden
Algorithm
 1. t = 0
 2. Prepare max-entangled pairs (= ground state of H0)
3. Grow the PEPS vertex by vertex:
??
1. Project onto ground state of Ht+1
2. t = t + 1

• How can we implement the measurement
,
when the ground state P0 is a complex, many-body state
which we don’t know how to prepare?
• Even if we could implement this measurement, we
cannot choose the outcome, so how can we
deterministically project onto P0??
Measuring the Ground State
• How can we implement the measurement
?
! Use quantum phase estimation:
QPE
measure if energy is <  or not
local Hamiltonian ) Hamiltonian simulation )
Measuring the Ground State
• How can we implement the measurement
?
! Use quantum phase estimation:
QPE
measure if energy is <  or not
• Condition 1: Spectral gap (Ht) > 1/poly
Projecting onto the Ground State
• How can we deterministically project from P0(t) to P0(t+1)?
! Use Marriot-Watrous measurement rewinding trick:
0
0
0
0
P0(t) =
1
P0
0
(t+1)
=
c
-s
s
c
0
0
0
0
“Jordan’s lemma” (or “CS decomposition”)
• Start in Jordan block of P0(t) containing |ti
• Measure {P0(t+1),P0(t+1)?} ! stay in same Jordan block
 Condition 2: Unique ground state (= injective PEPS)
Projecting onto the Ground State
• How can we deterministically project from P0(t) to P0(t+1)?
! Use Marriot-Watrous measurement rewinding trick:
Projecting onto the Ground State
• How can we deterministically project from P0(t) to P0(t+1)?
! Use Marriot-Watrous measurement rewinding trick:
• Measure {P0(t+1),P0(t+1)?}
Projecting onto the Ground State
• How can we deterministically project from P0(t) to P0(t+1)?
! Use Marriot-Watrous measurement rewinding trick:
c
• Measure {P0(t+1),P0(t+1)?}
• Outcome P0(t+1) ) done
Projecting onto the Ground State
• How can we deterministically project from P0(t) to P0(t+1)?
! Use Marriot-Watrous measurement rewinding trick:
c
s
• Measure {P0(t+1),P0(t+1)?}
• Outcome P0(t+1) ) done
• Outcome P0(t+1) ? …
Projecting onto the Ground State
• How can we deterministically project from P0(t) to P0(t+1)?
! Use Marriot-Watrous measurement rewinding trick:
c
s
• Measure {P0(t+1),P0(t+1)?}
• Outcome P0(t+1) ) done
• Outcome P0(t+1) ?
) rewind by measuring {P0(t),P0(t)?}
Projecting onto the Ground State
• How can we deterministically project from P0(t) to P0(t+1)?
! Use Marriot-Watrous measurement rewinding trick:
c
s
• Measure {P0(t+1),P0(t+1)?}
• Outcome P0(t+1) ) done
• Outcome P0(t+1) ?
) go back by measuring {P0(t),P0(t)?}
Projecting onto the Ground State
• How can we deterministically project from P0(t) to P0(t+1)?
! Use Marriot-Watrous measurement rewinding trick:
c
s
• Measure {P0(t+1),P0(t+1)?}
• Outcome P0(t+1) ) done
• Outcome P0(t+1) ?
) go back by measuring {P0(t),P0(t)?}
Projecting onto the Ground State
• How can we deterministically project from P0(t) to P0(t+1)?
! Use Marriot-Watrous measurement rewinding trick:
c
c
s
c
• Measure {P0(t+1),P0(t+1)?}
• Outcome P0(t+1) ) done
• Outcome P0(t+1) ?
) go back by measuring {P0(t),P0(t)?}
Projecting onto the Ground State
• How can we deterministically project from P0(t) to P0(t+1)?
! Use Marriot-Watrous measurement rewinding trick:
c
c
s
s
c
s
• Measure {P0(t+1),P0(t+1)?}
• Outcome P0(t+1) ) done
• Outcome P0(t+1) ?
) go back by measuring {P0(t),P0(t)?}
Projecting onto the Ground State
• How can we deterministically project from P0(t) to P0(t+1)?
! Use Marriot-Watrous measurement rewinding trick:
c
c
s
s
c
s
• Measure {P0(t+1),P0(t+1)?}
• Outcome P0(t+1) ) done
• Outcome P0(t+1) ?
) go back by measuring {P0(t),P0(t)?}
Projecting onto the Ground State
• How can we deterministically project from P0(t) to P0(t+1)?
! Use Marriot-Watrous measurement rewinding trick:
c
c
s
c
s
s
c
s
c
s
• Measure {P0(t+1),P0(t+1)?}
• Outcome P0(t+1) ) done
• Outcome P0(t+1) ?
) go back by measuring {P0(t),P0(t)?}
Projecting onto the Ground State
• How can we deterministically project from P0(t) to P0(t+1)?
! Use Marriot-Watrous measurement rewinding trick:
c
c
s
c
s
s
c
s
c
s
•
• Lemma:
)
exp fast
where
• Condition 3: Condition number (At ) > 1/poly
Growing PEPS in your Back Garden
Algorithm:
1. t = 0
2. Prepare max-entangled pairs (= ground state of H0)
3. Grow the PEPS vertex by vertex:
1. Project onto ground state of Ht+1
2. t = t + 1
Growing PEPS in your Back Garden
Algorithm:
1. t = 0
2. Prepare max-entangled pairs (= ground state of H0)
3. Grow the PEPS vertex by vertex:
1. Measure {P0(t+1),P0(t+1)?}
2. While outcome  P0(t)
1. Measure {P0(t),P0(t)?}
2. Measure {P0(t+1),P0(t+1)?}
3. t = t + 1
Are PEPS Physical?
• Is it possible to prepare PEPS on a quantum computer
(under mild conditions on PEPS)?
• Which subclass of PEPS are physical?
Condition 1: Spectral gap (Ht) > 1/poly
Condition 2: Unique ground state (= injective PEPS)
Condition 3: Condition number (At ) > 1/poly
Run-time:
Rules out all topological quantum states! 
Talk Outline
• Crash course on PEPS
• Growing PEPS in your Back Garden
• The Trouble with Tribbles Topological States
• Crash course on G-injective PEPS
• Growing Topological Quantum States
Projecting onto the Ground State
0
0
0
0
(t)
P0 =
1
P0
0
(t+1)
=
1
0
c1 s 1
-s1 c1
c2 s2
-s2 c2
“Jordan’s lemma” (or “CS decomposition”)
• State could be spread over any of the Jordan blocks of
P0(t) containing |t(k)i.
• Probability of measuring P0(t+1) can be 0.
Projecting onto the Ground State
• Probability of measuring P0(t+1) could be 0.
Projecting onto the Ground State
• Probability of measuring P0(t+1) could be 0.
s
Projecting onto the Ground State
• Probability of measuring P0(t+1) could be 0.
s
Projecting onto the Ground State
• Probability of measuring P0(t+1) could be 0.
Projecting onto the Ground State
• Probability of measuring P0(t+1) could be 0.
 We can get stuck! (never make it to
)
Talk Outline
• Crash course on PEPS
• Growing PEPS in your Back Garden
• The Trouble with Tribbles Topological States
• Crash course on G-injective PEPS
• Growing Topological Quantum States
Crash Course on G-injective PEPS!
[Schuch, Cirac, P-G 2010]
• G-injective PEPS
PEPS maps
left-invertible on invariant subspace of
symmetry group G.
• G-isometric PEPS
G-injective PEPS where
subspace.
= projector onto G-invariant
• Topological state
Degenerate ground state of Hamiltonian whose ground
states cannot be distinguished by local observables.
• G-injective PEPS = Topological state
Parent Hamiltonian has topologically degenerate ground
states (degeneracy = # “pair conjugacy classes” of G)
Crash Course on G-injective PEPS!
[Schuch, Cirac, P-G 2010]
• Many important topological quantum states are
G-injective PEPS:
• Kitaev’s toric code
• Quantum double models
• Resonant valence bond states
[Schuch, Poilblanc, Cirac, P-G, arXiv:1203.4816]
• …
Talk Outline
• Crash course on PEPS
• Growing PEPS in your Back Garden
• The Trouble with Tribbles Topological States
• Crash course on G-injective PEPS
• Growing Topological Quantum States
Growing Topological Quantum States
• Recall key Lemma relating probability c of successful
measurement to condition number:
where
• A(t) no longer invertible (only invertible on G-invariant
subspace) ) zero eigenvalues )  = 1 ) c = 0 (bad!)
• However, G-injectivity ) restriction of A(t) to G-invariant
subspace is invertible.
• How can we exploit this?
Growing Topological Quantum States
Idea:
• Get into the G-invariant subspace.
• Stay there!
Algorithm
1. t = 0
2. Prepare max-entangled pairs (ground state of H0)
3. Grow the PEPS vertex by vertex:
1. Project onto ground state of Ht+1
2. t = t + 1
Growing Topological Quantum States
Idea:
• Get into the G-invariant subspace.
• Stay there!
Algorithm
1. t = 0
2. Prepare G-isometric PEPS (ground state of H0)
3. Deform vertex by vertex to G-injective PEPS:
1. Project onto ground state of Ht+1
2. t = t + 1
For (suitable representation of) trivial group G = 1,
G-isometric PEPS = maximally entangled pairs
! recover original algorithm
Growing Topological Quantum States
Algorithm
1. t = 0
2. Prepare G-isometric PEPS (ground state of H0)
3. Deform vertex by vertex to G-injective PEPS:
1. Project onto ground state of Ht+1
2. t = t + 1
G-isometric PEPS = quantum double models
! algorithms known for preparing these exactly
[e.g. Aguado, Vidal, PRL 100, 070404 (2008)]
Growing Topological Quantum States
Algorithm
1. t = 0
2. Prepare G-isometric PEPS (ground state of H0)
3. Deform vertex by vertex to G-injective PEPS:
1. Project onto ground state of Ht+1
2. t = t + 1
Key Lemma: If initial state is already in G-invariant
subspace, prob. successful measurement
 is condition number restricted to G-invariant subspace
! Marriot-Watrous measurement rewinding trick works!
Conclusions
• Injective PEPS can be prepared efficiently on a quantum
computer, under the following conditions:
– Sequence of parent Hamiltonians is gapped
– PEPS maps A(v) are well-conditioned
• G-injective PEPS can be prepared efficiently under
similar conditions
 includes many important topological states
• Alternatives to Marriot-Watrous trick:
– Jagged adiabatic thm? [Aharonov, Ta-Shma, 2007]
(Worse run-time, may not work for G-injective case)
– Quantum rejection sampling ! quadratic speed-up
[Ozols, Roetteler, Roland, 2011]