PaperlayerView exact revision on arXiv

Source-linked AI summary

Architectures for quantum simulation showing a quantum speedup

J. Bermejo-Vega, D. Hangleiter, M. Schwarz, R. Raussendorf, J. Eisert

arXiv:1703.00466v3quant-phcond-mat.other

TL;DR

Universal quantum computing’s fault-tolerant overhead makes near-term demonstrations of computational advantage challenging, while proposed sampling schemes also face experimental hurdles. This paper presents certifiable two-dimensional simulation architectures based on non-adaptive measurement-based computation. Under stated complexity conjectures, their output distributions resist efficient classical sampling, and the prepared resource states can be certified.

  • Problem

    Universal quantum computing requires fault-tolerant protection with qubit overhead beyond available devices, while rigorous quantum-advantage demonstrations remain experimentally challenging.

    Source: §I · p. 1

  • Method

    The paper develops two-dimensional architectures combining prepared resource states, quenched local dynamics, and non-adaptive measurement, with efficient certification of the final states.

    Source: §I · pp. 1–2

  • Results

    If Conjectures 1–3 hold, no polynomial-time classical computer can sample any architecture’s output distribution to within 1/22 in ℓ1 norm.

    Source: §III · p. 3

  • Takeaways & Limitations

    The resource states can be rigorously certified with simple protocols, including inference of the quantity used in the complexity-theoretic argument.

    Source: §I · p. 2

    The classical-sampling hardness conclusion is conditional on Conjectures 1–3.

    Source: §III · p. 3

Abstract

from arXiv · show

One of the main aims in the field of quantum simulation is to achieve a quantum speedup, often referred to as "quantum computational supremacy", referring to the experimental realization of a quantum device that computationally outperforms classical computers. In this work, we show that one can devise versatile and feasible schemes of two-dimensional dynamical quantum simulators showing such a quantum speedup, building on intermediate problems involving non-adaptive measurement-based quantum computation. In each of the schemes, an initial product state is prepared, potentially involving an element of randomness as in disordered models, followed by a short-time evolution under a basic translationally invariant Hamiltonian with simple nearest-neighbor interactions and a mere sampling measurement in a fixed basis. The correctness of the final state preparation in each scheme is fully efficiently certifiable. We discuss experimental necessities and possible physical architectures, inspired by platforms of cold atoms in optical lattices and a number of others, as well as specific assumptions that enter the complexity-theoretic arguments. This work shows that benchmark settings exhibiting a quantum speedup may require little control in contrast to universal quantum computing. Thus, our proposal puts a convincing experimental demonstration of a quantum speedup within reach in the near term.

I. INTRODUCTION

Universal quantum computers promise computational advantages but require fault-tolerant protection whose qubit overhead is beyond available devices. The paper proposes simple, certifiable two-dimensional simulation schemes intended to support rigorous demonstrations of quantum speedup.

I. INTRODUCTION

  • The schemes aim to make a complexity-theoretic quantum-advantage demonstration experimentally realistic, while retaining rigorous arguments despite challenges from errors and classical descriptions of observed behavior.Earlier proposals for classically hard sampling still faced substantial experimental challenges.Source: §I · p. 1
  • Each scheme prepares a product state, evolves it for constant time under a nearest-neighbor translation-invariant Hamiltonian, then measures in a fixed basis without postselection.The prescriptions are close to those used in cold-atom optical lattices, and short evolution is expected to limit decoherence.Source: §I · pp. 1–2
  • The final resource states can be rigorously certified using simple on-site measurements and quadratically many samples, including inference of the quantity used in the complexity argument.The authors argue this certification helps support an unambiguous claim of potential quantum speedup.Source: §I · p. 2
  • The proposed experiments are predicted to challenge state-of-the-art classical computers on 50 × 50 qubit lattices, including the cost of rigorous certification.The authors note these system sizes are generally smaller than those feasible in present-day architectures.Source: §I · p. 2

II. BASIC SETUP OF THE QUANTUM SIMULATION SCHEMES

  • The basic setup uses a product-state initialization, a constant-time Ising quench on a square lattice, and X-basis measurement of primitive qubits, with optional dangling-bond qubits measurable in Z.Dangling-bond qubits appear in one scheme; a uniform basis rotation permits measuring all qubits in the same basis.Source: §II · p. 2

