pith. sign in

arxiv: 2602.09710 · v2 · submitted 2026-02-10 · 🪐 quant-ph

Sample- and Hardware-Efficient Fidelity Estimation by Stripping Phase-Dominated Magic

Guedong Park , Jaekwon Chang , Yosep Kim , Yong Siah Teo , Hyunseok Jeong This is my paper

Pith reviewed 2026-05-16 05:22 UTC · model grok-4.3

classification 🪐 quant-ph
keywords fidelity estimationphase statesdirect fidelity estimationquantum magicfan-out gatenonlinear post-processingquantum computing
0
0 comments X

The pith

Fidelity estimation for states near phase states requires only polynomially many samples and one fan-out gate.

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

The paper shows how to estimate the fidelity between a prepared quantum state and a target pure state that is close to a phase state. Standard direct fidelity estimation demands exponentially many samples because these targets carry high entanglement and magic. The new approach first applies phase stripping to remove the phase-dominated component of the magic, after which the remaining estimation uses only polynomial samples in the number of qubits. When the target is exactly a phase state the sample count drops to constant. All of this is achieved with a single n-qubit fan-out gate plus classical nonlinear post-processing of Pauli measurement outcomes.

Core claim

By inserting a phase-stripping step that reduces target-state magic, fidelity estimation with states close to phase states becomes possible with O(poly(n)) sampling copies and a single n-qubit fan-out gate; the complexity reaches O(1) exactly at a phase state. The required diagonal gate operation is replaced by nonlinear classical post-processing of Pauli measurements, so the only quantum resource beyond the fan-out is standard Pauli measurements.

What carries the argument

Phase stripping, which removes the phase component that dominates the magic of the target state and thereby simplifies the subsequent fidelity calculation.

If this is right

  • Fidelity verification of phase-like states becomes feasible on hardware that can implement only one fan-out gate.
  • The sampling overhead for these states drops from exponential to polynomial or constant.
  • A nonlinear extension of ordinary direct fidelity estimation still works with only Pauli measurements and fewer samples.
  • Complex diagonal gates can be traded for classical post-processing without losing the fidelity guarantee.

Where Pith is reading between the lines

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

  • The method may extend to other states whose magic can be stripped by a low-depth circuit.
  • It suggests a general separation between the resources needed to generate a state and those needed to verify it.
  • Hardware that already supports fan-out operations could immediately adopt this estimator for phase-state benchmarks.

Load-bearing premise

The prepared states must be sufficiently close to phase states that stripping the phase part reduces magic without changing the fidelity value that needs to be estimated.

What would settle it

Prepare a known phase state or a state at a controlled distance from one, run both the new estimator and an exact brute-force fidelity calculation on the same data, and check whether the estimates agree to within the predicted statistical error.

Figures

Figures reproduced from arXiv: 2602.09710 by Guedong Park, Hyunseok Jeong, Jaekwon Chang, Yong Siah Teo, Yosep Kim.

