Pith. sign in

REVIEW 3 major objections 4 minor 77 references

Shallow quantum circuit for generating extremely low-entangled approximate state designs

T0 review · 3 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read There exist $n$-qubit $\epsilon$-approximate state $t$-designs whose entanglement, magic, and coherence are $O(\log(t/\epsilon))$ — constant in $n$ for fixed $t$ and $\epsilon$ — generated by ancilla-free circuits of depth $O(t[\log t]^3…

desk verdict A genuinely new low-entanglement state-design construction, but the magic lower bound is false for t=2 and the depth result rests on an open conjecture, so the paper's central claims don't hold as written. read the letter →

arxiv 2507.17871 v3 pith:GQ5S7WXT submitted 2025-07-23 quant-ph cond-mat.stat-mechcond-mat.str-elphysics.comp-ph

Wonjun Lee , Minki Hhan , Gil Young Cho , Hyukjoon Kwon This is my paper · ORCID
classification quant-phcond-mat.stat-mechcond-mat.str-elphysics.comp-ph
keywords approximatestatedesignst-designsentanglementmagiccoherenceshallowquantumcircuitsrandominjectivemapsclassicalshadowtomography
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

This paper establishes that approximate random quantum states can be built with constant resource cost: for any fixed $t$ and $\epsilon$, there exist $n$-qubit $\epsilon$-approximate state $t$-designs whose entanglement, magic, and coherence are all $O(\log(t/\epsilon))$, a quantity independent of the system size $n$. It proves a matching lower bound, so these states saturate the fundamental cost of mimicking Haar randomness. The construction works by taking a $k$-qubit approximate design with $k = O(\log(t/\epsilon))$ and applying a $t$-wise independent random injective map that spreads the design over all $n$ qubits without adding any computational-basis superpositions. The paper further provides ancilla-free shallow circuits, of depth $O(t[\log t]^3 \log n \log(1/\epsilon))$, that generate these states, and shows that the resulting low-superposition structure yields a classical shadow tomography protocol with constant classical post-processing per sample.

What carries the argument

The load-bearing object is the $t$-wise independent random injective map $P$ from $[2^k]$ to $[2^n]$, implemented unitarily by $U_p\lvert b\rangle \otimes \lvert 0^{n-k}\rangle = \lvert p(b)\rangle$. The proof works through unique type states — equal superpositions over $t$ distinct computational basis vectors in the $t$-copy space — whose ensemble average equals the $t$-th moment of Haar-random states up to trace distance $t^2/2^{l-1}$. The map sends $k$-qubit unique type states to a perfectly uniform ensemble of $n$-qubit unique type states, which is exactly the $n$-qubit Haar moment; triangle inequalities then transfer any $k$-qubit design error to the $n$-qubit system. The circuit realization, Algorithm 1 (called the Shallow Depth Bits Randomizer), copies the $k$-qubit register with parallel CNOTs in $O(\log(n/k))$ depth and then randomizes target bits by repeated random $m$-MCX gates with $m = \lceil \log_2 t \rceil$, whose control conditions are sampled independently; the final depth is counted in single-qubit and CNOT gates under all-to-all connectivity. In the ancilla-free version, the depth stated in Theorem 3 is $O(t[\log t]^3 \log n \log(1/\epsilon))$.

What would settle it

Take the random $m$-uniform hypergraph produced by Algorithm 1 for small parameters — say $t = 4$, $\epsilon = 0.1$, $k = \lceil 3 \log_2(t^2/\epsilon) \rceil$, $m = \lceil \log_2 t \rceil$, $\alpha = t \log(1/\epsilon)$ — sample it many times, and compute the chromatic index exactly; if the probability that it exceeds $O(t \log t)$ is not below $\epsilon$, Theorem 3 is refuted. A complementary experiment is to compile the claimed $n=58$, $t=3$, $\epsilon=0.01$ ancilla-free circuit and count its depth after parallelizing commuting MCX gates, expecting depth about 58; a substantially larger depth would contradict the theorem.

Watch

Extended reading notes

Core claim

The central claim is that the dimension of an approximate state design can be expanded for free: applying a $t$-wise independent random injective map to a $k$-qubit $\epsilon$-approximate state $t$-design yields an $n$-qubit $\epsilon'$-approximate state $t$-design with $\epsilon' = \epsilon + t^2/2^{k-1} + t^2/2^{n-1}$ (Lemma 1). Since the map only permutes computational basis states, the output states retain the same support size, $2^k$, so their entanglement, magic, and coherence are bounded by $O(k)$. Taking $k = \lceil \log_2(4t^2/\epsilon) \rceil$ gives an $\epsilon$-approximate design for any $\epsilon \geq 4t^2/2^n$, with all three resources at $O(\log(t/\epsilon))$; Theorem 2 shows this is optimal by proving that any $\epsilon$-approximate state $t$-design has mean entanglement, magic, and coherence at least $\Omega(\log(t/\epsilon))$. The paper then constructs the map by circuits of parallel CNOTs and random multi-controlled-NOT gates, and claims an ancilla-free depth of $O(t[\log t]^3 \log n \log(1/\epsilon))$ — the most efficient among known no-ancilla constructions — plus a shadow-tomography estimator that accesses only $O(1)$ computational-basis matrix elements per sample.

Load-bearing premise

The depth claim of Theorem 3 rests on an unproved conjecture in Supplementary Note 4: that the random hypergraph whose edges are the parallel MCX gates has chromatic index $O(t \log t)$ with failure probability below $\epsilon$; if that conjecture fails, the stated circuit depth is not established.

Editorial extensions

If this is right

  • For fixed $t$ and $\epsilon$, entanglement, magic, and coherence can all be $O(1)$ in $n$, so Haar-like randomness does not force volume-law entanglement.
  • Average channel fidelity can be estimated to error $O(\epsilon)$ with sample complexity independent of $n$, using the approximate 2-design property.
  • The claimed ancilla-free depth $O(t[\log t]^3 \log n \log(1/\epsilon))$ is lower than previous no-ancilla constructions, and for $n=58$, $t=3$, $\epsilon=0.01$ it gives a concrete 58-depth circuit under all-to-all connectivity.
  • Classical shadow tomography with the new estimator uses superpositions between only two computational basis states, lowering classical post-processing by a factor $n^{O(1)}$ and enabling constant-sample certification of almost all pure states.
  • When $t$ and $\epsilon$ scale with $n$ (e.g., $t$ poly(n), $\epsilon$ 1/poly(n)), the lower bound grows to $\Omega(\log n)$, matching the resource scaling known for pseudorandom states.

Reading between the lines

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

  • If the chromatic-index conjecture behind Theorem 3 holds, the same construction may extend to $t$ and $\epsilon$ growing mildly with $n$ while keeping depth quasi-polylogarithmic; the paper only states the conjecture for the regime $\log(1/\epsilon) = o(t \log t)$.
  • The $O(1)$ classical post-processing per shadow sample suggests that replacing the random injective maps with explicit small-bias or $t$-wise independent families could yield deterministic certification protocols, though the paper does not explore this.
  • A direct near-term test is to compile the claimed $n=58$, $t=3$, $\epsilon=0.01$ circuit and measure its actual depth after parallelizing commuting MCX gates; observing depth far above 58 would indicate the conjecture fails, while matching it would support Theorem 3.
  • Because the generated states have low magic and entanglement, circuits preparing them are natural candidates for efficient classical simulation; the paper's construction may therefore sharpen the boundary of quantum advantage for random-state sampling, but this is not claimed by the authors.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 4 minor

Summary. The paper introduces an ensemble of n-qubit states formed by applying a t-wise independent random injective map to a k-qubit approximate state design, where k = O(log(t/epsilon)). It claims that these states form an epsilon-approximate state t-design with O(log(t/epsilon)) entanglement, magic, and coherence, and that these resources saturate matching lower bounds of Omega(log(t/epsilon)). It also claims an ancilla-free shallow circuit of depth O(t[log t]^3 log n log(1/epsilon)), and an application to classical shadow tomography with a low-superposition estimator.

Significance. If the results were correct, the construction would be significant: it would show that random states with system-size-independent resource overhead can mimic the first t moments of the Haar measure, and the shallow-circuit construction would improve on prior work. The shadow-tomography application is also conceptually interesting. However, the saturation claim rests on a lower bound that is false as stated for t = 2, and the circuit-depth claim rests on an explicitly unproved conjecture. The significance is therefore conditional, and the paper in its present form does not establish its central claims.

major comments (3)
  1. [Theorem 2 and SM Note 5] The claimed lower bound on mean magic is false for t = 2. The uniform ensemble of stabilizer states is an exact state 2-design because the Clifford group is a unitary 2-design, and every stabilizer state has stabilizer Renyi entropy M_alpha = 0 for all alpha > 0. Hence this ensemble is an epsilon-approximate 2-design with zero mean magic for any epsilon > 0, contradicting the claimed Omega(log(t/epsilon)) lower bound. The proof fails because for t = 2 the only allowed odd alpha = 1 gives Pi^(2) = SWAP, and tr(SWAP |psi><psi|^⊗2) = 1 for every pure state, so the proposed Hadamard test has no distinguishing power. The theorem must be restricted to t for which 2 alpha = t with odd alpha >= 3, and the counterexample for t = 2 must be addressed before the saturation claim can stand.
  2. [Theorem 3 and SM Note 4] The advertised depth bound O(t[log t]^3 log n log(1/epsilon)) is presented as a proven theorem, but its proof relies on an unproved conjecture. SM Note 4 states: 'We conjecture that in this regime, chi'(H) is upper bounded by O(t log t) with a failure probability smaller than epsilon.' This conjecture is used in Lemma 5 (SM Note 2) to obtain the depth reduction via parallel execution of MCX gates. Since the conjecture is not proved, Theorem 3 is not established as stated; the depth bound should either be proved or explicitly marked as conditional.
  3. [SM Note 6 and Theorem 1] The magic upper bound in Theorem 1 is not proven. SM Note 6 asserts that Lemma S4 of Ref. [14], which is proved for random subset phase states, extends to any state with 2^k computational-basis superpositions, with the phrase 'using the same proof' but no argument. This step is load-bearing for the claim that the constructed states have O(log(t/epsilon)) magic, and the cited lemma does not obviously apply to arbitrary superpositions with arbitrary amplitudes. A proof or a more careful statement is needed.
minor comments (4)
  1. [Algorithm 1 in End Matter] The loop bound log2(n/k) assumes n is a power of two times k; the general case is not discussed.
  2. [Equation (1)] The notation in Eq. (1) is not fully defined: the unitary U in the estimator for the off-diagonal part differs from the measurement unitary used for the diagonal part, and the two should be labeled separately.
  3. [SM Note 2] There is a typo: 't-wist independent' should be 't-wise independent'.
  4. [Table I] The comparison in Table I does not state the epsilon-dependence of the listed protocols, while the main text compares them at fixed epsilon; adding the epsilon scaling would make the comparison more informative.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the construction is self-contained, the lower-bound arguments use standard external facts, and no fitted parameter is renamed as a prediction.

full rationale

The derivation chain is not circular. Lemma 1 expands a k-qubit approximate design by a t-wise independent random injective map, and its proof uses known unique-type-state properties plus a triangle inequality; the n-qubit design property is computed, not assumed as an input. Theorem 1 chooses k = O(log(t/epsilon)) and obtains O(log(t/epsilon)) entanglement, magic, and coherence from the support size, which is an independent upper bound rather than a restatement of the target result. Theorem 2's lower bounds are argued through standard entanglement and stabilizer-Renyi tests following Aaronson et al. and Gu et al.; they do not import the construction or fit parameters. There are no self-citations by the present authors, and no uniqueness theorem from prior work is invoked to force the construction. Two non-circular caveats should be flagged explicitly. First, SM Note 4 contains the statement: 'We conjecture that in this regime, chi'(H) is upper bounded by O(t log t) with a failure probability smaller than epsilon.' Theorem 3's depth claim therefore rests on an unproven conjecture, but a conjecture is a missing proof, not a circular reduction. Second, SM Note 5 derives the magic lower bound from an odd-alpha Hadamard test; for alpha = 1, tr(SWAP |psi><psi|^2) = 1 identically, so the stated Omega(log(t/epsilon)) magic lower bound fails for t = 2. That is a correctness gap in the theorem as stated, not a circularity, because the bound is not equivalent to its input by construction. The shadow-tomography estimator is the standard inverse-channel estimator and its unbiasedness is verified by direct calculation in SM Note 7; no fitted input is relabeled as a prediction. Overall, the paper is self-contained against external benchmarks, and no circular step is exhibited.

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

The paper introduces no new physical entities. The main load-bearing assumptions are standard symmetric-subspace facts, the existence of t-wise independent random injective maps, and an unproved conjecture about parallel MCX execution. The free parameters are proof constants chosen to satisfy inequalities, not fitted to data.

free parameters (2)
  • subsystem size constant c = c = 6 (paper sets k = ceil(3 log2(t^2/epsilon)))
    The proof of t-wise independence of the implemented random injective map requires c >= 5.77 (SM Eq. 48); the paper chooses c = 6 implicitly. The construction's error and resource bounds depend on this choice.
  • MCX rounds parameter beta = beta = O(1), chosen with beta > 1+c for the parallelization regime
    Used in SM Note 4 to set alpha = beta t log(1/epsilon); the depth bound and the parallelization analysis depend on this asymptotic constant.
assumptions (4)
  • standard math Unique type states approximate the Haar moment: TD(rho_Haarl, rho_uniquel) <= t^2/2^(l-1) (Lemma 3).
    Invoked in the proof of Lemma 1 (dimension expansion) and in Theorem 1. This is a known result from symmetric subspace theory (SM Ref [1]).
  • domain assumption t-wise independent random injective maps from [2^k] to [2^n] exist and can be implemented by the described MCX circuit with failure probability below epsilon.
    The construction relies on the existence of t-wise independent injective maps (Refs [32,33]) and on the explicit circuit implementation in Algorithm 1. The proof of the full-rank probability in SM Section 3 supports this, but the depth bound also relies on a conjecture.
  • domain assumption Multi-controlled NOT gates can be implemented in O(m) depth without ancilla and in polylogarithmic depth with one ancilla.
    Used in the depth calculation of Theorem 3 (SM Section 2), citing Ref [6] and Ref [7]. These are external circuit-construction results.
  • ad hoc to paper The chromatic index of the random hypergraph of MCX gates satisfies chi'(H) = O(t log t) with failure probability smaller than epsilon.
    This is explicitly stated as a conjecture in SM Note 4. Theorem 3's depth bound O(t[log t]^3 log n log(1/epsilon)) depends on this unproved statement.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Shallow quantum circuit for generating extremely low-entangled approximate state designs." pith.science (2026). https://pith.science/paper/GQ5S7WXT

@misc{pith2026250717871,
  author       = {Pith},
  title        = {Pith review of: Shallow quantum circuit for generating extremely low-entangled approximate state designs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GQ5S7WXT}},
  note         = {Machine review of arXiv:2507.17871}
}
abstract

