pith. sign in

arxiv: 2506.03435 · v2 · submitted 2025-06-03 · 🪐 quant-ph · cs.CC

Computational Complexity and Simulability of Non-Hermitian Quantum Dynamics

Brian Barch , Daniel Lidar This is my paper

Pith reviewed 2026-05-19 10:32 UTC · model grok-4.3

classification 🪐 quant-ph cs.CC
keywords non-Hermitian quantum dynamicscomputational complexityPostBQPpostselectionquantum circuitsclassical simulabilityquantum trajectories
0
0 comments X p. Extension

The pith

Quantum circuits using a fixed non-unitary gate with coherent renormalization after each application can decide any problem in PostBQP.

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

The paper establishes that non-Hermitian quantum dynamics, when modeled as repeated use of one fixed non-unitary gate on a constant number of qubits inside otherwise standard polynomial-size circuits, confer the full power of postselection. This yields NHBQP(U) equal to PostBQP, which equals PP, for any such fixed gate U. A reader would care because PostBQP is widely believed to lie outside efficient classical or quantum computation under standard assumptions, so the result indicates that scalable non-Hermitian advantage cannot be obtained without incurring prohibitive efficiency costs. The work further shows that when the non-Hermitian evolution admits a purification into a classically simulable unitary family, the model stays efficiently simulable provided the relevant postselected outcomes occur with inverse-polynomial probability.

Core claim

We prove that NHBQP(U), the class of problems solvable by poly-size circuits that may apply a fixed non-unitary O(1)-qubit gate U with renormalization after each use, equals PostBQP for every such U. In the uniform circuit-family model the characterization is tight: NHBQP(U) = PostBQP = PP. Unitary circuits augmented with postselection can simulate not only NH Hamiltonian evolution but arbitrary quantum trajectories; consequently any NH system whose purification lies inside a strongly simulable unitary family remains efficiently classically simulable whenever postselected events have probability at least inverse polynomial.

What carries the argument

The NHBQP(U) model: polynomial-size quantum circuits that combine a universal unitary gate set with repeated applications of one fixed non-unitary gate U on O(1) qubits, followed by coherent renormalization of the state after each use of U.

If this is right

  • If coherent normalized non-unitary evolution can be realized with only polynomial overhead, the resulting model implements postselection.
  • Any scalable computational advantage from non-Hermiticity must come with a cost that limits its efficiency.
  • Unitary circuits with postselection can simulate evolution under arbitrary NH Hamiltonians and general quantum trajectories.
  • NH models whose purifications belong to simulable families such as Clifford or matchgate circuits remain efficiently classically simulable when postselected events occur with probability Omega(2^{-poly(n)}).

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The result suggests that any physical implementation attempting to exploit non-Hermiticity for computation will face exponential suppression or normalization costs that grow with circuit depth.
  • The separation between simulable and powerful regimes is sharpened: non-Hermiticity alone does not create new computational power inside already simulable unitary families.

Load-bearing premise

The model assumes perfect coherent normalization is possible after each application of the fixed non-unitary gate and that the circuit family remains uniform.

What would settle it

An explicit construction of a fixed non-unitary gate U such that NHBQP(U) is contained in BQP, or an efficient classical algorithm deciding all languages in NHBQP(U), would falsify the claimed equality to PostBQP.

Figures

Figures reproduced from arXiv: 2506.03435 by Brian Barch, Daniel Lidar.

