Pith. sign in

REVIEW 2 major objections 4 minor 75 references

Closing gaps of a quantum advantage with short-time Hamiltonian dynamics

T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Constant-time Ising Hamiltonian simulation is an approximate 2-design with #P-hard output probabilities.

desk verdict Genuine progress on anticoncentration via 2-designs, but the paper overstates its average-case hardness result: the proven theorem is about a truncated non-unitary perturbation, not the architecture's own output probabilities. read the letter →

arxiv 1908.08069 v2 pith:EBSF7VBF submitted 2019-08-21 quant-ph

Jonas Haferkamp , Dominik Hangleiter , Adam Bouland , Bill Fefferman , Jens Eisert , Juani Bermejo-Vega This is my paper · ORCID
classification quant-ph MSC 81P6868Q17
keywords quantumadvantageanticoncentrationunitary2-designsHamiltoniansimulationaverage-casehardness#P-hardnessspectralgaptranslation-invariantcircuits
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper proves two properties that were previously conjectured for a near-term quantum advantage scheme: the output distributions of a constant-time, translation-invariant Ising Hamiltonian evolution on a 2D lattice anticoncentrate, and exactly evaluating those output probabilities is #P-hard for most instances. The first property is obtained in a stronger form: on an $n\times m$ lattice with $m\in O(4n+\log(1/\varepsilon))$, measuring the first $m-1$ columns in the $X$ basis makes the effective unitary on the last column a relative $\varepsilon$-approximate unitary 2-design, meaning its first two moments match the Haar measure up to a multiplicative factor. The second property follows from a worst-to-average reduction: an oracle that computes a $3/4+1/\mathrm{poly}(N)$ fraction of the probabilities can be lifted to compute all of them, a #P-hard task. These are the two principal open conjectures in a physically simple sampling proposal; with them closed, the remaining gap to a full noise-robust hardness proof is the approximate average-case hardness conjecture.

What carries the argument

The central object is the relative $\varepsilon$-approximate unitary 2-design: a distribution on unitaries whose second moment operator lies between $(1-\varepsilon)$ and $(1+\varepsilon)$ times the Haar moment operator in the completely positive order. The proof of Theorem 1 chains several reductions. First, the design property is equivalent to bounding the tensor-product-expander quantity $g(v,2)$, defined as the operator norm of the difference between the second-moment operator and its Haar average; this quantity contracts under convolution and tolerates removal of fixed unitaries. Second, three layers of the circuit are rewritten as two fixed unitaries around a random unitary drawn from $v_n$, and universality of $v_n$ is proved by propagating entangling power from the boundary into the bulk. Third, a generalized detectability lemma bounds $g(v_n,2)$ by $1/\sqrt{\Delta(H_n)/9+1}$, where $H_n$ is the frustration-free Hamiltonian formed from averaged projectors $P^X_i$, $P^Z_i$, and $P^{ZXZ}_i$. Fourth, the Nachtergaele martingale bound lower-bounds $\Delta(H_n)$ by a constant using an exact description of the relevant ground spaces. Theorem 2 uses a truncated Taylor interpolation between a fixed angle vector and a Haar-random one, making the output probability a low-degree polynomial in the interpolation parameter; a polynomial-recovery algorithm then converts an oracle correct on a $3/4+1/\mathrm{poly}(N)$ fraction of instances into a worst-case solver.

What would settle it

Recompute the lowest eigenvalues of the seven-site bulk Hamiltonian used in the Nachtergaele step using certified interval arithmetic or rational arithmetic; a zero gap would invalidate the uniform spectral-gap lower bound on which Theorem 1 and hence anticoncentration rest.

Watch

Extended reading notes

Core claim

The paper's central discovery is that the quantum simulation architectures of the original speedup proposal form relative $\varepsilon$-approximate unitary 2-designs in linear effective depth, and that their output probabilities are exact average-case hard. Concretely, Theorem 1 states that for an $n\times m$ lattice with $m\in O(4n+\log(1/\varepsilon))$, measuring the first $m-1$ columns in the $X$ basis leaves an effective unitary on the last column whose first and second moments are within relative error $\varepsilon$ of the Haar measure; by a second-moment probability argument, this implies anticoncentration of the full output distribution. Theorem 2 states that computing any $3/4+1/\mathrm{poly}(N)$ fraction of the output probabilities is #P-hard, where the hard distribution is a truncated, perturbed version of the Haar measure on the local angles. Together the two theorems close the conjectures left open for this architecture and bring its complexity-theoretic evidence to the same standard previously achieved for random circuit sampling.