Random quantum states have various applications in quantum information science. We discover a new ensemble of quantum states that serve as an $\epsilon$-approximate state $t$-design while possessing extremely low entanglement, magic, and coherence. These resources can reach their theoretical lower bounds, $\Omega(\log (t/\epsilon))$, which are also proven in this work. This implies that for fixed $t$ and $\epsilon$, entanglement, magic, and coherence do not scale with the system size, i.e., $O(1)$ with respect to the total number of qubits $n$. Moreover, we explicitly construct an ancilla-free shallow quantum circuit for generating such states by transforming $k$-qubit approximate state designs into $n$-qubit ones without increasing the support size. The depth of such a quantum circuit, $O(t [\log t]^3 \log n \log(1/\epsilon))$, is the most efficient among existing algorithms without ancilla qubits. A class of quantum circuits proposed in our work offers reduced cost for classical simulation of random quantum states, leading to potential applications in quantum information processing. As a concrete example, we propose classical shadow tomography using an estimator with superpositions between only two states, from which almost all quantum states can be efficiently certified by requiring only $O(1)$ measurements and classical post-processing time.

Figures

Figures reproduced from arXiv: 2507.17871 by the authors.

Figure 1
Figure 1. FIG. 1. Overview of the generation of approximate state designs. (a) States in an ensemble [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. FIG. 2. Circuit for generating [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

77 extracted references · 60 canonical work pages

  1. [47]

    Bittel and L

    L. Bittel and L. Leone, Operational interpretation of the stabilizer entropy (2025), arXiv:2507.22883 [quant-ph] . 7 End Matter Approximate state designs. An ensemble E of n-qubit states forms an approximate state t-design with additive error ϵ if it approximates Haar random states in the following sense: TD ( Eϕ∼E [ |ϕ⟩ ⟨ϕ|⊗t ] ,ρ (t) Haar ) ≤ϵ (6) with ...

    arXiv 2025

  2. [14]

    Arute, K

    F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. Brandao, D. A. Buell, et al. , Quantum supremacy using a programmable superconducting processor, Nature 574, 505 (2019)

    work page 2019

  3. [1]

    D. N. Page, A verage entropy of a subsystem, Phys. Rev. Lett. 71, 1291 (1993)

    work page 1993

  4. [2]

    Hayden, D

    P. Hayden, D. W. Leung, and A. Winter, Aspects of generic entanglement, Commun. Math. Phys. 265, 95 (2006)

    work page 2006

  5. [3]

    Srednicki, Chaos and quantum thermalization, Phys

    M. Srednicki, Chaos and quantum thermalization, Phys. Rev. E 50, 888 (1994)

    1994

  6. [4]

    Yoshida and A

    B. Yoshida and A. Kitaev, Efficient decoding for the hayden-preskill protocol (2017), arXiv:1710.03363 [hep- th]

    arXiv 2017

  7. [5]

    Yoshida and N

    B. Yoshida and N. Y. Yao, Disentangling scrambling and decoherence via quantum teleportation, Phys. Rev. X 9, 011006 (2019)

    work page 2019

  8. [6]

    Piroli, C

    L. Piroli, C. Sünderhauf, and X.-L. Qi, A random unitary circuit model for black hole evaporation, Journal of High Energy Physics 2020, 10.1007/jhep04(2020)063 (2020)

    doi:10.1007/jhep04(2020)063 2020

Show all 77 references
  1. [7]

    Ji, Y.-K

    Z. Ji, Y.-K. Liu, and F. Song, Pseudorandom quan- tum states, in Advances in Cryptology – CRYPTO 2018 , edited by H. Shacham and A. Boldyreva (Springer Inter- national Publishing, Cham, 2018) pp. 126–152

    2018

  2. [8]

    Ananth, L

    P. Ananth, L. Qian, and H. Yuen, Cryptography from pseudorandom quantum states, in Annual International Cryptology Conference (Springer, 2022) pp. 208–236

    2022

  3. [9]

    Kretschmer, L

    W. Kretschmer, L. Qian, M. Sinha, and A. Tal, Quan- tum cryptography in algorithmica, in Proceedings of the 55th Annual ACM Symposium on Theory of Computing (2023) pp. 1589–1602

    2023

  4. [10]

    Knill, D

    E. Knill, D. Leibfried, R. Reichle, J. Britton, R. B. Blakestad, J. D. Jost, C. Langer, R. Ozeri, S. Seidelin, and D. J. Wineland, Randomized benchmarking of quan- tum gates, Phys. Rev. A 77, 012307 (2008)

    2008

  5. [11]

    Huang, R

    H.-Y. Huang, R. Kueng, and J. Preskill, Predicting many properties of a quantum system from very few measure- ments, Nat. Phys. 16, 1050 (2020)

    2020

  6. [12]

    Helsen, I

    J. Helsen, I. Roth, E. Onorati, A. Werner, and J. Eisert, General framework for randomized benchmarking, PRX Quantum 3, 020357 (2022)

    2022

  7. [13]

    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, Characterizing quantum supremacy in near- term devices, Nat. Phys. 14, 595 (2018)

    2018

  8. [15]

    Elben, S

    A. Elben, S. T. Flammia, H.-Y. Huang, R. Kueng, J. Preskill, B. Vermersch, and P. Zoller, The randomized measurement toolbox, Nat. Rev. Phys. 5, 9 (2023)

    2023

  9. [16]

    Emerson, E

    J. Emerson, E. Livine, and S. Lloyd, Convergence con- 6 ditions for random quantum circuits, Phys. Rev. A 72, 060302 (2005)

    2005

  10. [17]

    Oszmaniec, M

    M. Oszmaniec, M. Kotowski, M. Horodecki, and N. Hunter-Jones, Saturation and recurrence of quantum complexity in random local quantum dynamics, Phys. Rev. X 14, 041068 (2024)

    2024

  11. [18]

    Ambainis and J

    A. Ambainis and J. Emerson, Quantum t-designs: t-wise independence in the quantum world, in Twenty-Second Annual IEEE Conference on Computational Complexity (CCC’07) (2007) pp. 129–140

    2007

  12. [20]

    Chamon, E

    C. Chamon, E. R. Mucciolo, A. E. Ruckenstein, and Z.- C. Yang, Fast pseudorandom quantum state generators via inflationary quantum gates, npj Quantum Inf. 10, 37 (2024)

    2024

  13. [21]

    Feng and M

    X. Feng and M. Ippoliti, Dynamics of pseudoen- tanglement, Journal of High Energy Physics 2025, 10.1007/jhep02(2025)128 (2025)

    2025 doi

  14. [23]

    L. Cui, T. Schuster, F. Brandao, and H.-Y. Huang, Unitary designs in nearly optimal depth (2025), arXiv:2507.06216 [quant-ph]

    2025 arXiv

  15. [25]

    T. Haug, K. Bharti, and D. E. Koh, Pseudorandom uni- taries are neither real nor sparse nor noise-robust, Quan- tum 9, 1759 (2025)

    2025

  16. [26]

    Zhang, P

    B. Zhang, P. Xu, X. Chen, and Q. Zhuang, Holographic deep thermalization for secure and efficient quantum ran- dom state generation, Nature Communications 16, 6341 (2025)

    2025

  17. [27]

    F. G. S. L. Brandão, A. W. Harrow, and M. Horodecki, Local random quantum circuits are approximate polynomial-designs, Commun. Math. Phys. 346, 397 (2016)

    2016

  18. [28]

    Haferkamp, Random quantum circuits are approxi- mate unitary t-designs in depth O ( nt5+o(1) ) , Quantum 6, 795 (2022)

    J. Haferkamp, Random quantum circuits are approxi- mate unitary t-designs in depth O ( nt5+o(1) ) , Quantum 6, 795 (2022)

    2022

  19. [29]

    A. W. Harrow and S. Mehraban, Approximate unitary t- designs by short random quantum circuits using Nearest- Neighbor and Long-Range gates, Commun. Math. Phys. 401, 1531 (2023)

    2023

  20. [30]

    W. W. Ho and S. Choi, Exact emergent quantum state designs from quantum chaotic dynamics, Phys. Rev. Lett. 128, 060601 (2022)

    2022

  21. [31]

    J. S. Cotler, D. K. Mark, H.-Y. Huang, F. Hernández, J. Choi, A. L. Shaw, M. Endres, and S. Choi, Emergent quantum state designs from individual many-body wave functions, PRX Quantum 4, 010311 (2023)

    2023

  22. [32]

    N. Alon, A. Andoni, T. Kaufman, K. Matulef, R. Ru- binfeld, and N. Xie, Testing k-wise and almost k-wise independence, in Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing , STOC ’07 (Association for Computing Machinery, New York, NY, USA, 2007) p. 496–505

    2007

  23. [34]

    See supplementary material for further details

  24. [36]

    Baumgratz, M

    T. Baumgratz, M. Cramer, and M. B. Plenio, Quantify- ing coherence, Phys. Rev. Lett. 113, 140401 (2014)

    2014

  25. [37]

    Horodecki, P

    M. Horodecki, P. Horodecki, and R. Horodecki, General teleportation channel, singlet fraction, and quasidistilla- tion, Phys. Rev. A 60, 1888 (1999)

    1999

  26. [38]

    M. A. Nielsen, A simple formula for the average gate fidelity of a quantum dynamical operation, Phys. Lett. A 303, 249 (2002)

    2002

  27. [39]

    S. J. Evered, D. Bluvstein, M. Kalinowski, S. Ebadi, T. Manovitz, H. Zhou, S. H. Li, A. A. Geim, T. T. Wang, N. Maskara, H. Levine, G. Semeghini, M. Greiner, V. Vuletić, and M. D. Lukin, High-fidelity parallel entan- gling gates on a neutral-atom quantum computer, Nature 622, 2...

    2023

  28. [40]

    M. Xue, S. Xu, X. Li, and X. Li, High-fidelity and ro- bust controlled-z gates implemented with rydberg atoms via echoing rapid adiabatic passage, Phys. Rev. A 110, 032619 (2024)

    2024

  29. [41]

    Bluvstein, S

    D. Bluvstein, S. J. Evered, A. A. Geim, S. H. Li, H. Zhou, T. Manovitz, S. Ebadi, M. Cain, M. Kali- nowski, D. Hangleiter, J. P. Bonilla Ataides, N. Maskara, I. Cong, X. Gao, P. Sales Rodriguez, T. Karolyshyn, G. Semeghini, M. J. Gullans, M. Greiner, V. Vuletić, and M. D. Luki...

    2024

  30. [42]

    Bravyi, D

    S. Bravyi, D. Browne, P. Calpin, E. Campbell, D. Gosset, and M. Howard, Simulation of quantum circuits by low- rank stabilizer decompositions, Quantum 3, 181 (2019)

    2019

  31. [43]

    Huang, J

    H.-Y. Huang, J. Preskill, and M. Soleimanifar, Certifying almost all quantum states with few single-qubit measure- ments, in 2024 IEEE 65th Annual Symposium on Foun- dations of Computer Science (FOCS) (IEEE, 2024) pp. 1202–1206

    2024

  32. [44]

    Lange, A

    H. Lange, A. Van de Walle, A. Abedinnia, and A. Bohrdt, From architectures to applications: a review of neural quantum states, Quantum Science and Technology 9, 040501 (2024)

    2024

  33. [45]

    Schollwöck, The density-matrix renormalization group in the age of matrix product states, Annals of Physics 326, 96 (2011) , january 2011 Special Issue

    U. Schollwöck, The density-matrix renormalization group in the age of matrix product states, Annals of Physics 326, 96 (2011) , january 2011 Special Issue

    2011

  34. [46]

    Gupta, W

    M. Gupta, W. He, and R. O’Donnell, Few single- qubit measurements suffice to certify any quantum state (2025), arXiv:2506.11355 [quant-ph]

    2025 arXiv

  35. [48]

    Construction of state t-design from random injective map (proof of Lemma 1 in the main text) 6

  36. [49]

    Quantum circuit implementation of random injective map (proof of Theorem 3 in the main text) 9 Efficient circuit implementation of random injective map for t ≤ 3 11

  37. [50]

    Full rank probability 13

  38. [51]

    Parallel execution of MCX gates 17

  39. [52]

    Lower bounds on entanglement, magic, and coherence (proof of Theorem 2 in the main text) 19

  40. [53]

    Upper bound on magic of ϵ-approximate state t-designs in Theorem 1 19

  41. [54]

    O(1)-entangled shadow estimator (proof of Theorem 4 in the main text) 20 Certification and benchmarking using shadow tomography (proof of Theorem 5 in the main text) 22 Measurement circuit for shadow tomography 25

  42. [55]

    Random MCX

    Application of approximate state design with a fixed ϵ 32 Supplementary References 33 References 33 ∗ wonjun1998@postech.ac.kr † minkihhan@gmail.com ‡ gilyoungcho@kaist.ac.kr § hjkwon@kias.re.kr 1 SUPPLEMENT AR Y FIGURES Supplementary Figure 1: Parallel CNOT gate circuit 1 st i...

  43. [56]

    [ 1, 2], and then, prove Lemma 1 based on it

    Construction of state t-design from random injective map (proof of Lemma 1 in the main text) In this section, we introduce the unique type state introduced in Refs. [ 1, 2], and then, prove Lemma 1 based on it. Let us consider a vector v ∈ [L]t for L = 2l. A type vector type(v...

  44. [57]

    To this end, we first state and prove the following lemmas

    Quantum circuit implementation of random injective map (proof of Theorem 3 in the main text) In this section, we prove Theorem 3 . To this end, we first state and prove the following lemmas. We note that Uf with an exact 2t-wise random function f can be implemented in O(kt) dep...

  45. [58]

    Due to Lemma 5, we can implement Upa using O(t[logt]3 logn log(1/ϵ)) depth circuits without any ancilla bits and ˜O(t[logt]3 logn log(1/ϵ)) depth circuits with ⌈n/k⌉ ancilla bits

    (26) Let Upa with pa ∼ Pa be a unitary operator implementation of a t-wise independent random injective map that mapsρ(t) unique,k toρ(t) unique,n with a failure probability smaller than ϵ/4. Due to Lemma 5, we can implement Upa using O(t[logt]3 logn log(1/ϵ)) depth circuits w...

  46. [59]

    Here, [K]t dist is the set of t distinct integers in [1,K ]

    F ull rank probability Let us assume that we have sampled {xi}t i=1 ∈ [K]t dist uniformly at random with K = 2k. Here, [K]t dist is the set of t distinct integers in [1,K ]. Let α be a positive integer. We then sample sets {Si}α i=1 of m-bits and their values {yi}α i=1 ∈ [Zm 2...

  47. [60]

    Since the weight of s isw, there exist t −w different v vectors havingsTv = 0

    Second, when v has exactly one non-trivial element, then sTv is vanishing if there exists l ∈ [t] such thatvl is one with sl = 0. Since the weight of s isw, there exist t −w different v vectors havingsTv = 0. Third, when v has exactly two non-trivial elements, then sTv is vanis...

  48. [61]

    Additionally, let us set k = 3 log ( t2/ϵ ) , m = logt, and α =βt log(1/ϵ)

    Parallel execution of MCX gates Let us set t> 0, 1 ≥ϵ> 0, and β =O(1). Additionally, let us set k = 3 log ( t2/ϵ ) , m = logt, and α =βt log(1/ϵ). Let us consider an asymptotic limit of 1/ϵ ≫t. Then, we have k ∼ log(1/ϵ) and α ∼βt log(1/ϵ). Let us assume that there are two k-b...

  49. [62]

    For a measure of entanglement, we use the entanglement entropy of any subsystem A such that |A| = Θ(n) with the number of qubits n

    Lower bounds on entanglement, magic, and coherence (proof of Theorem 2 in the main text) In this section, we derive upper and lower bounds for entanglement, magic, and coherence of states in an ensemble E forming ϵ-approximate state t-design. For a measure of entanglement, we ...

  50. [63]

    Upper bound on magic of ϵ-approximate state t-designs in Theorem 1 An upper bound of α-stabilizer Rényi entropy Mα(|ψ⟩) of |ψ⟩ in Esub with the subset dimension K = 2 Θ(log(t/ϵ)) can be obtained using Lemma S4 of Ref. [ 14]. It states that any random subset phase state having ...

  51. [64]

    Let Up with p ∼ P be the unitary operator such that Up |b,a ⟩ = ⏐ ⏐p(b) ⊕ 0ka ⟩ with k-bits k and (n −k)-bits a

    O(1)-entangled shadow estimator (proof of Theorem 4 in the main text) In this section, we drive the shadow estimator for measurement unitary operators E = {V ⊗I ⊗(n−k)Up|V ∈ U (K),p ∈ P (N )} (98) with the system size n, the subsystem size k ≤n,N = 2n,K = 2k, a unitary 3-desig...

  52. [65]

    (152) We can approximate Favg(Λ) by replacing Haar random states to an ensemble E forming an ϵ-approximate state 2-design as ˜Favg(Λ) = Eψ∼E [⟨ψ| Λ(|ψ⟩ ⟨ψ|) |ψ⟩]

    Application of approximate state design with a fixed ϵ An example requiring approximate state design is the average fidelity estimation of a quantum channel Λ defined as Favg(Λ) = Eψ∼Haar [⟨ψ| Λ(|ψ⟩ ⟨ψ|) |ψ⟩]. (152) We can approximate Favg(Λ) by replacing Haar random states to an...

  53. [66]

    A. W. Harrow, The church of the symmetric subspace (2013), arXiv:1308.6595 [quant-ph]

    2013 arXiv

  54. [67]

    Ananth, A

    P. Ananth, A. Gulati, L. Qian, and H. Yuen, Pseudorandom (function-like) quantum state generators: New definitions and applications, in Theory of Cryptography, edited by E. Kiltz and V. Vaikuntanathan (Springer Nature Switzerland, Cham, 2022) pp. 237–265

    2022

  55. [68]

    N. Alon, L. Babai, and A. Itai, A fast and simple randomized parallel algorithm for the maximal independent set problem, Journal of Algorithms 7, 567 (1986)

    1986

  56. [69]

    Metger, A

    T. Metger, A. Poremba, M. Sinha, and H. Yuen, Simple constructions of linear-depth t-designs and pseudorandom unitaries (2024), arXiv:2404.12647 [quant-ph]

    2024 arXiv

  57. [70]

    C.-F. Chen, J. Haah, J. Haferkamp, Y. Liu, T. Metger, and X. Tan, Incompressibility and spectral gaps of random circuits (2024), arXiv:2406.07478 [quant-ph]

    2024 arXiv

  58. [71]

    Gidney, Algorithmic assertions, https://algassert.com/circuits/2015/06/05/Constructing-Large-Controlled-Nots

    C. Gidney, Algorithmic assertions, https://algassert.com/circuits/2015/06/05/Constructing-Large-Controlled-Nots. html

    2015

  59. [72]

    Claudon, J

    B. Claudon, J. Zylberman, C. Feniou, F. Debbasch, A. Peruzzo, and J.-P. Piquemal, Polylogarithmic-depth controlled-NOT gates without ancilla qubits, Nature Communications 15, 5886 (2024)

    2024

  60. [73]

    Schuster, J

    T. Schuster, J. Haferkamp, and H.-Y. Huang, Random unitaries in extremely low depth, Science 389, 92 (2025)

    2025

  61. [74]

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

    2017

  62. [75]

    Kurauskas and K

    V. Kurauskas and K. Rybarczyk, On the chromatic index of random uniform hypergraphs, SIAM Journal on Discrete Mathematics 29, 541 (2015) , https://doi.org/10.1137/130942292

    2015 doi

  63. [76]

    Leone, S

    L. Leone, S. F. E. Oliviero, and A. Hamma, Stabilizer rényi entropy, Phys. Rev. Lett. 128, 050402 (2022)

    2022

  64. [77]

    Baumgratz, M

    T. Baumgratz, M. Cramer, and M. B. Plenio, Quantifying coherence, Phys. Rev. Lett. 113, 140401 (2014)

    2014

  65. [78]

    Aaronson, A

    S. Aaronson, A. Bouland, B. Fefferman, S. Ghosh, U. Vazirani, C. Zhang, and Z. Zhou, Quantum pseudoentanglement (2023), arXiv:2211.00747 [quant-ph]

    2023 arXiv

  66. [79]

    A. Gu, L. Leone, S. Ghosh, J. Eisert, S. F. Yelin, and Y. Quek, Pseudomagic quantum states, Phys. Rev. Lett. 132 (2024)

    2024

  67. [80]

    T. Haug, S. Lee, and M. S. Kim, Efficient quantum algorithms for stabilizer entropies, Phys. Rev. Lett. 132, 240602 (2024)

    2024

  68. [81]

    Joag-Dev and F

    K. Joag-Dev and F. Proschan, Negative Association of Random Variables with Applications, The Annals of Statistics 11, 286 (1983)

    1983

  69. [82]

    Ji, Y.-K

    Z. Ji, Y.-K. Liu, and F. Song, Pseudorandom quantum states, in Advances in Cryptology – CRYPTO 2018 , edited by H. Shacham and A. Boldyreva (Springer International Publishing, Cham, 2018) pp. 126–152

    2018

Pith tools

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