A. Physical desiderata and concrete schemes

The paper specifies simple two-dimensional, translationally invariant architectures and argues that their measurement distributions resist efficient classical sampling under stated complexity-theoretic conjectures. It supports the argument with a hardness reduction and numerical evidence for anti-concentration, while comparing resource requirements and assumptions with earlier proposals.

A. Physical desiderata and concrete schemes

  • The design criteria favor simple, size-independent couplings, small 2D periods, and translationally invariant final measurements; more ordered initial states require higher periodicity and finer controlled rotations.Table I compares the symmetry periods and resource requirements of the proposed architectures with a prior planar-graph proposal.Source: A. Physical desiderata and concrete… · p. 2, Table I · p. 3
  • Architecture I uses a disordered product state and Ising quench implementing edge CZ gates; II uses a state random in one lattice direction, while III adds dangling bonds and Z-basis measurements there.I and II use X-basis measurements; III uses X measurements on non-dangling qubits and adds controlled-e−iπ/8Z gates on dangling bonds.Source: A. Physical desiderata and concrete… · p. 3

III. MAIN RESULT

  • Under Conjectures 1–3, no classical computer can sample any architecture I–III within 1/22 ℓ1 error in time O(poly(n, m)).The main result states this conditional hardness for the output distributions of all three architectures.Source: §III · p. 3
  • For the specified random Ising models, approximating |Z(α,β)|2 with relative error 1/4 + o(1) is #P-hard when m ∈ O(n2).The average-case conclusion additionally relies on Conjecture 2, which equates average- and worst-case approximation hardness for the random models.Source: §III · p. 4
  • Exact simulations up to 20 logical qubits found the anti-concentration ratio quickly converges to 1/e and outcomes are Porter–Thomas distributed, supporting the O(n)-depth circuit conjecture.The paper presents Porter–Thomas behavior as a signature of chaotic Haar-random unitary processes.Source: §III · p. 4
  • The proposal’s constant physical depth is consistent with prior depth bounds because its encoding uses O(n) overhead; efficient certification protocols also exist for this work and Ref..The paper contrasts its constant-depth architecture with other non-TI proposals requiring polynomial-depth circuits, which use fewer qubits.Source: §III · p. 4

IV. EFFICIENT CERTIFICATION OF THE FINAL RESOURCE STATES

The final resource states can be rigorously certified using local measurements that bound their distance from the anticipated states and hence their output-distribution distance. The protocol is optimized to use on-site measurements and O(N^2) samples.

IV. EFFICIENT CERTIFICATION OF THE FINAL RESOURCE STATES

  • A bound on parent-Hamiltonian energy gives a fidelity witness, which bounds trace distance from the target state and therefore the measurement-distribution distance.The target resource states are ground states of gapped, frustration-free parent Hamiltonians.Source: §IV · p. 4
  • The original protocol required O(N^3 log(N)) preparations and five- or six-body measurements, which may be impractical for thousands of atoms.Its per-term estimate uses O(N^2 log N) samples.Source: §IV · p. 5
  • O(N^2) samples suffice after parallel measurement of commuting terms, reducing the original O(N^3 log(N)) certification cost.The optimized protocol also uses on-site measurements only.Source: §IV · pp. 5–6
  • Imperfect measurements can be modeled as a noise channel on the state, but achieving error bounds that scale inversely with system size remains demanding.The authors describe the required detection precision as demanding but not unrealistic.Source: §IV · p. 5
  • On-site measurements suffice to estimate parent-Hamiltonian terms, including architecture III terms decomposed into product operators with classical post-processing.The protocol estimates the relevant parent-Hamiltonian energy from local measurement outcomes.Source: §IV · pp. 5–6

V. CONCEIVABLE PHYSICAL ARCHITECTURES

The paper discusses candidate physical platforms and outlines the complexity-theoretic proof of hardness. It notes that none of the listed platforms currently realizes every required element at the necessary precision.

V. CONCEIVABLE PHYSICAL ARCHITECTURES

  • Cold-atom optical lattices are presented as the most plausible platform for anticipated system sizes, with controlled collisions enabling large-scale translationally invariant controlled-Z interactions.Other potentially useful capabilities include single-site imaging, row addressing, and preparation of disordered initial states.Source: §V · p. 6
  • Semiconductor quantum dots, polariton systems, superconducting arrays, and trapped ions are also considered, although none realizes all required elements at the necessary precision.The prescriptions are described as comparatively close to what can be done.Source: §V · p. 6