Figure 1
Figure 1. Figure 1: FIG. 1. Circuit depicting usage of an [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: FIG. 2. Geometric representation of two rounds of unitary [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: FIG. 3. Decomposition of a non-unitary effective channel [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: FIG. 4. The circuit describing a single Trotter step of simu [PITH_FULL_IMAGE:figures/full_fig_p010_4.png] view at source ↗
Figure 6
Figure 6. Figure 6: FIG. 6. Two-qubit meter circuit used to implement [PITH_FULL_IMAGE:figures/full_fig_p010_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: FIG. 7. Product nature of [PITH_FULL_IMAGE:figures/full_fig_p011_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: FIG. 8. Effective circuit generating Lindbladian dynamics [PITH_FULL_IMAGE:figures/full_fig_p014_8.png] view at source ↗
read the original abstract

Non-Hermitian (NH) quantum systems demonstrate striking differences from their Hermitian counterparts, leading to claims of NH advantage in areas ranging from metrology to entanglement generation. We show that in the context of quantum computation, any such NH advantage is unlikely to be scalable as an efficient computational resource: if coherent normalized non-unitary evolution could be realized with only polynomial overhead, then the resulting model could implement postselection, implying implausibly strong complexity-theoretic power under standard assumptions. We define NHBQP(U) as the computational power of poly-size quantum circuits that, in addition to a standard universal unitary gate set, may apply a fixed gate U on $O(1)$ qubits that is not proportional to a unitary, with the state renormalized after each use of U. We prove this model is powerful enough to decide PostBQP. In the standard uniform circuit-family model this characterization is tight: for any fixed such U, NHBQP(U)=PostBQP=PP. PostBQP is believed intractable, so this suggests that any scalable NH computational advantage must come with a cost limiting its efficiency. Additionally, we study locality-preserving purifications of restricted classes of non-unitary systems. Using this framework, we show that unitary gates with postselection can simulate not only evolution under NH Hamiltonians but arbitrary quantum trajectories. Any NH model whose purification lies in a strongly simulable unitary family (e.g., Clifford, matchgate, or low-bond-dimension tensor-network circuits) remains efficiently classically simulable, provided the relevant postselected events occur with probability $\Omega(2^{-\text{poly}(n)})$. Thus adding non-Hermiticity to a universal unitary system makes it infeasibly computationally powerful, while adding it to a strongly simulable system adds no computational power in this setting.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript defines the NHBQP(U) model consisting of polynomial-size quantum circuits that may apply a fixed non-unitary gate U on O(1) qubits (with coherent renormalization after each use) in addition to a standard universal unitary gate set. It proves that NHBQP(U) = PostBQP = PP for any fixed non-unitary U in the uniform circuit-family model. The paper further develops a framework of locality-preserving purifications of non-unitary evolutions, showing that postselected unitary circuits can simulate both NH Hamiltonian evolution and arbitrary quantum trajectories, and that any NH model whose purification lies in a strongly simulable unitary family (Clifford, matchgate, or low-bond-dimension tensor networks) remains efficiently classically simulable when the relevant postselected events occur with probability Ω(2^{-poly(n)}).

Significance. If the central characterizations hold, the work supplies a complexity-theoretic obstruction to scalable computational advantage from non-Hermitian dynamics: efficient coherent normalization would enable postselection and therefore solve PP-complete problems. The simulability results supply a complementary positive statement, delineating precisely when non-Hermiticity adds no computational power beyond the underlying unitary model. The proofs rely on standard uniform circuit families and explicit reductions that preserve uniformity, which strengthens the applicability of the conclusions.

minor comments (3)
  1. [§2] Definition of NHBQP(U) (likely §2): the precise semantics of the coherent renormalization step after each application of U should be stated formally, including whether the normalization factor is computed exactly or approximated and how it is incorporated into the circuit description.
  2. [§3] Proof of PostBQP ⊆ NHBQP(U) (likely §3): while the amplification argument via repeated applications aligned to the dominant singular direction is sketched, an explicit bound on the number of repetitions in terms of the singular-value gap of the fixed U would make the polynomial overhead fully transparent.
  3. [simulability section] Simulability section: the condition Ω(2^{-poly(n)}) on postselection probability is stated, but the manuscript should clarify whether this bound is uniform across all simulable families or depends on the bond dimension or circuit depth of the purification.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their careful review and for recommending minor revision. The referee's summary accurately captures the definition of the NHBQP(U) model, the equivalence to PostBQP=PP in the uniform circuit model, and the framework of locality-preserving purifications together with the simulability results for restricted non-Hermitian systems. We appreciate the recognition that these results supply both an obstruction to scalable non-Hermitian advantage and a precise delineation of when non-Hermiticity adds no computational power.

Circularity Check

0 steps flagged

No significant circularity; derivation relies on standard complexity inclusions

full rationale

The paper defines the NHBQP(U) model explicitly via repeated application of a fixed non-unitary gate U followed by coherent renormalization, then proves equivalence to PostBQP by two explicit reductions: (i) embedding postselection into repeated applications of U to amplify amplitudes along its dominant singular vector, and (ii) mapping each renormalization step to postselection on the no-jump branch of a unitary dilation. Both directions preserve uniformity and are justified by the known result PostBQP = PP (Aaronson 2005) rather than any self-citation or fitted parameter. No step reduces by construction to its own input; the central claim is an equivalence between independently defined models and does not invoke ansatzes, uniqueness theorems, or renamings from prior author work.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper introduces the NHBQP(U) model but rests on standard complexity facts and the definition of coherent renormalization; no free parameters or new physical entities are introduced.

axioms (1)
  • standard math PostBQP equals PP
    This known equality is invoked to conclude that NHBQP(U)=PP for any fixed U.

pith-pipeline@v0.9.0 · 5857 in / 1352 out tokens · 42523 ms · 2026-05-19T10:32:44.033260+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Magic Steady State Production: Non-Hermitian, Dissipative, and Stochastic Pathways

    quant-ph 2025-07 unverdicted novelty 6.0

    Non-Hermitian and dissipative dynamics engineer magic steady states in qubits that attract every initial state to high-magic targets.

Reference graph

Works this paper leans on

76 extracted references · 76 canonical work pages · cited by 1 Pith paper · 5 internal anchors

  1. [1]

    Normalized Evolution In order to consider time evolutionU as mapping states to states, one approach is to normalize its action on pure states |ψt⟩ |ψt⟩ ≡ U |ψ0⟩ ∥U |ψ0⟩∥ (4) or trace-normalize its action on mixed states ρt: ρt ≡ U ρ0U † Tr[U ρ0U †] (5) This is equivalent to dividing by the normalizing factor in the Bayes rule for conditional probability d...

    work page

  2. [2]

    Eigenvalues of pseudo-Hermitian H come in complex conjugate pairs

    P T-Symmetric Systems A Hamiltonian is said to be pseudo-Hermitian if there exists a Hermitian (generally non-unique) η such that H †η = ηH [3–5]. Eigenvalues of pseudo-Hermitian H come in complex conjugate pairs. If there further ex- ists a positive definite η, then H is said to be quasi- Hermitian or Parity-Time ( P T)-Symmetric and is guar- anteed to h...

    work page

  3. [3]

    We can always biorthonormalize the eigenvectors such that ⟨li|ri⟩ = δij, and may additionally normalize ⟨ri|ri⟩ = 1, but cannot do the same for {⟨li|}

    Diagonalizing H When H is diagonalizable but NH, it can be diagonal- ized in terms of right |ri⟩ and left ⟨li| eigenvectors as H = X i λi|ri⟩ ⟨li| (8) for λi the (in general complex) eigenvalues. We can always biorthonormalize the eigenvectors such that ⟨li|ri⟩ = δij, and may additionally normalize ⟨ri|ri⟩ = 1, but cannot do the same for {⟨li|}. Given thi...

    work page

  4. [4]

    In fact, many have outputs that can be reproduced by algorithms in BPP or even P

    Simulability Not all quantum systems are as hard as BQP. In fact, many have outputs that can be reproduced by algorithms in BPP or even P. These systems are referred to as weakly or strongly simulable [51–53]. Weakly simulable quantum systems admit classical al- gorithms that can sample measurement outcomes with approximately the correct distribution in p...

    work page

  5. [5]

    Evolution under an NH Hamiltonian even for short times is known to be able to solve certain decision problems outside BQP [21, 24]

    Complexity of NH Systems The computational power of models of computation generated by NH Hamiltonians is a subset of PostBQP, but is otherwise relatively unstudied. Evolution under an NH Hamiltonian even for short times is known to be able to solve certain decision problems outside BQP [21, 24]. This is striking, as NH systems are often used as an ap- pr...

    work page

  6. [6]

    First, de- compose H = H0 − iΓ for Hermitian H0, Γ, and write H0 = h⃗ n· ⃗ σand Γ = γ ⃗ m· ⃗ σfor unit vectors ⃗ n, ⃗ m, where ⃗ σis the Pauli vector

    P T-Symmetric H Here we show how to approximate postselection with an arbitrary single qubit P T-Symmetric H. First, de- compose H = H0 − iΓ for Hermitian H0, Γ, and write H0 = h⃗ n· ⃗ σand Γ = γ ⃗ m· ⃗ σfor unit vectors ⃗ n, ⃗ m, where ⃗ σis the Pauli vector. Notice that ⃗ n̸= ⃗ mor else H = ( h − iγ)⃗ n· ⃗ σhas complex eigenvalues and cannot be P T-Symm...

    work page

  7. [7]

    With ω2 = h2 − γ2, U = cos(ωt)I − i ω sin(ωt)H

    Ellipsoidal Periodic U Thanks to the anticommutation of σ1, σ2, H2 = (h2 − γ2)I cleanly, so the Taylor series of e−iHt decomposes into a cos and sin term like in the Hermitian case. With ω2 = h2 − γ2, U = cos(ωt)I − i ω sin(ωt)H. (B.6) Intuitively, this periodic behavior makes sense as a quasi- Hermitian Hamiltonian generates rotations on the ellip- soid ...

    work page

  8. [8]

    To see this, first notice that the minimizing unitary will be the polar factor V W †, as ∥αU − V W †∥ ≤ ∥ αU − T ∥ (C.4) for all unitary T [67]

    Singular Radius and the Minimum Distance from Unitarity One can show that ∆ is related to the minimal dis- tance between any normalization choice αU of U and the unitary group U(d) as ∆ = 1 c min α,T ∥αU − T ∥ (C.3) for α > 0, T ∈ U (d), and some c ∈ ( 1 2 , 1]. To see this, first notice that the minimizing unitary will be the polar factor V W †, as ∥αU −...

    work page

  9. [9]

    Singular Radius Bound After r repetitions of the effective non-unitary gate D as in Section III, the Kraus operator is Dr, whose singular values are λr j. To emulate postselection in the subspace span{|s1⟩ , |sd⟩}, we choose r large enough that the renormalized map suppresses the j = d branch below an error ε = 2−p(n) for polynomial p(n), i.e., λd/λ1 r ≤ ...

    work page

  10. [10]

    Ashida, Z

    Y. Ashida, Z. Gong, and M. Ueda, Advances in Physics 69, 249 (2020)

    work page 2020

  11. [11]

    Ashida and M

    Y. Ashida and M. Ueda, Physical Review Letters 120 (2018), 10.1103/physrevlett.120.185301

    work page doi:10.1103/physrevlett.120.185301 2018

  12. [12]

    C. M. Bender and S. Boettcher, Phys. Rev. Lett.80, 5243 (1998)

    work page 1998

  13. [13]

    C. M. Bender, D. C. Brody, and H. F. Jones, Phys. Rev. Lett. 89, 270401 (2002)

    work page 2002

  14. [14]

    Mostafazadeh, Journal of Mathematical Physics 43, 205 (2002)

    A. Mostafazadeh, Journal of Mathematical Physics 43, 205 (2002)

    work page 2002

  15. [15]

    Mostafazadeh, Czechoslovak Journal of Physics 53, 1079 (2003)

    A. Mostafazadeh, Czechoslovak Journal of Physics 53, 1079 (2003). 15

    work page 2003

  16. [16]

    Gopalakrishnan and M

    S. Gopalakrishnan and M. J. Gullans, Physical Review Letters 126, 170503 (2021)

    work page 2021

  17. [17]

    Matsumoto, K

    N. Matsumoto, K. Kawabata, Y. Ashida, S. Furukawa, and M. Ueda, Phys. Rev. Lett. 125, 260601 (2020)

    work page 2020

  18. [18]

    Y. Li, X. Chen, and M. P. A. Fisher, Phys. Rev. B 98, 205136 (2018)

    work page 2018

  19. [19]

    Skinner, J

    B. Skinner, J. Ruhman, and A. Nahum, Phys. Rev. X 9, 031009 (2019)

    work page 2019

  20. [20]

    A. Chan, R. M. Nandkishore, M. Pretko, and G. Smith, Phys. Rev. B 99, 224307 (2019)

    work page 2019

  21. [21]

    Y. Li, X. Chen, and M. P. A. Fisher, Phys. Rev. B 100, 134306 (2019)

    work page 2019

  22. [22]

    M. J. Gullans and D. A. Huse, Phys. Rev. X 10, 041020 (2020)

    work page 2020

  23. [23]

    S. Choi, Y. Bao, X.-L. Qi, and E. Altman, Phys. Rev. Lett. 125, 030505 (2020)

    work page 2020

  24. [24]

    Ippoliti, M

    M. Ippoliti, M. J. Gullans, S. Gopalakrishnan, D. A. Huse, and V. Khemani, Phys. Rev. X 11, 011030 (2021)

    work page 2021

  25. [25]

    Recognizing critical lines via entanglement in non-hermitian systems,

    K. D. Agarwal, T. K. Konar, L. G. C. Lakkaraju, and A. S. De, “Recognizing critical lines via entanglement in non-hermitian systems,” (2023), arXiv:2305.08374 [quant-ph]

    work page arXiv 2023

  26. [26]

    Barch, N

    B. Barch, N. Anand, J. Marshall, E. Rieffel, and P. Za- nardi, Phys. Rev. B 108, 134305 (2023)

    work page 2023

  27. [27]

    Hodaei, A

    H. Hodaei, A. U. Hassan, S. Wittek, H. Garcia-Gracia, R. El-Ganainy, D. N. Christodoulides, and M. Kha- javikhan, Nature 548, 187 (2017)

    work page 2017

  28. [28]

    Parto, C

    M. Parto, C. Leefmans, J. Williams, R. M. Gray, and A. Marandi, Light: Science & Applications 14, 6 (2025)

    work page 2025

  29. [29]

    Enhanced quantum sens- ing in time-modulated non-hermitian systems,

    Q.-C. Wu, Y.-H. Zhou, T. Liu, Y.-H. Kang, Q.-P. Su, C.-P. Yang, and Z.-W. Zhou, “Enhanced quantum sens- ing in time-modulated non-hermitian systems,” (2025), arXiv:2503.16217 [quant-ph]

    work page arXiv 2025

  30. [30]

    Obser- vation of a non-hermitian supersonic mode,

    Y. Zhang, J. Carrasquilla, and Y. B. Kim, “Obser- vation of a non-hermitian supersonic mode,” (2024), arXiv:2406.15557 [quant-ph]

    work page arXiv 2024

  31. [31]

    D. S. Abrams and S. Lloyd, Physical Review Letters 81, 3992 (1998)

    work page 1998

  32. [32]

    Mochizuki and R

    K. Mochizuki and R. Hamazaki, Phys. Rev. Res. 5, 013177 (2023)

    work page 2023

  33. [33]

    Quantum computing, postselection, and probabilistic polynomial-time,

    S. Aaronson, “Quantum computing, postselection, and probabilistic polynomial-time,” (2004), arXiv:quant- ph/0412187 [quant-ph]

    work page arXiv 2004

  34. [34]

    Bernstein and U

    E. Bernstein and U. Vazirani, SIAM J. Comput. 26, 1411 (1997)

    work page 1997

  35. [35]

    The Computational Complexity of Linear Optics

    S. Aaronson and A. Arkhipov, “The computational com- plexity of linear optics,” (2010), arXiv:1011.3245 [quant- ph]

    work page internal anchor Pith review Pith/arXiv arXiv 2010

  36. [36]

    K. W. Yip, T. Albash, and D. A. Lidar, Physical Review A 97, 022116 (2018)

    work page 2018

  37. [37]

    S. Sang, Z. Li, T. H. Hsieh, and B. Yoshida, PRX Quan- tum 4, 040332 (2023)

    work page 2023

  38. [38]

    Barch, Phys

    B. Barch, Phys. Rev. B 110, 094307 (2024)

    work page 2024

  39. [39]

    Lee, M.-H

    Y.-C. Lee, M.-H. Hsieh, S. T. Flammia, and R.-K. Lee, Phys. Rev. Lett. 112, 130404 (2014)

    work page 2014

  40. [40]

    D´ ora and C

    B. D´ ora and C. P. Moca, Physical Review Letters 124, 136802 (2020)

    work page 2020

  41. [41]

    Turkeshi and M

    X. Turkeshi and M. Schir´ o, Phys. Rev. B 107, L020403 (2023)

    work page 2023

  42. [42]

    T. J. Osborne, Phys. Rev. Lett. 97, 157202 (2006)

    work page 2006

  43. [43]

    M. B. Hastings, Physical Review Letters 103 (2009), 10.1103/physrevlett.103.050502

    work page doi:10.1103/physrevlett.103.050502 2009

  44. [44]

    T. A. Brun, American Journal of Physics 70, 719 (2002)

    work page 2002

  45. [45]

    Lindblad, Communications in Mathematical Physics 48, 119 (1976)

    G. Lindblad, Communications in Mathematical Physics 48, 119 (1976)

    work page 1976

  46. [46]

    Alicki and K

    R. Alicki and K. Lendi, Quantum Dynamical Semi- groups and Applications , Lecture Notes in Physics No. 717 (Springer-Verlag, Berlin ; New York, 2007)

    work page 2007

  47. [47]

    Breuer and F

    H.-P. Breuer and F. Petruccione, The Theory of Open Quantum Systems (Oxford University Press, Oxford ; New York, 2002)

    work page 2002

  48. [48]

    Fring and M

    A. Fring and M. H. Y. Moussa, Phys. Rev. A 93, 042114 (2016)

    work page 2016

  49. [49]

    F. J. Dyson, Phys. Rev. 102, 1230 (1956)

    work page 1956

  50. [50]

    Papadimitriou, Computational Complexity (Addison Wesley Longman, Reading, Massachusetts, 1995)

    C. Papadimitriou, Computational Complexity (Addison Wesley Longman, Reading, Massachusetts, 1995)

    work page 1995

  51. [51]

    Kitaev, A.H

    A.Yu. Kitaev, A.H. Shen, M.N. Vyalyi, Classical and Quantum Computation , Graduate Studies in Mathemat- ics, Vol. 47 (American Mathematical Society, Providence, RI, 2000)

    work page 2000

  52. [52]

    Arora and B

    S. Arora and B. Barak, Computational Complexity: A Modern Approach (Cambridge University Press, Cam- bridge, 2009)

    work page 2009

  53. [53]

    Aaronson and L

    S. Aaronson and L. Chen, in Proceedings of the 32nd Computational Complexity Conference , CCC ’17 (Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, DEU, 2017)

    work page 2017

  54. [54]

    Aaronson and A

    S. Aaronson and A. Ambainis, in Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, STOC ’15 (Association for Computing Ma- chinery, New York, NY, USA, 2015) pp. 307–316

    work page 2015

  55. [55]

    A Note on Oracle Separations for BQP

    L. Chen, “A note on oracle separations for bqp,” (2016), arXiv:1605.00619 [quant-ph]

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  56. [56]

    A. W. Harrow and A. Montanaro, Nature 549, 203 EP (2017)

    work page 2017

  57. [57]

    Y. Han, L. A. Hemaspaandra, and T. Thier- auf, SIAM Journal on Computing 26, 59 (1997), https://doi.org/10.1137/S0097539792240467

    work page doi:10.1137/s0097539792240467 1997

  58. [58]

    The Equivalence of Sampling and Searching

    S. Aaronson, “The equivalence of sampling and search- ing,” (2010), arXiv:1009.5104 [quant-ph]

    work page internal anchor Pith review Pith/arXiv arXiv 2010

  59. [59]

    Toda, SIAM J

    S. Toda, SIAM J. Comput. 20, 865 (1991)

    work page 1991

  60. [60]

    M. J. Bremner, R. Jozsa, and D. J. Shepherd, Proceed- ings of the Royal Society A: Mathematical, Physical and Engineering Sciences 467, 459 (2011)

    work page 2011

  61. [61]

    Van Den Nest, Quantum Info

    M. Van Den Nest, Quantum Info. Comput. 10, 258 (2010)

    work page 2010

  62. [62]

    T. H. Johnson, J. D. Biamonte, S. R. Clark, and D. Jaksch, Scientific Reports 3 (2013), 10.1038/srep01235

    work page doi:10.1038/srep01235 2013

  63. [63]

    Aloisio, G

    I. Aloisio, G. White, C. Hill, and K. Modi, PRX Quan- tum 4, 020310 (2023)

    work page 2023

  64. [64]

    A. M. Childs, Y. Su, M. C. Tran, N. Wiebe, and S. Zhu, Phys. Rev. X 11, 011020 (2021)

    work page 2021

  65. [65]

    Karuvade, A

    S. Karuvade, A. Alase, and B. C. Sanders, Phys. Rev. Res. 4, 013016 (2022)

    work page 2022

  66. [66]

    The Heisenberg Representation of Quantum Computers

    D. Gottesman, “The heisenberg representation of quan- tum computers,” (1998), arXiv:quant-ph/9807006 [quant-ph]

    work page internal anchor Pith review Pith/arXiv arXiv 1998

  67. [67]

    Classical simulation complexity of extended Clifford circuits

    R. Jozsa and M. V. den Nest, “Classical simula- tion complexity of extended clifford circuits,” (2013), arXiv:1305.6190 [quant-ph]

    work page internal anchor Pith review Pith/arXiv arXiv 2013

  68. [68]

    Anders and H

    S. Anders and H. J. Briegel, Phys. Rev. A 73, 022334 (2006)

    work page 2006

  69. [69]

    Valiant, SIAM J

    L.G. Valiant, SIAM J. on Computing 31, 1229 (2002)

    work page 2002

  70. [70]

    Jozsa and A

    R. Jozsa and A. Miyake, Proceedings of the Royal Soci- ety A: Mathematical, Physical and Engineering Sciences 464, 3089 (2008). 16

    work page 2008

  71. [71]

    Shtanko, A

    O. Shtanko, A. Deshpande, P. S. Julienne, and A. V. Gorshkov, PRX Quantum 2, 030350 (2021)

    work page 2021

  72. [72]

    Ex- tending simulability of cliffords and matchgates,

    A. M. Projansky, J. Necaise, and J. D. Whitfield, “Ex- tending simulability of cliffords and matchgates,” (2024), arXiv:2410.10068 [quant-ph]

    work page arXiv 2024

  73. [73]

    Cleve and C

    R. Cleve and C. Wang, in 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 80, edited by I. Chatzigiannakis, P. Indyk, F. Kuhn, and A. Muscholl (Schloss Dagstuhl – Leibniz- Zentrum f¨ ur Informatik, Dagstuhl, Germany, 2017) pp. 17:1–17:14

    work page 2017

  74. [74]

    Z. Ding, X. Li, and L. Lin, PRX Quantum 5, 020332 (2024)

    work page 2024

  75. [75]

    I. L. Paiva, A. Te’eni, B. Y. Peled, E. Cohen, and Y. Aharonov, Communications Physics 5 (2022), 10.1038/s42005-022-01081-0

    work page doi:10.1038/s42005-022-01081-0 2022

  76. [76]

    Fan and A

    K. Fan and A. J. Hoffman, Proceedings of the American Mathematical Society 6, 111 (1955)

    work page 1955