Load-bearing premise

The load-bearing premise is that a particular fixed seven-site bulk Hamiltonian has a strictly positive spectral gap; the paper verifies this only by floating-point numerical diagonalization, not by a rigorous certificate, and the proof of Theorem 1 fails if that gap is zero.

Editorial extensions

If this is right

  • Anticoncentration holds for a constant-time, translation-invariant nearest-neighbour Ising quench on a 2D lattice, a regime where no such theorem was previously available.
  • The effective circuits are universal despite not being locally universal, so the design argument covers a physically natural, translation-invariant family rather than a gate set randomized gate by gate.
  • Exact average-case #P-hardness transfers to commuting (IQP-style) circuits and to any generalized circuit architecture with worst-case #P-hard probability evaluation.
  • The only remaining assumption before the full noise-robust sampling-hardness argument closes is approximate average-case hardness; the paper does not prove that conjecture.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Going beyond the paper, the rigorous depth constant from the Nachtergaele bound is almost certainly loose; extrapolating the paper's own numerics for small $n$ suggests the 2-design threshold may be reached with a substantially smaller prefactor.
  • Going beyond the paper, a certified computation of the seven-site gap would remove the only numerical step in the proof of Theorem 1, upgrading the 2-design result to a fully rigorous finite-dimensional verification.
  • Going beyond the paper, because relative approximate 2-designs are known resources for decoupling and randomized benchmarking, the same translation-invariant quench could serve as a practical randomizing primitive, not only as a sampling-hardness device.
  • Going beyond the paper, the boundary-to-bulk universality propagation suggests a general recipe: any translation-invariant Hamiltonian family containing a boundary entangler plus local $X$ and $Z$ rotations may be a candidate for the same 2-design proof.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper studies a measurement-based Hamiltonian quantum simulation architecture on an n-by-m square lattice and claims to close two open gaps in the quantum-advantage argument for this scheme. Theorem 1 asserts that the effective random circuit on the last column, obtained after measuring the first m-1 columns in the X basis, is a relative epsilon-approximate unitary 2-design whenever m is in O(4n + log(1/epsilon)). The proof reduces this to the spectral gap of a frustration-free Hamiltonian, uses the detectability lemma and the Nachtergaele martingale bound, and invokes a numerically computed gap for a seven-site bulk Hamiltonian. Theorem 2 claims that exactly computing a 3/4 + 1/poly(N) fraction of the output probabilities is #P-hard. The proof follows the polynomial-interpolation approach of Bouland et al., but the formal statement in Appendix D establishes hardness only for the truncated theta-perturbed Haar distribution H_{theta,K}, whose gates are non-unitary. The text acknowledges this caveat and points to Movassagh's rational-interpolation fix without incorporating it.

Significance. If Theorem 1 holds as stated, it is a substantial result: it gives the first proof that a constant-time, translation-invariant Hamiltonian simulation architecture produces an approximate 2-design in linear effective depth, with anticoncentration as a corollary. The proof machinery is technically impressive: the reduction to tensor-product expanders, the use of the generalized detectability lemma, and the verification of the Nachtergaele conditions are carried out in unusual detail, and the numerical gap computation gives convincing evidence for the constants. The average-case hardness part contributes a useful reduction for a distribution close to the architectural distribution, but in its present form it does not prove the informal Theorem 2. The paper is therefore significant but currently overclaims one of its two advertised pillars.

major comments (2)
  1. [Section 'Average-case hardness' and Appendix D, Theorem 20] The informal Theorem 2, the abstract, and the conclusion state that it is #P-hard to compute a 3/4 + 1/poly(N) fraction of the output probabilities of the architectures of quantum simulation. The formal result in Appendix D (Theorem 20) is weaker: hardness is proven for p_0(C') over circuits C' drawn from C*H_{theta,K}, where H_{theta,K} is the truncated perturbed Haar distribution of Definitions 18-19. The gates in that distribution are truncated Taylor series, not unitary gates, so C' is not a circuit of the architecture and its amplitudes are not output probabilities of the architecture. The manuscript itself states that 'strictly speaking, our result does not prove average-case hardness of the Haar distribution on S1' and cites Movassagh's rational-interpolation fix [58] without proving or integrating it. Because average-case hardness of exactly evaluating the architecture's own output probabilities is one of the two gaps the paper claims to close, this mismatch is load-bearing. The authors should either restate Theorem 2 and the abstract to match Theorem 20, or supply and prove the transfer from H_{theta,K} to the architectural distribution.
  2. [Appendix C and Lemma 17, Eq. (13)] The proof of Theorem 1 depends on positivity of the spectral gap of the seven-site Hamiltonian H_B^7: the Nachtergaele bound yields Delta(H_n) >= Delta(H_B^7)/32 only if Delta(H_B^7) > 0. Appendix C reports Delta(H_B^7) ≈ 0.111 obtained with scipy.sparse.linalg.eigsh, but no certified interval, rational-arithmetic bound, or interval-arithmetic certificate is provided. A floating-point eigenvalue computation is strong numerical evidence but does not by itself make the claimed theorem rigorous. I recommend adding a small certified computation, or explicitly stating that the theorem depends on a numerical conjecture for this constant.