VI. PROOF OF HARDNESS RESULT

  • The hardness proof maps architectures I–III to cluster-state MBQC, establishes postselected universality, proves Lemma 2 using a parallelization technique, and applies Stockmeyer’s Theorem.Under Conjectures 2–3, efficient classical approximate sampling would imply a collapse of the Polynomial Hierarchy to its third level.Source: §VI · pp. 6–7

A. Mapping architectures I-III to cluster state MBQCs

The architectures can be recast as non-adaptive measurements on a 2D cluster state, with the measurement pattern depending on the architecture. With postselection, they can prepare states produced by homogeneous Clifford+T circuits.

A. Mapping architectures I-III to cluster state MBQCs

  • Architectures I and III map to cluster-state circuits with random {X, X−π/4} measurements, while architecture II uses random {X, X−π/8} measurements identical along columns.The mapping is computationally equivalent to the respective architecture.Source: A. Mapping architectures I-III to… · p. 7

B. Universality of architectures I-III for postselected measurement based quantum computation

  • With postselection, any architecture I–III can prepare the output of an n-qubit, depth-D homogeneous Clifford+T circuit using an O(n) × O(Dn) lattice.The prepared state includes O(n) additional qubits.Source: B. Universality of architectures I-III… · p. 7
  • The construction’s resource scaling depends on circuit depth rather than size, allowing concurrent nearest-neighbor gates to be parallelized.The preparation is exact via cluster-state MBQC under the stated postselection construction.Source: B. Universality of architectures I-III… · p. 7
  • Random measurement outcomes induce Pauli byproducts; propagating them changes a later measurement angle’s sign, explaining the required adaptive correction in the logical-circuit picture.The same argument extends from a 1D cluster edge to the full cluster by induction.Source: B. Universality of architectures I-III… · p. 8, Figure 4 · p. 9

C. #P-hardness of approximating output probabilities (proof

The proof relates approximation of an Ising partition function to output probabilities of dense, long-range IQP circuits. It also gives a linear-depth 1D nearest-neighbor implementation for those circuits.

C. #P-hardness of approximating output probabilities (proof

  • O(n^2)-size dense long-range IQP circuits can be implemented in O(n) depth on a 1D nearest-neighbor architecture, an asymptotically optimal depth scaling.The technique supports the hardness proof for approximating the associated Ising partition function; the authors note the earlier 2D result for a sparse subfamily had depth O(n log n).Source: of Lemma 2) · p. 9

A 1D linear-depth implementation of dense IQP circuits

Dense IQP circuits can be implemented with linear depth on a 1D nearest-neighbor line, and the paper uses this result in a hardness argument for its architectures. The sampling-hardness conclusion depends on complexity assumptions and anti-concentration.

A 1D linear-depth implementation of dense IQP circuits

  • Dense n-qubit IQP circuits with long-range interactions admit a Θ(n)-depth implementation using 1D nearest-neighbor gates.Alternating two-qubit gates and SWAP layers route every pair through a crossing, where its IQP gate is applied.Source: A 1D linear-depth implementation of… · p. 9

Proof of Lemma 2

  • Dense IQP output-probability hardness transfers to architectures I–III by encoding the circuits on lattices with n × O(n²) qubits.The reduction uses the circuit implementation lemma together with the architecture mappings; approximating the relevant conditional probabilities is #P-hard up to relative error 1/4 + o(1).Source: Proof of Lemma 2 · p. 10

