This afternoon at @InHenriPoincare Quantum Advantage week: @queenofquanta and Dominik Hangleiter on “Quantum Simulation architectures showing a quantum speedup”
http;//arxiv.org/abs/1703.00466 and
arxiv.org/abs/1706.03786
(with @martin_schwarz, Robert Raussendorf and @jenseisert
http;//arxiv.org/abs/1703.00466 and
arxiv.org/abs/1706.03786
(with @martin_schwarz, Robert Raussendorf and @jenseisert
.@queenofquanta ’s motivations :
I. a near term experimental proof of quantum speedup
II. Prove complexity-theoretic hardness of analog quantum-simulation #LTQI
I. a near term experimental proof of quantum speedup
II. Prove complexity-theoretic hardness of analog quantum-simulation #LTQI
.@queenofquanta : Existing synamical simulator (e.g. 10⁴–10⁵ atoms in lattices) can’t be simulated with state-of-the-art tensor netwoek algorithme (e.g. DMRG). Are these good enough ?
#LTQI
#LTQI
:
Quantum simulation:
☺ Easy scaling
☹ No hardness proof
Simplest intractable circuits (IQP, boson sampling, Ising, random circuits)
☺HArdness proofs
☹Challenging scaling
☹For ising: Hamiltonian period=56 !
☹Verification inefficient or expensive
#LTQI
Quantum simulation:
☺ Easy scaling
☹ No hardness proof
Simplest intractable circuits (IQP, boson sampling, Ising, random circuits)
☺HArdness proofs
☹Challenging scaling
☹For ising: Hamiltonian period=56 !
☹Verification inefficient or expensive
#LTQI
.@queenofquanta 's result: a simple Hamiltonian which can't be simulated given some conjectures #LTQI 
.@queenofquanta’s 1st scheme:
1.Prepare N qubits on a n×m square lattice in |0>+exp(iβ)|1> state, is random β∈{0,π/4}
2. Quench to H=∑π/4 Z_i Z_j + ∑π/4 Z_i and evolve under U=exp(iH)
3. Measure everything in X basis
#LTQI
1.Prepare N qubits on a n×m square lattice in |0>+exp(iβ)|1> state, is random β∈{0,π/4}
2. Quench to H=∑π/4 Z_i Z_j + ∑π/4 Z_i and evolve under U=exp(iH)
3. Measure everything in X basis
#LTQI
.@queenofquanta :
Scheme equivalent to cluster state + {X, X+Y} measurement.
This allows to use standard MBQC tools to show it encodes universal random translation invariant schemes of quantum computation.
⇒ output probabilities ♯P hard to simulate upto ∼¼ rel. error
#LTQI
Scheme equivalent to cluster state + {X, X+Y} measurement.
This allows to use standard MBQC tools to show it encodes universal random translation invariant schemes of quantum computation.
⇒ output probabilities ♯P hard to simulate upto ∼¼ rel. error
#LTQI
.@queenofquanta : Actually, the output distribution are closely related to the partition function of the Ising model
#LTQI
#LTQI
.@queenofquanta’s 3 “plausible complexity theoretic conjectures”
C1: Polynomial hierarchy (PH) is ∞
C2 (Avrg complex.): average complexity of approximating |Z^(α,β)|² for random Ising model = worst case
C3 (Anticoncentration): Const. fraction 1/e of output probabilities >2⁻ⁿ
C1: Polynomial hierarchy (PH) is ∞
C2 (Avrg complex.): average complexity of approximating |Z^(α,β)|² for random Ising model = worst case
C3 (Anticoncentration): Const. fraction 1/e of output probabilities >2⁻ⁿ
.@queenofquanta also can certify the schem, using O(N) 1-2 qubit measurements to estimate the fidelity of
the scheme
#LTQI
the scheme
#LTQI
.@queenofquanta : Link with th PH: the existence of a simulation algorithm implies the existence of a “probability estimator” in PH level 3.
P^♯P , PostBQP are above PH
⇒ in that case PostBQP=PH₃ and PH collapses
#LTQI
P^♯P , PostBQP are above PH
⇒ in that case PostBQP=PH₃ and PH collapses
#LTQI
.@queenofquanta : arXiv:1706.03786 ( arxiv.org/abs/1706.03786 ) shows a variant where C3(Anticoncentration) is not needed #LTQI