minor comments (4)
  1. [Abstract, Section 'Architectures', Eq. (B90)] The phrase 'constant depth architectures' is potentially misleading: the physical Hamiltonian evolution time is constant, but the effective circuit depth required by Theorem 1 is m in O(4n + log(1/epsilon)), which is linear in n. Please use 'constant-time' or 'constant physical depth' consistently.
  2. [Appendix D, Definition 18] The definition r_l^j := -i log R_l^j relies on a matrix logarithm that is multivalued for unitary operators. A brief remark on the chosen branch or on why the ambiguity does not affect the later arguments would improve rigor.
  3. [Appendix B, Eq. (B21)] In the definition of P^Z_i, the integral is written with d phi^X_i instead of d phi^Z_i; this appears to be a typo.
  4. [Appendix B, Lemma 16, Eqs. (B49)-(B55)] Several display lines in the verification of the three-qubit ground space contain apparent typographical errors in the basis labels; for example, the right-hand side of Eq. (B52) should presumably be |0101>|0101>|0101>, not |0101>|0101>|0110>. Please recheck these equations.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the derivation reduces to external benchmarks (the Haar measure) and a fixed small-system numerical constant, not to the claims themselves.

full rationale

The chain for Theorem 1 is a genuine reduction: the 2-design property is defined against the Haar measure as an external benchmark, reduced to a tensor-product-expander bound, then via the detectability lemma to the spectral gap of a fixed frustration-free Hamiltonian, and finally lower-bounded using Nachtergaele's theorem. The only numerical input is the spectral gap of the fixed seven-site Hamiltonian H_B^7 reported in Appendix C; this is a concrete computed constant for a fixed operator, not a parameter fitted to force anticoncentration. If the floating-point value were wrong the theorem would lack a proven constant, but that is a rigor gap, not circularity. Theorem 2 reduces average-case hardness to the worst-case #P-hardness of Lemma 21 (proven in prior work [24]) via polynomial interpolation and Berlekamp-Welch; the interpolation target is the truncated perturbed distribution H_{\theta,K}, and the paper explicitly acknowledges that "strictly speaking, our result does not prove average-case hardness of the Haar distribution on S1 but a close distribution". That admission marks an overclaim or missing transfer step, but it is not a self-referential construction. The self-citations to [24] and [28] supply the architecture and the random-circuit-sampling proof strategy as starting points; they do not assume Theorem 1 or Theorem 2. No fitted input is renamed as a prediction, and no uniqueness claim is imported to forbid alternatives.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The proofs rest on standard black-box theorems (generalized detectability lemma, Nachtergaele martingale bound, Paley-Zygmund anticoncentration lemma), on the prior worst-case #P-hardness result for the same architecture from Ref. [24], and on an external fix by Movassagh to extend average-case hardness to the exact Haar distribution. The 2-design proof also depends on the numerical positivity of the seven-site spectral gap Δ(H_B^7), which is not formally certified. No free parameters are fitted to the target claims: the architecture is fixed from prior work and the depth scaling is derived, not tuned. The proof parameter l=6 in the Nachtergaele verification is a hand-chosen constant satisfying the required inequality, and is not fitted to data. No new physical entities are introduced; the detectability Hamiltonian and the (θ,K)-perturbed distribution are mathematical tools.