D. Hardness argument (proof of Theorem 1)

  • Under Conjectures 1–3, a classical sampler within constant ℓ1 error would imply a polynomial-hierarchy collapse, contradicting Conjecture 1.The argument combines Stockmeyer’s theorem with average-case hardness and anti-concentration; numerical evidence reports near-1/e anti-concentration for n ≥ 9.Source: D. Hardness argument (proof of Theorem… · pp. 10–11

VII. CONCLUSION

The paper establishes simple quantum-simulation schemes with a complexity-theoretic case for superpolynomial speedup, while identifying experimental realization and further complexity results as next steps.

VII. CONCLUSION

  • The proposed simple quantum-simulation schemes are argued to exhibit superpolynomial quantum speedup in a complexity-theoretic sense.The authors describe the schemes as a step toward quantum devices outperforming classical supercomputers, not yet as experimentally realizable blueprints.Source: §VII · p. 11
  • Detailed settings for cold atoms or trapped ions remain to be explored, although the proposed schemes resemble steps already taken experimentally.The authors point to little local control and comparatively short coherence times as relevant features.Source: §VII · p. 11
  • The authors identify further complexity-theoretic results on intermediate problems as needed to capture the potential of non-universal quantum devices.Source: §VII · p. 11

Appendix A: Full Hamiltonian (2)

The appendices specify Hamiltonian and partition-function mappings, then present numerical evidence that the associated random circuits anti-concentrate and approach Porter–Thomas output statistics.

Appendix A: Full Hamiltonian (2)

  • Architecture III adds dangling-bond couplings that implement CT gates, while architectures I–II omit that Hamiltonian term.The primitive-lattice coupling degree is four in the bulk, two at corners, and three elsewhere on edges; dangling-bond degree is one in architecture III.Source: Appendix A · p. 14

Appendix B: Mapping output probabilities to Ising partition functions

  • The appendix maps output probabilities through a random Ising-model partition function, with angles defined from measurement outcomes and the architecture’s chosen θ.It derives the stated probability relation by applying the Hamiltonian formula and squaring.Source: Appendix B · p. 14

Appendix C: Numerical evidence for anti-concentration of the output distribution

  • For circuits associated with n × n and n × n² lattices, the anti-concentration fraction approaches 1/e with decreasing variance across instances.The simulations used 100 random instances per size and evaluated the fraction of output probabilities exceeding the threshold.Source: Appendix C · pp. 14–15, Figure 7 · p. 16
  • As qubit count increases, the empirical output-probability distributions approach the Porter–Thomas distribution.The appendix reports this convergence using total variation distance and relates the observed 1/e fraction to the exponential distribution.Source: Appendix C · p. 15

Appendix D: #P-hardness from n × O(n) lattices

Two modifications to architectures I–II yield #P-hardness on lattices with n × O(n) qubits by enabling postselected implementations of hard IQP circuits. The construction changes selected input states and measurement bases while preserving the basic layout.

Appendix D: #P-hardness from n × O(n) lattices

  • The modifications change even-row preparations: |0⟩ sites become invisible to the Ising evolution, while |−i⟩ preparation with X measurement is equivalent to |+⟩ preparation with Y measurement.Architecture I uses fully disordered preparation; architecture II uses preparation translation-invariant in one direction with period at most four.Source: Appendix D · pp. 16–17
  • Modified architecture I simulates arbitrary nearest-neighbor Clifford+T circuits by postselection on a (2k − 1) × (2k − 1) lattice, with constant overhead for the hard IQP circuits.Source: Appendix D · pp. 16–17
  • Modified architecture II also yields an efficient, exact postselected implementation of the desired IQP circuits.Its byproduct operators permit breaking the TI(2,∞) symmetry to implement non-translation-invariant nearest-neighbor Clifford+T circuits.Source: Appendix D · pp. 17–18

Appendix E: Certification protocol

The appendix develops a certification protocol with lower sample complexity and on-site measurements, then constructs parent Hamiltonians for the architecture states. The third architecture's Hamiltonian has 6-local terms, with lower locality at the boundary.

Appendix E: Certification protocol

  • The protocol reduces certification sample complexity from O(N^3 log N) to O(N^2) using parallel local measurements and classical post-processing.It also uses on-site single-qubit observables rather than few-body Hamiltonian terms and applies to arbitrary non-degenerate gapped local Hamiltonians.Source: Appendix E · p. 18

1. Parent Hamiltonians

  • For architectures I–III, the pre-measurement state is obtained by applying Uβ and then the local quench unitary U to the initial product state.The appendix derives non-degenerate gapped local parent Hamiltonians for these states.Source: §1 · p. 18
  • Architecture III's parent Hamiltonian has 6-local terms, except at the boundary where their locality is reduced.Its construction distinguishes square primitive-sublattice qubits from dangling-bond qubits, with couplings Ji,j = π/4 and π/16, respectively.Source: §1 · pp. 18–19

2. Energy estimation of G-local Hamiltonians

The section develops parallel energy estimation through decompositions of local Hamiltonians into groups of jointly measurable terms. It establishes general decomposition bounds and applies tailored decompositions to the three architectures.

2. Energy estimation of G-local Hamiltonians

  • A (κ, α, τ) decomposition groups a Hamiltonian into a small sum of terms whose energy distributions can be sampled with parallel τ-body measurements and classical post-processing.Parallel measurement circuits are enabled by decomposing the Hamiltonian into commuting terms; the section uses this structure for energy estimation.Source: §2 · p. 19
  • Any G-local Hamiltonian admits a (κ, α, τ) decomposition, supporting parallel energy estimation by measuring grouped terms and combining outcomes classically.The section frames the estimator around energy measurements of each grouped Hamiltonian term.Source: §2 · pp. 19–20
  • For constant-degree interaction graphs, local Hamiltonians admit decompositions with bounded measurement groups, and any such decomposition can be converted to on-site measurements.Lemma 9 bounds κ by χ(G(2)) ≤ τ^2 + 1 and gives an on-site (κ4τ, α, 1) decomposition; constant-degree graphs model geometrically constrained systems.Source: §2 · pp. 19–20
  • Lemma 9's bounds need not be tight for commuting Hamiltonians: fully connected Ising terms can be measured directly with single-shot on-site Zi measurements.The section also reports tighter bounds for the Hamiltonians in architectures I–III.Source: §2 · p. 20
  • The three architecture Hamiltonians admit tailored decompositions whose grouped terms retain architecture-specific symmetries.HI uses DO symmetry, HII uses TI(1,∞) symmetry, and HIII uses TI(…); the supplied passage does not complete the final symmetry notation.Source: §2 · p. 20
  • For HI and HII, a two-coloring splits Hamiltonian terms into even and odd groups with κ = 2 and τ = 1; HIII obtains a (2, 5/9, 2) decomposition and a (32, 5/9, 1) on-site decomposition.The construction measures non-overlapping terms in parallel, and the resulting grouped Hamiltonians inherit their parent Hamiltonians' symmetries.Source: §2 · p. 21

3. Certification protocol

The protocol certifies whether a prepared state meets a fidelity threshold by estimating its energy relative to a known gapped Hamiltonian. Under stated bounds, it supports efficient certification of the final states in architectures I–III when they are sufficiently close to their targets.

3. Certification protocol

  • A quadratic-time weak-membership protocol certifies ground states of non-degenerate gapped local Hamiltonians and applies to architectures I–III.The protocol is a parallelized version of the approach in Ref..Source: §3 · p. 21
  • The test rejects prepared states with fidelity at or below FT and accepts states at least FT + δ with high probability.Weak membership is defined for a classical target-state description and copies of the prepared state.Source: §3 · p. 21
  • The protocol estimates grouped-term energies from repeated measurements, derives a lower bound on fidelity, and accepts or rejects against the chosen threshold.Each Hi is measured using a single-shot circuit of τ-local observables and classical post-processing.Source: §3 · p. 21
  • With constant-bounded ground-state energy, inverse gap, and interaction strength, the protocol is a weak-membership test; architectures I–III are certifiable when their fidelity distance from the target is at least 1/N close.The architecture conclusion uses parent Hamiltonians with norm scaling as N and gap larger than a constant.Source: §3 · p. 21

Appendix F: Alternative weaker forms of Conjectures 1-2

The appendix states weaker sufficient forms of the two conjectures used in the main result. Under the weaker second conjecture, the first is unnecessary for the proof.

Appendix F: Alternative weaker forms of Conjectures 1-2

  • The proof needs only that the Polynomial Hierarchy does not collapse to its third level, rather than requiring it to be infinite.This is the weaker form of Conjecture 1 described in the appendix.Source: Appendix F · p. 21
  • Conjecture 2 can be weakened to require that approximating Ising partition functions is not in BPP^NP, rather than requiring average-case #P-hardness.If this weaker form holds, Conjecture 1 is not needed in the proof of Theorem 1; the appendix also favors relative-error over additive-error formulations.Source: Appendix F · p. 22

Related papers

Loading 1703.00466v3…