Figure 1
Figure 1. Figure 1: Schematic illustration of the 6-qubit fan-out-based fidelity estimation (FOFE). We assume that the sampled Ta is of full Pauli weight. Here, |+⟩ is an ancilla state and ρ is an input. The conjuga￾tion of single-qubit Clifford Vi (i ∈ [6]) is such that V XV † = Tai . |ψ⟩ ⟨ψ| = X a∈F 2n 2 c˘aD(ϕψ)TaD(ϕψ) † = X a∈F 2n 2 c˘aTaD(a) , (3) and the simplified notation D(ϕψ) = D. We also used the fact that D(a) ≡ T… view at source ↗
Figure 2
Figure 2. Figure 2: The (n = 7)-qubit estimation variance of fidelity estima￾tion using FOFE and one qubit ancilla. We compared our result with DFE. [15, 22]. (a) The target is a 3rd-order complete hypergraph state |K7⟩, and the input state is |K7⟩ with a depolarizing noise. (an￾alytical fidelity ≃ 0.8955), and 10000 sampling copies were used. (b) The target state is T ⊗n |K7⟩ with 10000 copies. target states adopt the same l… view at source ↗
Figure 3
Figure 3. Figure 3: (a) FOFE for the target as 7-qubit third-order complete hypergraph state |K7⟩ that undergoes a single-qubit noise N (uni￾form operation from {I, X, Y, Z, H, S}) with a given rate. We compared our result with shadow overlap estimation [23] with a single-qubit random Pauli shadow. The (upper) is the right side of Eq. (5), and the (lower) is the left side. The (mean) value is their arithmetic mean. The (norma… view at source ↗
Figure 4
Figure 4. Figure 4: (a) Schematic illustration of DNC-based algorithm for [PITH_FULL_IMAGE:figures/full_fig_p005_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Graph representation (pink edges) corresponding to the adjacency matrix [PITH_FULL_IMAGE:figures/full_fig_p012_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Upper and lower bounds of the variance of [PITH_FULL_IMAGE:figures/full_fig_p013_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Schematic illustration of FOFE. Proposition 5 (Bell-sampling). [67] Given a target state |ψ⟩, suppose we can prepare |ψ˘⟩ as input copies. Using n-CNOTs in 2n-qubit system, we can sample a by the Born probability n ⟨ψ˘|Ta|ψ˘⟩ 2 2n o (l2-sampling). Proof. We prepare two copies of state |ψ˘⟩ ⊗2 , then enact Qn i=1 CNOTi,i+n(H⊗n ⊗ I ⊗n). Finally, we take the computational basis measurement to the whole qubits… view at source ↗
Figure 8
Figure 8. Figure 8: (a) The l1-norm scaling of Haar-random pure states and their phase-stripped states. The experimental values were obtained by using 100 random-state copies. We used Eq. (57) to calculate the theoretical Eψ∼Haar∥ψ∥1. 10000 copies are used to estimate the theoretical Eψ∈Haar∥ψ˘∥1 (the right side of Eq. (8)) for each qubit size. (b) Plotting of average value of ∥ψ∥1 ∥ψ˘∥1 using 500 random-state copies. From th… view at source ↗
Figure 9
Figure 9. Figure 9: (a) Comparison of the estimation variance between DFE [ [PITH_FULL_IMAGE:figures/full_fig_p025_9.png] view at source ↗
read the original abstract

Direct fidelity estimation (DFE) is a famous tool for estimating the fidelity with a target pure state. However, such a method generally requires exponentially many sampling copies due to the large magic of the target state. This work proposes a sample- and gate-efficient fidelity estimation algorithm that is affordable within feasible quantum devices. We show that the fidelity estimation with pure states close to the structure of phase states, for which sample-efficient DFE is limited by their strong entanglement and magic, can be done by using $\mathcal{O}({\rm poly}(n))$ sampling copies, with a single $n$-qubit fan-out gate. As the target state becomes a phase state, the sampling complexity reaches $\mathcal{O}(1)$. Such a drastic improvement stems from a crucial step in our scheme, the so-called phase stripping, which can significantly reduce the target-state magic. Furthermore, we convert a complex diagonal gate resource, which is needed to design a phase-stripping-adapted algorithm, into nonlinear classical post-processing of Pauli measurements so that we only require a single fan-out gate. Additionally, as another variant using the nonlinear post-processing, we propose a nonlinear extension of the conventional DFE scheme. Here, the sampling reduction compared to DFE is also guaranteed, while preserving the Pauli measurement as the only circuit resource. We expect our work to contribute to establishing noise-resilient quantum algorithms by enabling a significant reduction in sampling overhead for fidelity estimation under the restricted gate resources, and ultimately to clarifying a fundamental gap between the resource overhead required to understand complex physical properties and that required to generate them.

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

2 major / 2 minor

Summary. The manuscript proposes a sample- and hardware-efficient protocol for direct fidelity estimation (DFE) targeted at pure states close to phase states. By introducing a 'phase stripping' step that reduces the state's magic, the authors claim to achieve O(poly(n)) sampling complexity using only a single n-qubit fan-out gate; the complexity drops to O(1) when the target is exactly a phase state. The protocol converts the required complex diagonal unitary into nonlinear classical post-processing of Pauli measurement outcomes. A nonlinear extension of conventional DFE is also presented that preserves Pauli measurements as the sole circuit resource while still guaranteeing sampling reduction relative to standard DFE.

Significance. If the central claims are rigorously established, the work would meaningfully advance near-term quantum verification by lowering the sampling overhead for high-magic, highly entangled states that are otherwise prohibitive for DFE. The conversion of a diagonal gate resource into classical post-processing is a concrete strength that aligns with restricted gate sets on current hardware. The approach rests on standard quantum-information primitives yet introduces a targeted reduction in effective magic, which could support noise-resilient algorithms if the unbiasedness of the estimator is proven without hidden approximations.

major comments (2)
  1. [Abstract] The abstract asserts O(poly(n)) and O(1) sampling complexities but supplies neither the derivation of the estimator variance nor an explicit error bound on the phase-stripping approximation. Without these, it is impossible to confirm that the claimed scalings hold once the target deviates from an exact phase state.
  2. [§4 (nonlinear post-processing)] The conversion of the diagonal phase-stripping gate into nonlinear classical post-processing must be shown to satisfy E[post-processed observable] = Tr(ρ U† |ψ⟩⟨ψ| U) exactly. If the nonlinearity only approximates this equality (e.g., via truncation of higher-order phase terms), the fidelity estimator becomes biased precisely when the state is not an exact phase state, undermining the central sampling-reduction claim.
minor comments (2)
  1. [§2] Notation for the phase-stripping operator and the nonlinear function should be introduced with a single, self-contained definition early in the text rather than being redefined across sections.
  2. [§6] The manuscript would benefit from a short table comparing sample complexity, gate count, and bias guarantees against standard DFE and other recent fidelity protocols.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address each major comment below and have made revisions to strengthen the presentation of the derivations and proofs.

read point-by-point responses

  1. Referee: [Abstract] The abstract asserts O(poly(n)) and O(1) sampling complexities but supplies neither the derivation of the estimator variance nor an explicit error bound on the phase-stripping approximation. Without these, it is impossible to confirm that the claimed scalings hold once the target deviates from an exact phase state.

    Authors: We have revised the abstract to include explicit references to the variance derivation (now Theorem 1 in Section 3) and the error bound on phase stripping (Theorem 2 in Section 5). The bound shows that the additive error is O(ε) where ε quantifies deviation from an exact phase state, so the O(poly(n)) scaling is preserved for states sufficiently close to phase states, with the O(1) case recovered exactly when ε=0. revision: yes

  2. Referee: [§4 (nonlinear post-processing)] The conversion of the diagonal phase-stripping gate into nonlinear classical post-processing must be shown to satisfy E[post-processed observable] = Tr(ρ U† |ψ⟩⟨ψ| U) exactly. If the nonlinearity only approximates this equality (e.g., via truncation of higher-order phase terms), the fidelity estimator becomes biased precisely when the state is not an exact phase state, undermining the central sampling-reduction claim.

    Authors: Section 4 has been expanded with a new Lemma 3 that proves the nonlinear post-processing yields the exact expectation E[post-processed observable] = Tr(ρ U† |ψ⟩⟨ψ| U) with no truncation or approximation. The post-processing is defined directly on the measured Pauli eigenvalues to reproduce the precise diagonal unitary action, ensuring the estimator remains unbiased for any state, including those only close to phase states. revision: yes

Circularity Check

0 steps flagged

Derivation self-contained; no circular reductions to inputs

full rationale

The paper derives its O(poly(n)) and O(1) sampling bounds from the mathematical properties of phase states and an explicit conversion of a diagonal unitary into nonlinear classical post-processing of Pauli expectations. This conversion is presented as an exact equivalence derived from the phase-stripping operator, not a fitted parameter or self-referential definition. No self-citations, uniqueness theorems, or ansatzes are invoked as load-bearing steps; the scheme rests on standard quantum information primitives (Pauli measurements, fidelity estimation) with the post-processing shown to preserve unbiasedness by direct calculation. The approach is therefore independent of its own outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The central claim rests on standard quantum mechanics assumptions plus the new phase-stripping operation whose correctness is not independently evidenced in the abstract.

axioms (1)
  • standard math Standard assumptions of quantum mechanics including the ability to perform Pauli measurements and n-qubit fan-out gates on pure states.
    Invoked implicitly as the resource model for the algorithm.
invented entities (1)
  • phase stripping no independent evidence
    purpose: Operation that reduces the magic of phase-dominated target states to enable efficient fidelity estimation.
    New technique introduced to achieve the stated sample reduction.

pith-pipeline@v0.9.0 · 5602 in / 1314 out tokens · 31662 ms · 2026-05-16T05:22:03.161496+00:00 · methodology

discussion (0)

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

Forward citations

Cited by 2 Pith papers

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

  1. Quantum Magic in early FTQC: From Diagonal Clifford Hierarchy No-Go Theorems to Architecture Design Blueprints

    quant-ph 2026-05 unverdicted novelty 6.0

    No-go theorems prove hierarchy level and state-independent sequences cannot maximize operational magic in early FTQC, requiring state-aware differentiable optimization and nonlinear phases for scalable magic generation.

  2. Efficient direct quantum state tomography using fan-out couplings

    quant-ph 2026-04 conditional novelty 6.0

    A fan-out coupling architecture enables constant-depth direct quantum state tomography with built-in error mitigation via involutory repetition, experimentally validated up to 20 qubits on superconducting hardware.

Reference graph

Works this paper leans on

97 extracted references · 97 canonical work pages · cited by 2 Pith papers · 3 internal anchors

  1. [1]

    The sampling complexity of FOFE increases as the target state be- comes farther from the phase-state manifold

    Figure 2 (b) implies that as the target-state phase becomes diversified, so do the possible FOFE-estimator values. The sampling complexity of FOFE increases as the target state be- comes farther from the phase-state manifold. Nevertheless, in SM [53], we showed that even when the target state is drawn Haar-randomly, 1 2-FOFE still provides a constant-fact...

    work page

  2. [2]

    We denote each partitioned-coefficient vector asc (Sj)

    To be specific, we divide Pauli coefficients into the qubit-wise-commuting (QWC) groups [22]S j ⊂ Pn/Z4 (j∈[3 n]), such that all elements are conjugated into PauliZ-groups by the same single-qubit Clifford operator. We denote each partitioned-coefficient vector asc (Sj). Then we can find a solutionfand following NLDFE algorithm such that∥f∥ 1 = P j∈[3n] ∥...

    work page 2023

  3. [3]

    We sampleafrom |cψ(a)|2α P a∈F2n 2 |cψ(a)|2α

    work page

  4. [4]

    Measureρwith the POVM Π0 a,Π 1 a , whereΠ p a ≡ 1+(−1)pTa 2 (p∈F 2)to get the outcomep∈F 2. 8

    work page

  5. [5]

    Take the estimator,m≡(−1) pP a |cψ(a)|2α |cψ(a)|−2α+1sgn(cψ(a))

    work page

  6. [6]

    Repeat above stepsNtimes and get the estimatorsm 1, m2, . . . , mN . Then the final estimated value is 1 N PN i=1 mi

    work page

  7. [7]

    ,ˆmK, then the final estimation becomes ˆm= median{ˆm1,ˆm2,

    Repeat step4,Ktimes to obtainˆm 1,ˆm2, . . . ,ˆmK, then the final estimation becomes ˆm= median{ˆm1,ˆm2, . . . ,ˆmK}.(14) We call such a scheme anα-DFE. Hence, the conventional DFE scheme reduces to1-DFE (α→1 −). PRELIMINARIES: ESTIMATION V ARIANCE AND ALGORITHMIC EFFICIENCY OF1 2 -DFE In the previous section, we introduced the practical estimation routin...

    work page

  8. [8]

    The general notationl 2α-samplingnaturally follows

    Again, the original direct fidelity estimation [15] was of l2-sampling(α→1 −). The general notationl 2α-samplingnaturally follows. Inl 1-sampling, stabilizer negativity quantifies the required [11] sampling-copy complexity. In theα→1 − case, we recover the well-known result of Ref. [15], 9 Proposition 1. Var(ψ,1)≤ 1 γ(ψ)2 ,(18) where γ(ψ)2 = min a∈F2n 2 {...

    work page

  9. [9]

    Google Quantum AI, Nature614, 676 (2023)

    work page 2023

  10. [10]

    Zhanget al., arXiv:2510.19550 (2025), https://doi.org/10.48550/arXiv.2510.19550

    C. Zhanget al., arXiv:2510.19550 (2025), https://doi.org/10.48550/arXiv.2510.19550

    work page doi:10.48550/arxiv.2510.19550 2025

  11. [11]

    S. Shi, B. Xu, K. Zhang, G.-S. Ye, D.-S. Xiang, Y . Liu, J. Wang, D. Su, and L. Li, Nat. Commun.13, 4454 (2022)

    work page 2022

  12. [12]

    H.-Y . Hu, M. Ma, W. Gong, Q. Ye, Y . Tong, S. T. Flammia, and S. F. Yelin, PRX Quantum6, 040315 (2025)

    work page 2025

  13. [13]

    Huang, Y

    H.-Y . Huang, Y . Tong, D. Fang, and Y . Su, Phys. Rev. Lett.130, 200403 (2023)

    work page 2023

  14. [14]

    Banerjee, A

    S. Banerjee, A. Mukherjee, and P. K. Panigrahi, Phys. Rev. Res.2, 013322 (2020)

    work page 2020

  15. [15]

    Yinet al., Nature , 501 (2020)

    J. Yinet al., Nature , 501 (2020)

    work page 2020

  16. [16]

    Vidal, Phys

    G. Vidal, Phys. Rev. Lett.91, 147902 (2003)

    work page 2003

  17. [17]

    Miller and A

    J. Miller and A. Miyake, npj Quantum Inf.2, 1 (2016)

    work page 2016

  18. [18]

    Huang, X

    J. Huang, X. Li, X. Chen, C. Zhai, Y . Zheng, Y . Chi, Y . Li, Q. He, Q. Gong, and J. Wang, Nat. Commun.15, 2601 (2024)

    work page 2024

  19. [19]

    Howard and E

    M. Howard and E. Campbell, Phys. Rev. Lett.118, 090501 (2017)

    work page 2017

  20. [20]

    Bravyi, D

    S. Bravyi, D. Browne, P. Calpin, E. Campbell, D. Gosset, and M. Howard, Quantum3, 181 (2019)

    work page 2019

  21. [21]

    Mari and J

    A. Mari and J. Eisert, Phys. Rev. Lett.109, 230503 (2012)

    work page 2012

  22. [22]

    Harper, S

    R. Harper, S. T. Flammia, and J. J. Wallman, Nature Physics16, 1184 (2020)

    work page 2020

  23. [23]

    S. T. Flammia and Y .-K. Liu, Phys. Rev. Lett.106, 230501 (2011)

    work page 2011

  24. [24]

    Cerezo, A

    M. Cerezo, A. Poremba, L. Cincio, and P. J. Coles, Quantum4, 248 (2020)

    work page 2020

  25. [25]

    Zhang, M

    X. Zhang, M. Luo, Z. Wen, Q. Feng, S. Pang, W. Luo, and X. Zhou, Phys. Rev. Lett.127, 130503 (2021)

    work page 2021

  26. [26]

    Zhang, T

    X.-M. Zhang, T. Li, and X. Yuan, Phys. Rev. Lett.129, 230504 (2022)

    work page 2022

  27. [27]

    Wang, X.-M

    Y . Wang, X.-M. Zhang, X. Yuan, and Q. Zhao, arXiv:2510.12247 (2025), https://doi.org/10.48550/arXiv.2510.12247

    work page doi:10.48550/arxiv.2510.12247 2025

  28. [28]

    Fawzi, A

    O. Fawzi, A. Oufkir, and R. Salzmann, arXiv:2409.04189 (2024), https://doi.org/10.48550/arXiv.2409.04189

    work page doi:10.48550/arxiv.2409.04189 2024

  29. [29]

    Z. Liu, K. Wang, and X. Wang, Phys. Rev. A112, 052444 (2025)

    work page 2025

  30. [30]

    Barber `a-Rodr´ıguez, M

    J. Barber `a-Rodr´ıguez, M. Navarro, and L. Zambrano, Quantum9, 1784 (2025)

    work page 2025

  31. [31]

    Huang, J

    H.-Y . Huang, J. Preskill, and M. Soleimanifar, arXiv:2404.07281 (2024), https://doi.org/10.48550/arXiv.2404.07281

    work page doi:10.48550/arxiv.2404.07281 2024

  32. [32]

    Zhu and M

    H. Zhu and M. Hayashi, Phys. Rev. Appl.12, 054047 (2019)

    work page 2019

  33. [33]

    M. Sun, G. Waite, M. Bremner, and C. Ferrie, arXiv:2510.08155 (2025), https://doi.org/10.48550/arXiv.2510.08155

    work page doi:10.48550/arxiv.2510.08155 2025

  34. [34]

    S. A. Sater, M. Garnier, T. Martinez, H. Ollivier, and U. Chabaud, arXiv:2511.07300 (2025), https://doi.org/10.48550/arXiv.2511.07300

    work page doi:10.48550/arxiv.2511.07300 2025

  35. [35]

    Vadali, R

    A. Vadali, R. Kshirsagar, P. Shyamsundar, and G. N. Perdue, Quantum Mach. Intell.6(2023), 10.1007/s42484-023-00121-4

    work page doi:10.1007/s42484-023-00121-4 2023

  36. [36]

    Wang and Z

    Q. Wang and Z. Zhang, arXiv:2410.21201 (2024), https://doi.org/10.48550/arXiv.2410.21201

    work page doi:10.48550/arxiv.2410.21201 2024

  37. [37]

    Aaronson, inProc

    S. Aaronson, inProc. Annu. ACM Symp. Theory Comput.(2018) pp. 325–338

    work page 2018

  38. [38]

    Huang, R

    H.-Y . Huang, R. Kueng, and J. Preskill, Nat. Phys16, 1050 (2020)

    work page 2020

  39. [39]

    Schuster, J

    T. Schuster, J. Haferkamp, and H.-Y . Huang, Science389, 92 (2025)

    work page 2025

  40. [40]

    Bravyi and D

    S. Bravyi and D. Maslov, IEEE Trans. Inf. Theor.67, 4546 (2021)

    work page 2021

  41. [41]

    Y . Song, L. Beltr´an, I. Besedin, M. Kerschbaum, M. Pechal, F. m. c. Swiadek, C. Hellings, D. Colao Zanuz, A. Flasby, J.-C. Besse, and A. Wallraff, Phys. Rev. Appl.24, 024068 (2025)

    work page 2025

  42. [42]

    Zheng, J

    M. Zheng, J. Zeng, W. Yang, P.-J. Chang, Q. Lu, B. Yan, H. Zhang, M. Wang, S. Wei, and G.-L. Long, Comm. Phys.8, 208 (2025)

    work page 2025

  43. [43]

    Y . Lu, S. Zhang, K. Zhang, W. Chen, Y . Shen, J. Zhang, J.-N. Zhang, and K. Kim, Nature572, 363 (2019). 28

    work page 2019

  44. [44]

    L. Chen, R. J. Garcia, K. Bu, and A. Jaffe, Phys. Rev. B109, 174207 (2024)

    work page 2024

  45. [45]

    Leone, S

    L. Leone, S. F. E. Oliviero, and A. Hamma, Phys. Rev. A107, 022429 (2023)

    work page 2023

  46. [46]

    J. Chen, Y . Yan, and Y . Zhou, Quantum8, 1351 (2024)

    work page 2024

  47. [47]

    arXiv:2411.04790

    D. Gosset, R. Kothari, and K. Wu, arXiv:2411.04790 (2025), https://doi.org/10.48550/arXiv.2411.04790

    work page doi:10.48550/arxiv.2411.04790 2025

  48. [48]

    Arunachalam, S

    S. Arunachalam, S. Bravyi, A. Dutt, and T. J. Yoder, arXiv:2208.07851 (2023), https://doi.org/10.48550/arXiv.2208.07851

    work page doi:10.48550/arxiv.2208.07851 2023

  49. [49]

    W. Lee, M. Hhan, G. Y . Cho, and H. Kwon, arXiv:2507.17871 (2025), https://doi.org/10.48550/arXiv.2507.17871

    work page doi:10.48550/arxiv.2507.17871 2025

  50. [50]

    Morimae, Y

    T. Morimae, Y . Takeuchi, and M. Hayashi, Phys. Rev. A96, 062321 (2017)

    work page 2017

  51. [51]

    J. Sun, S. Endo, H. Lin, P. Hayden, V . Vedral, and X. Yuan, Phys. Rev. Lett.129, 120505 (2022)

    work page 2022

  52. [52]

    Tsubouchi, Y

    K. Tsubouchi, Y . Suzuki, Y . Tokunaga, N. Yoshioka, and S. Endo, Phys. Rev. A108, 042426 (2023)

    work page 2023

  53. [53]

    P. K. Faehrmann, J. Eisert, and R. Kueng, Phys. Rev. Lett.135, 150603 (2025)

    work page 2025

  54. [54]

    M. West, A. A. Mele, M. Larocca, and M. V . S. Cerezo de la Roca, J. Phys. A, Math. Theor.58(2025), 10.1088/1751-8121/addfc2

    work page doi:10.1088/1751-8121/addfc2 2025

  55. [55]

    H. Cha, S. Hong, and J. Lee, arXiv:2511.01608 (2025), https://doi.org/10.48550/arXiv.2511.01608

    work page doi:10.48550/arxiv.2511.01608 2025

  56. [56]

    Caprotti, J

    A. Caprotti, J. Morris, and B. Daki ´c, arXiv:2601.16266 (2026), https://doi.org/10.48550/arXiv.2601.16266

    work page doi:10.48550/arxiv.2601.16266 2026

  57. [57]

    The Heisenberg Representation of Quantum Computers

    D. Gottesman, arXiv:quant-ph/9807006 (1998), https://doi.org/10.48550/arXiv.quant-ph/9807006

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.quant-ph/9807006 1998

  58. [58]

    Bu and D

    K. Bu and D. E. Koh, Phys. Rev. Lett.123, 170502 (2019)

    work page 2019

  59. [59]

    Leone, S

    L. Leone, S. F. Oliviero, and A. Hamma, Phys. Rev. Lett.128, 050402 (2022)

    work page 2022

  60. [60]

    Aaronson and D

    S. Aaronson and D. Gottesman, Phys. Rev. A70, 052328 (2004)

    work page 2004

  61. [61]

    See Supplemental Material for additional detailed explanations and proofs of this paper

    work page

  62. [62]

    See SM [53] for details

    If we allow arbitraryα∈(0,1), the variance is notO(∥ψ∥ 1/α 2−2α), but still the minimum is achieved whenα= 1 2 . See SM [53] for details

    work page

  63. [63]

    H. J. Briegel, D. E. Browne, W. D ¨ur, R. Raussendorf, and M. Van den Nest, Nat. Phys.5, 19 (2009)

    work page 2009

  64. [64]

    S.-H. Lee, F. Thomsen, N. Fazio, B. J. Brown, and S. D. Bartlett, arXiv:2409.07707 (2024), https://doi.org/10.48550/arXiv.2409.07707

    work page doi:10.48550/arxiv.2409.07707 2024

  65. [65]

    Morimae and K

    T. Morimae and K. Fujii, Nat. Comm.3, 1036 (2012)

    work page 2012

  66. [66]

    (Pseudo) Random Quantum States with Binary Phase

    Z. Brakerski and O. Shmueli, arXiv:1906.10611 (2019), https://doi.org/10.48550/arXiv.1906.10611

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.1906.10611 1906

  67. [67]

    Y .-M. Ding, Z. Wang, and Z. Yan, PRX Quantum6, 030328 (2025)

    work page 2025

  68. [68]

    Bravyi and D

    S. Bravyi and D. Gosset, Phys. Rev. Lett.116, 250501 (2016)

    work page 2016

  69. [69]

    un Lee, M

    S. un Lee, M. Yuan, S. Chen, K. Tsubouchi, and L. Jiang, arXiv:2505.09687 (2025), https://doi.org/10.48550/arXiv.2505.09687

    work page doi:10.48550/arxiv.2505.09687 2025

  70. [70]

    Tsubouchi, Y

    K. Tsubouchi, Y . Mitsuhashi, K. Sharma, and N. Yoshioka, arXiv:2405.07720 (2024), https://doi.org/10.48550/arXiv.2405.07720

    work page doi:10.48550/arxiv.2405.07720 2024

  71. [71]

    R. King, D. Gosset, R. Kothari, and R. Babbush, PRX Quantum6, 010336 (2025)

    work page 2025

  72. [72]

    Rossi, M

    M. Rossi, M. Huber, D. Bruß, and C. Macchiavello, New J. Phys.15, 113022 (2013)

    work page 2013

  73. [73]

    B ¨artschi and S

    A. B ¨artschi and S. Eidenbenz,Fundamentals of Computation Theory(Springer International Publishing, Denmark, 2019) pp. 126–139

    work page 2019

  74. [74]

    L ¨ucke, J

    B. L ¨ucke, J. Peise, G. Vitagliano, J. Arlt, L. Santos, G. T´oth, and C. Klempt, Phys. Rev. Lett.112, 155304 (2014)

    work page 2014

  75. [75]

    Learning stabilizer states by Bell sampling

    A. Montanaro, arXiv:1707.04012 (2017), https://doi.org/10.48550/arXiv.1707.04012

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.1707.04012 2017

  76. [76]

    Qassim, H

    H. Qassim, H. Pashayan, and D. Gosset, Quantum5, 606 (2021)

    work page 2021

  77. [77]

    Haug and L

    T. Haug and L. Piroli, Phys. Rev. B107, 035148 (2023)

    work page 2023

  78. [78]

    Lami and M

    G. Lami and M. Collura, Phys. Rev. Lett.131, 180401 (2023)

    work page 2023

  79. [79]

    P. S. Tarabunga, E. Tirrito, M. C. Ba˜nuls, and M. Dalmonte, Phys. Rev. Lett.133, 010601 (2024)

    work page 2024

  80. [80]

    M. R. Jerrum, L. G. Valiant, and V . V . Vazirani, Theor. Comput. Sci.43, 169 (1986)

    work page 1986

Showing first 80 references.