assumptions (6)
  • domain assumption Worst-case #P-hardness of approximating the architecture's output probabilities to precision 2^{-poly(n)} (Lemma 21, from Ref. [24]).
    The average-case hardness proof (Appendix D) reduces to this prior result. It is an established theorem from the same group's earlier paper, used as the worst-case base for the worst-to-average reduction.
  • standard math Generalized detectability lemma (Lemma 13, from Ref. [48]) and Nachtergaele spectral gap bound (Lemma 15, from Ref. [49]).
    Used as black boxes: the detectability lemma bounds the tensor-product-expander norm by the spectral gap, and the Nachtergaele bound lower-bounds the gap in the thermodynamic limit. Both are established theorems in quantum many-body physics.
  • standard math A relative ε-approximate unitary 2-design anticoncentrates via the Paley-Zygmund inequality (Lemma 4, from Ref. [32]).
    This bridges Theorem 1 to anticoncentration of the last-column probabilities.
  • domain assumption The output distribution of the full architecture anticoncentrates if the conditional distribution on the last column anticoncentrates, using p(x_L, x_R) = p(x_R|x_L)/2^{n(m−1)} (main text, after Lemma 4).
    This is a property of the measurement-based protocol; the paper derives it from the circuit mapping in Appendix A. It is internal to the architecture.
  • domain assumption Movassagh's rational-function interpolation fix (Ref. [58]) extends average-case hardness from the (θ,K)-truncated perturbed distribution to the original Haar-random distribution.
    The informal Theorem 2 (main text) states hardness over the architectures with Haar-random angles, but Appendix D proves Theorem 20 for the perturbed, non-unitary distribution. The literal statement relies on Movassagh's separate proof, which is cited with details omitted.
  • domain assumption The seven-site bulk spectral gap is positive, Δ(H_B^7) > 0, as reported numerically in Appendix C.
    Lemma 17 requires this positivity to conclude the spectral gap is bounded below for all n; the paper provides floating-point values (≈0.111) without a certified proof.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Closing gaps of a quantum advantage with short-time Hamiltonian dynamics." pith.science (2026). https://pith.science/paper/EBSF7VBF

@misc{pith2026190808069,
  author       = {Pith},
  title        = {Pith review of: Closing gaps of a quantum advantage with short-time Hamiltonian dynamics},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EBSF7VBF}},
  note         = {Machine review of arXiv:1908.08069}
}
read the original abstract

Demonstrating a quantum computational speedup is a crucial milestone for near-term quantum technology. Recently, quantum simulation architectures have been proposed that have the potential to show such a quantum advantage, based on commonly made assumptions. The key challenge in the theoretical analysis of this scheme - as of other comparable schemes such as boson sampling - is to lessen the assumptions and close the theoretical loopholes, replacing them by rigorous arguments. In this work, we prove two open conjectures for these architectures for Hamiltonian quantum simulators: Anticoncentration of the generated probability distributions and average-case hardness of exactly evaluating those probabilities. The latter is proven building upon recently developed techniques for random circuit sampling. For the former, we develop new techniques that exploit the insight that approximate 2-designs for the unitary group admit anticoncentration. We prove that the 2D translation-invariant, constant depth architectures of quantum simulation form approximate 2-designs in a specific sense, thus obtaining a significantly stronger result. Our work provides the strongest evidence to date that Hamiltonian quantum simulation architectures are classically intractable.

Figures

Figures reproduced from arXiv: 1908.08069 by the authors.

Figure 1
Figure 1. Two layers of the circuit described in Definition [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. Three layers of the physical circuit on six sites. For a convenient graphical representation, we use the notation [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
Figure 3
Figure 3. A circuit on six sites that implements the same unitary as the one in Figure 2. [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Illustration of the supports of the projectors [PITH_FULL_IMAGE:figures/full_fig_p016_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

75 extracted references · 57 canonical work pages

  1. [24]

    Bermejo-Vega, D

    J. Bermejo-Vega, D. Hangleiter, M. Schwarz, R. Raussendorf, and J. Eisert, Architectures for quantum simulation showing a quantum speedup, Phys. Rev. X 8, 021010 (2018)

    2018

  2. [58]

    Welch and E

    L. Welch and E. Berlekamp, Error correction for algebraic block codes, US Patent , US4633470 (1986). 7

    work page 1986

  3. [1]

    P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer , SIAM J. Sci. Statist.Comput. 41, 303 (1999)

    work page 1999

  4. [2]

    R. P. Feynman, Simulating physics with computers, Int J. Theor Phys 21, 467 (1982)

    work page 1982

  5. [3]

    Lloyd, Universal quantum simulators , Science 273, 1073 (1996)

    S. Lloyd, Universal quantum simulators , Science 273, 1073 (1996)

    work page 1996

  6. [4]

    Bloch, J

    I. Bloch, J. Dalibard, and S. Nascimbene, Quantum simulations with ultracold quantum gases, Nature Phys. 8, 267 (2012)

    work page 2012

  7. [5]

    Reiher, N

    M. Reiher, N. Wiebe, K. M. Svore, D. Wecker, and M. Troyer, Elucidating reaction mechanisms on quantum computers, Proc. Natl. Ac. Sc. 114, 7555 (2017)

    work page 2017

  8. [6]

    Campbell, A

    E. Campbell, A. Khurana, and A. Montanaro, Applying quan- tum algorithms to constraint satisfaction problems , (2018), arXiv:1810.05582

    arXiv 2018

Show all 75 references
  1. [7]

    Litinski, A game of surface codes: Large-scale quantum computing with lattice surgery, Quantum 3, 128 (2019)

    D. Litinski, A game of surface codes: Large-scale quantum computing with lattice surgery, Quantum 3, 128 (2019)

    2019

  2. [8]

    Gidney and M

    C. Gidney and M. Ekera, How to factor 2048 bit RSA in- tegers in 8 hours using 20 million noisy qubits , (2019), arXiv:1905.09749

    2019 arXiv

  3. [9]

    Trotzky, Y .-A

    S. Trotzky, Y .-A. Chen, A. Flesch, I. P. McCulloch, U. Scholl- wöck, J. Eisert, and I. Bloch, Probing the relaxation towards equilibrium in an isolated strongly correlated one-dimensional Bose gas, Nature Phys. 8, 325 (2012)

    2012

  4. [10]

    Braun, M

    S. Braun, M. Friesdorf, J. S. Hodgman, M. Schreiber, J. P. Ronzheimer, A. Riera, M. del Rey, I. Bloch, J. Eisert, and U. Schneider, Emergence of coherence and the dynamics of quantum phase transitions, PNAS 112, 3641 (2015)

    2015

  5. [11]

    J.-y. Choi, S. Hild, J. Zeiher, P. Schauß, A. Rubio-Abadal, T. Yefsah, V . Khemani, D. A. Huse, I. Bloch, and C. Gross, Exploring the many-body localization transition in two dimen- sions, Science 352, 1547 (2016)

    2016

  6. [12]

    Bernien, S

    H. Bernien, S. Schwartz, A. Keesling, H. Levine, A. Omran, H. Pichler, S. Choi, A. S. Zibrov, M. Endres, M. Greiner, V . Vuletic, and M. D. Lukin, Probing many-body dynamics on a 51-atom quantum simulator, Nature 551, 579 (2017)

    2017

  7. [13]

    Zhang, G

    J. Zhang, G. Pagano, P. W. Hess, A. Kyprianidis, P. Becker, H. Kaplan, A. V . Gorshkov, Z.-X. Gong, and C. Monroe, Ob- servation of a many-body dynamical phase transition with a 53-qubit quantum simulator, Nature 551, 601 (2017). 6

    2017

  8. [14]

    Aaronson and A

    S. Aaronson and A. Arkhipov, The computational complexity of linear optics, Proc. Ann. ACM. Syp. Th. Comp. 9, 143 (2013)

    2013

  9. [15]

    M. J. Bremner, A. Montanaro, and D. J. Shepherd, Average- case complexity versus approximate simulation of commuting quantum computations, Phys. Rev. Lett. 117, 080501 (2016)

    2016

  10. [16]

    Boixo, S

    S. Boixo, S. V . Isakov, V . N. Smelyanskiy, R. Babbush, N. Ding, Z. Jiang, J. M. Martinis, and H. Neven, Characterizing quan- tum supremacy in near-term devices , Nature Phys. 14, 595 (2018)

    2018

  11. [17]

    H. Wang, Y . He, Y .-H. Li, Z.-E. Su, B. Li, H.-L. Huang, X. Ding, M.-C. Chen, C. Liu, J. Qin,et al., High-efficiency mul- tiphoton boson sampling, Nature Photonics 11, 361 (2017)

    2017

  12. [18]

    A. W. Harrow and A. Montanaro, Quantum computational supremacy, Nature 549, 203 (2017)

    2017

  13. [19]

    quantum supremacy

    D. Hangleiter, M. Kliesch, J. Eisert, and C. Gogolin, Sam- ple complexity of device-independently certified “quantum supremacy”, Phys. Rev. Lett. 122, 210502 (2019)

    2019

  14. [20]

    Gogolin, M

    C. Gogolin, M. Kliesch, L. Aolita, and J. Eisert, Boson- sampling in the light of sample complexity, arXiv:1306.3995

    arXiv

  15. [21]

    Aaronson and A

    S. Aaronson and A. Arkhipov, Bosonsampling is far from uni- form, (2013), arXiv:1309.7460

    2013 arXiv

  16. [22]

    Eisert, D

    J. Eisert, D. Hangleiter, N. Walk, I. Roth, D. Markham, R. Parekh, U. Chabaud, and E. Kashefi, Quantum certification and benchmarking, (2019), arXiv:1910.06343

    2019 arXiv

  17. [23]

    Gao, S.-T

    X. Gao, S.-T. Wang, and L.-M. Duan, Quantum supremacy for simulating a translation-invariant Ising spin model, Phys. Rev. Lett. 118 (2017), 10.1103/PhysRevLett.118.040502

    2017 doi

  18. [25]

    M. J. Bremner, A. Montanaro, and D. J. Shepherd, Average- case complexity versus approximate simulation of commuting quantum computations, Phys. Rev. Lett. (2016), 10.1103/Phys- RevLett.117.080501

    2016 doi

  19. [26]

    Hangleiter, M

    D. Hangleiter, M. Kliesch, M. Schwarz, and J. Eisert, Direct certification of a class of quantum simulations , Quantum Sci. Technol. 2, 015004 (2017)

    2017

  20. [27]

    Boixo, S

    S. Boixo, S. V . Isakov, V . N. Smelyanskiy, R. Babbush, N. Ding, Z. Jiang, M. J. Bremner, J. M. Martinis, and H. Neven,Charac- terizing quantum supremacy in near-term devices, Nature Phys. , 1 (2018)

    2018

  21. [28]

    Bouland, B

    A. Bouland, B. Fefferman, C. Nirkhe, and U. Vazirani, Quan- tum supremacy and the complexity of random circuit sampling, Nature Phys. 15, 159 (2019)

    2019

  22. [29]

    B. M. Terhal and D. P. DiVincenzo, Adaptive quantum com- putation, constant depth quantum circuits and Arthur-Merlin games, Quant. Inf. Comp. 4, 134 (2004)

    2004

  23. [30]

    Stockmeyer, On approximation algorithms for # P, SIAM J

    L. Stockmeyer, On approximation algorithms for # P, SIAM J. Comput. 14, 849 (1985)

    1985

  24. [31]

    Explicitly, we exploit the connection to gaps of frustration-free Hamiltonians [31, 47]

    that shows that random universal circuits form an ap- proximate t-design. Explicitly, we exploit the connection to gaps of frustration-free Hamiltonians [31, 47]. We follow the general strategy of Brandão et al. [31], but every individual step of the proof requires new methods...

    2020

  25. [32]

    F. G. S. L. Brandão, A. W. Harrow, and M. Horodecki, Lo- cal Random Quantum Circuits are Approximate Polynomial- Designs, Commun. Math. Phys. 346, 397 (2016)

    2016

  26. [33]

    Hangleiter, J

    D. Hangleiter, J. Bermejo-Vega, M. Schwarz, and J. Eisert, Anticoncentration theorems for schemes showing a quantum speedup, Quantum 2, 65 (2018)

    2018

  27. [34]

    Harrow and S

    A. Harrow and S. Mehraban, Approximate unitary t-designs by short random quantum circuits using nearest-neighbor and long-range gates, (2018), arXiv:1809.06957

    2018 arXiv

  28. [35]

    Bouland, J

    A. Bouland, J. F. Fitzsimons, and D. E. Koh, Complexity clas- sification of conjugated Clifford circuits , in Proc. 33rd Comp. Compl. Conf. (Schloss Dagstuhl–Leibniz-Zentrum fuer Infor- matik, 2018) p. 21

    2018

  29. [36]

    R. L. Mann and M. J. Bremner, On the complexity of ran- dom quantum computations and the Jones polynomial, (2017), arXiv:1711.00686

    2017 arXiv

  30. [37]

    Szehr, F

    O. Szehr, F. Dupuis, M. Tomamichel, and R. Renner, Decou- pling with unitary approximate two-designs , New J. Phys. 15, 053022 (2013)

    2013

  31. [38]

    Hirche and C

    C. Hirche and C. Morgan, Efficient achievability for quantum protocols using decoupling theorems , Proc. 2014 IEEE Int. Symp. Info. Theory , 536 (2014)

    2014

  32. [39]

    Dupuis, M

    F. Dupuis, M. Berta, J. Wullschleger, and R. Renner, One-shot decoupling, Commun. Math. Phys. 328, 251 (2014)

    2014

  33. [40]

    Emerson, R

    J. Emerson, R. Alicki, and K. Zyczkowski, Scalable noise es- timation with random unitary operators, J. Opt. B , 347 (2005)

    2005

  34. [41]

    I. Roth, R. Kueng, S. Kimmel, Y .-K. Liu, D. Gross, J. Eisert, and M. Kliesch, Recovering quantum gates from few average gate fidelities, Phys. Rev. Lett. 121, 170502 (2018)

    2018

  35. [42]

    F. G. S. L. Brandão, A. W. Harrow, and M. Horodecki, Efficient quantum pseudorandomness , Phys. Rev. Lett. 116, 170502 (2016)

    2016

  36. [43]

    M. J. Bremner, A. Montanaro, and D. J. Shepherd, Achieving quantum supremacy with sparse and noisy commuting quantum computations, Quantum 1, 8 (2017)

    2017

  37. [44]

    Miller, S

    J. Miller, S. Sanders, and A. Miyake, Quantum supremacy in constant-time measurement-based computation: A unified architecture for sampling and verification , Phys. Rev. A 96, 062320 (2017)

    2017

  38. [45]

    Mezher, J

    R. Mezher, J. Ghalbouni, J. Dgheim, and D. Markham, Ef- ficient quantum pseudorandomness with simple graph states , Phys. Rev. A 97, 022333 (2018)

    2018

  39. [46]

    Mezher, J

    R. Mezher, J. Ghalbouni, J. Dgheim, and D. Markham,Efficient approximate unitary t-designs from partially invertible univer- sal sets and their application to quantum speedup , (2019), arXiv:1905.01504

    2019 arXiv

  40. [47]

    W. G. Brown, Y . S. Weinstein, and L. Viola, Quantum pseu- dorandomness from cluster-state quantum computation , Phys. Rev. A 77, 040303 (2008)

    2008

  41. [48]

    W. G. Brown and L. Viola,Convergence rates for arbitrary sta- tistical moments of random quantum circuits , Phys. Rev. Lett. 104, 250501

  42. [49]

    Anshu, I

    A. Anshu, I. Arad, and T. Vidick, A simple proof of the de- tectability lemma and spectral gap amplification, Phys. Rev. B 93, 205142 (2016)

    2016

  43. [50]

    Nachtergaele, The spectral gap for some spin chains with disrete symmetry breaking , Commun

    B. Nachtergaele, The spectral gap for some spin chains with disrete symmetry breaking , Commun. Math. Phys. 175, 565 (1996)

    1996

  44. [51]

    A. W. Harrow and R. A. Low, Random quantum circuits are approximate 2-designs, Commun. Math. Phys.291, 257 (2009)

    2009

  45. [52]

    Brylinski and R

    J.-L. Brylinski and R. Brylinski, Universal quantum gates , (2001), arXiv:quant-ph/0108062

    2001 arXiv

  46. [53]

    M. J. Bremner, C. M. Dawson, J. L. Dodd, A. Gilchrist, A. W. Harrow, D. Mortimer, M. A. Nielsen, and T. J. Osborne, A practical scheme for quantum computation with any two-qubit entangling gate, Phys. Rev. Lett. 89, 247902 (2002)

    2002

  47. [54]

    Aharonov, I

    D. Aharonov, I. Arad, Z. Landau, and U. Vazirani, The de- tectability lemma and quantum gap amplification , Prof. Ann. ACM Symp. T. Comp. , 417426 (2009)

    2009

  48. [55]

    Cubitt, D

    T. Cubitt, D. Perez-Garcia, and M. M. Wolf, Undecidability of the spectral gap, Nature 528, 207 (2015)

    2015

  49. [56]

    Bausch, T

    J. Bausch, T. Cubitt, A. Lucia, and D. Perez-Garcia, Un- decidability of the spectral gap in one dimension , (2018), arXiv:1810.01858

    2018 arXiv

  50. [57]

    Lipton, New directions in testing, Dist

    R. Lipton, New directions in testing, Dist. Comp. Crypt. 2, 191 (1991)

    1991

  51. [59]

    Movassagh, Efficient unitary paths and quantum computa- tional supremacy: A proof of average-case hardness of Random Circuit Sampling, (2018), arXiv:1810:04681

    R. Movassagh, Efficient unitary paths and quantum computa- tional supremacy: A proof of average-case hardness of Random Circuit Sampling, (2018), arXiv:1810:04681

    2018

  52. [60]

    Mantri, R

    A. Mantri, R. F. Demarie, and J. F. Fitzsimons, Universality of quantum computation with cluster states and (X,Y)-plane mea- surements, Sci. Rep. 7, 42861 (2017)

    2017

  53. [61]

    E. A. Rakhmanov, Bounds for polynomials with a unit discrete norm, Ann. Math. 165, 55 (2007)

    2007

  54. [62]

    Paturi, On the degree of polynomials that approximate sym- metric Boolean functions, Proc

    R. Paturi, On the degree of polynomials that approximate sym- metric Boolean functions, Proc. ACM STOC , 468 (1992)

    1992

  55. [63]

    Haferkamp, D

    J. Haferkamp, D. Hangleiter, J. Eisert, and M. Gluza, Con- tracting projected entangled pair states is average-case hard , (2018), arXiv:1810.00738. Appendix A: The full Hamiltonian and mapping to effective circuits The Ising Hamiltonian for the architectures of quantum simula...

    2018 arXiv

  56. [64]

    Prepare each qubit in the state|+⟩

  57. [65]

    For each qubit, draw a phaseϕj∈S1 ∼ = [0, 2π]/∼ uniformly at random and apply the diagonal gateGj :=eiϕjZ

  58. [66]

    Apply a controlled Z gateCZ to all neighbouring qubits

  59. [67]

    Apply a Hadamard gate to each qubit

  60. [68]

    Repeat the above D = poly(N) many times

  61. [69]

    In general, we refer to the resulting quantum circuits arising from drawing randomGj as random circuits

    Measure in the Z eigenbasis. In general, we refer to the resulting quantum circuits arising from drawing randomGj as random circuits. The task that we will show to be average-case hard is to sample from the output distribution of this circuit. In general, we restrict to famili...

  62. [70]

    Tensor product expanders and designs In the first step of the proof, we reduce the 2-design property to a so-called 2-copy tensor product expander property as established in Ref. [31]. For completeness and to set the notation, we review this step here. We use the following rela...

  63. [71]

    We refer to the circuit generated by one column as a layer of the random circuit

    Reduction to spectral gaps of frustration-free Hamiltonians The random quantum circuits generated by measuring the first m− 1 columns are translation invariant in the sense that the full measure is the (m− 1)-fold convolution of the measure for an individual column. We refer to...

  64. [72]

    One method to obtain such a lower bound on the spectral gap in the thermodynamic limit is theNachtergaele bound [49] sometimes called martingale method

    Lower bounding the spectral gap In the following we are going to show that there is a constant α >0 such that ∆(Hn) > αfor alln. One method to obtain such a lower bound on the spectral gap in the thermodynamic limit is theNachtergaele bound [49] sometimes called martingale met...

  65. [73]

    There is a constant dl for which the Hamiltonians satisfy 0≤ N∑ i=l 1 [1,i−l]⊗H[i−l+1,i]⊗ 1 [i+1,n]≤dlH[1,n] for all n≥ql. (B34)

  66. [74]

    The lowest eigenvalue for all H[p,q] is 0 and there is a spectral gapγl > 0: ∆ ( H[q−l+1,q] ) ≥γl for all q≥ql (B35) for some constantql

  67. [75]

    There existεl < 1/ √ l + 1 such that ⏐⏐⏐⏐G[q−l+1,q+1] ( G[1,q]−G[1,q+1] )⏐⏐⏐⏐ ∞≤εl for all q≥ql

    We denote the ground state projector of 1 [1,p−1]⊗H[p,q]⊗ 1 [q+1,n] withG[p,q]. There existεl < 1/ √ l + 1 such that ⏐⏐⏐⏐G[q−l+1,q+1] ( G[1,q]−G[1,q+1] )⏐⏐⏐⏐ ∞≤εl for all q≥ql. (B36) Then, ∆ ( H[1,n] ) ≥ γl+1 dl+1 ( 1−εl √ l + 1 )2 for all n≥ql. (B37) Here, we would like to ap...

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.