Pith. sign in

REVIEW 5 minor 68 references

Sparse classical data can be loaded coherently with optimal square-root T-count in the support size, matching lower bounds even for adaptive circuits.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · grok-4.5

2026-07-31 12:58 UTC pith:5MWQOXEZ

load-bearing objection Tight T-count theory for sparse QROM, with matching applications to sparse state prep and block encoding; the one disclosed adaptive gap does not undercut the main claims.

arxiv 2607.28260 v1 pith:5MWQOXEZ submitted 2026-07-30 quant-ph cs.CCcs.DS

Optimal T Counts under Sparsity: from QROM to State Preparation and Block Encoding

Tongyang Li , Fengning Ou , Xinzhao Wang , Penghui Yao , Pei Yuan , Shengyu Zhang This is my paper
classification quant-ph cs.CCcs.DS
keywords sparse QROMT-countClifford+Tstate preparationblock encodingmultilevel hashingadaptive circuitsquantum singular value transformation
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

Many quantum algorithms need coherent access to classical tables. When only s of the 2^n addresses hold nonzero data, the paper shows that the non-Clifford cost of implementing that access is governed by square roots of s rather than of the full table size. The upper bound is a multilevel hashing scheme that repeatedly resolves a constant fraction of the remaining support with dense lookups; the matching lower bounds come from reducing the task to state preparation and counting distinct adaptive Clifford+T circuits. The same square-root sparsity dependence is then tight for preparing s-sparse quantum states and for block-encoding row-and-column s-sparse matrices. A sympathetic reader cares because data-loading cost often dominates fault-tolerant resource estimates, and the new bounds replace near-linear sparsity dependence with the optimal square-root scaling in several standard primitives.

Core claim

Sparse QROM with support size s, n-bit addresses and m-bit messages has asymptotically optimal T-count Θ(√(sm)+√(sn)); the promised-sparse variant is Θ(√(sm)). The same square-root dependence on s is tight for s-sparse state preparation and for block encoding of s-sparse matrices, even when mid-circuit measurements and classical feed-forward are allowed.

What carries the argument

Multilevel hashing for promised sparse QROM: at each level a random linear hash isolates a constant fraction of still-unresolved addresses into singleton buckets that are resolved by one dense QROM call; the unresolved set shrinks geometrically, so total T-count sums to O(√(sm)).

Load-bearing premise

The matching lower bounds hold only when the support is neither tiny nor nearly dense, and the fully adaptive upper bound for ordinary sparse QROM still carries a small extra logarithmic term that is not yet matched.

What would settle it

Exhibit either an adaptive Clifford+T circuit for promised sparse QROM whose T-count is o(√(sm)) on a hard family of supports, or a counting argument showing that every such circuit needs ω(√(sm)) T gates outside the stated sparsity window.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • s-sparse n-qubit states prepare with T-count Θ(√(sn)+√(s log(1/ε))+log(1/ε)), matching the adaptive lower bound.
  • Row-and-column s-sparse matrices admit block encodings whose T-count is Θ(√(2^n s n)+√(2^n s log(s/ε_BE))+log(s/ε_BE)).
  • The same block-encoding cost propagates into QSVT, sparse Hamiltonian simulation and sparse linear-system solvers, replacing prior near-linear sparsity factors by square-root factors.
  • Quantum rejection sampling on an s-sparse distribution inherits an O(√(s log(1/δ))) T-cost per post-selection round.

Where Pith is reading between the lines

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

  • Once sparse data loading is no longer the asymptotic bottleneck, end-to-end T-counts for chemistry and linear-algebra algorithms will be dominated by the polynomial degree or condition number rather than by table size.
  • The remaining gap between the adaptive upper and lower bounds for general (non-promised) sparse QROM is a concrete target: either a better support-identification primitive or a tighter adaptive counting argument would close it.
  • The multilevel-hash idea may transfer to other coherent classical-data tasks whose cost is currently linear in support size, such as sparse isometries or dictionary-based encodings.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 5 minor

Summary. The paper initiates the study of T-count for sparse QROM (only s of 2^n addresses nonzero) and proves asymptotically optimal bounds Θ(√(sm)+√(sn)) in the unitary model, with promised sparse QROM tight at Θ(√(sm)) even adaptively. Upper bounds use a multilevel linear-hashing scheme that resolves a constant fraction of the remaining support per level, reducing to dense SELECT–SWAP QROM; general sparse QROM is obtained by index certification. Lower bounds reduce to state preparation and count Pauli-postselection Clifford canonical forms, holding for adaptive Clifford+T circuits. Matching adaptive bounds are obtained for s-sparse state preparation and for block encoding of row-and-column s-sparse matrices, with corollaries for QSVT, Hamiltonian simulation, linear systems, and rejection sampling.

Significance. Coherent sparse data loading is a bottleneck in fault-tolerant quantum algorithms (sparse Hamiltonian simulation, linear systems, state preparation). Prior T-count work focused on dense QROM (SELECT–SWAP) or near-linear sparse state preparation; this paper supplies the first matching square-root T-count theory under sparsity, including adaptive lower bounds. The multilevel hashing construction is constructive and cleanly reduces to a black-box dense QROM, and the applications inherit tight asymptotics. The disclosed gap for fully adaptive general sparse QROM (upper O(√(sm)+√(s log s)) vs unitary lower √(sn)) does not undercut the promised case or the main applications. This is a substantial, self-contained contribution to fault-tolerant resource estimation.

minor comments (5)
  1. [Abstract / Table 1 / Remark 5.3] Table 1 and Remark 5.3 already flag the adaptive general-sparse gap, but the abstract and §1.1 lead with Θ(√(sm)+√(sn)) without immediately qualifying that the matching upper bound is for the unitary/non-adaptive model. A one-sentence qualification in the abstract or the table caption would prevent misreading.
  2. [§1.4 / Theorems 5.4–5.7] The lower-bound windows (e.g. C(n+m)² ≤ s ≤ 2^{(1-δ)n} in Thm 5.4; Cn ≤ s ≤ 2^{(1-δ)n} in Thms 5.5 and 5.7) are standard for canonical-form counting but are easy to miss. A short remark in §1.4 on the nearly-dense and ultra-sparse regimes would help practitioners.
  3. [§3.1, Algorithms 3.1–3.2] In Algorithm 3.1–3.2, the active-flag and singleton-flag bookkeeping is correct but dense; a one-line invariant (e.g. “after level i, T holds d_x iff x was resolved at some i★ ≤ i”) would make the uncomputation argument easier to audit.
  4. [§3.1, proof of Theorem 3.1] Theorem 2.6 is cited with an additive +m term restored in a footnote; when the paper invokes it inside multilevel hashing (m_i = O(log s_i)), the additive terms sum to O(m log s) and are absorbed under s ≥ m log² m. Stating this absorption once in the proof of Thm 3.1 would avoid repeated mental bookkeeping.
  5. [§2.3 / §4 / Remark 5.8] Minor typos/notation: “F act 2.13” → “Fact 2.13”; in §4.2 the normalization is written both ¯s and S in Remark 5.8; ε vs ε_BE vs δ_BE are used consistently but a short notation paragraph at the start of §4 would help.

Circularity Check

0 steps flagged

No significant circularity: multilevel-hashing upper bounds and counting lower bounds are independent constructions against external hard families.

full rationale

The paper’s optimality claims are not forced by definition or by self-referential fitting. Upper bounds for promised/general sparse QROM are explicit multilevel-hashing circuits that reduce to the external dense-QROM SELECT–SWAP theorem of Low–Kliuchnikov–Schaeffer; the T-count sum is a geometric series over unresolved support sizes, not an identity with the target. Lower bounds reduce tasks to state preparation and injectively map exponentially large, pairwise-separated hard families (Hamming-separated message tables, support families from independent-set arguments) into Pauli-postselection Clifford canonical forms whose number is 2^{O((n+t)^2)}; the counting is external combinatorial content, not a restatement of the claimed bound. Dense state-preparation and QSVT primitives are cited as black boxes with stated hypotheses that do not include the sparse targets. Applications (sparse state prep, block encoding) compose these primitives and re-run the same style of counting on new hard families; nothing is fitted to data or defined in terms of the conclusion. Self-citations are ordinary background, not load-bearing uniqueness theorems that close a loop. The disclosed adaptive gap for general sparse QROM (Remark 5.3) is an incompleteness, not circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 6 axioms · 2 invented entities

The work sits on standard Clifford+T complexity, known dense QROM and dense state-preparation T-count theorems, and the adaptive-to-postselected-Clifford reduction of Gosset–Kothari–Wu / Beverland et al. No empirical free parameters. Invented notions are definitional models (promised/adaptive sparse QROM), not physical entities.

axioms (6)
  • domain assumption Clifford+T gate set with T-count as the non-Clifford cost measure; Clifford circuits classically simulable (Gottesman–Knill).
    Stated in Introduction and §2.1; standard fault-tolerant cost model.
  • domain assumption Dense QROM is implementable with T-count O(√(2^n m)+m) (Low–Kliuchnikov–Schaeffer SELECT-SWAP).
    Theorem 2.6; used as black box in every upper bound.
  • domain assumption Any n-qubit state preparable to error ε with T-count O(√(2^n log(1/ε))+log(1/ε)) (Gosset–Kothari–Wu).
    Theorem 4.1; used for compressed amplitudes and lower-bound embedding.
  • domain assumption Adaptive Clifford+T circuits with expected T-count t reduce to Pauli-postselected Clifford canonical forms with O(t) magic states preparing a nearby state (Lemmas 2.2–2.3 / Corollary 2.4).
    Load-bearing for all adaptive lower bounds in §5.
  • standard math Random linear hashes over F_2 collide with probability 2^{-m_i}; Markov yields constant-fraction singleton buckets w.h.p.
    Proof of Theorem 3.1; standard probabilistic method.
  • domain assumption Block-encoding / QSVT / Hamiltonian-simulation / QLSS query complexities from Gilyén et al. and Costa et al. compose with the new sparse block-encoding T-count.
    §4.2 applications; standard composition, not re-proved.
invented entities (2)
  • Promised sparse QROM no independent evidence
    purpose: Weaker oracle correct only on supp(d); enables multilevel hashing upper bound Θ(√(sm)) and erase steps in state prep / block encoding.
    Definition 2.7; definitional model, not a physical postulate.
  • Adaptive (channel) QROM / promised sparse QROM no independent evidence
    purpose: Allow mid-circuit measurement and feedforward so lower bounds apply beyond unitary circuits.
    Definitions 2.8–2.10; standard adaptive circuit model specialized to QROM.

pith-pipeline@v1.2.0-daily-grok45 · 44943 in / 3411 out tokens · 65497 ms · 2026-07-31T12:58:34.058755+00:00 · methodology

0 comments
read the original abstract

Many quantum algorithms require coherent access to classical data, often modeled by quantum read-only memory (QROM). We initiate the study of the $T$ count of sparse QROM, in which only $s$ of the $2^n$ addresses store nonzero data. We prove asymptotically optimal $T$-count bounds $\Theta(\sqrt{sm} + \sqrt{sn})$ with square-root dependence on the support size $s$ and message length $m$. Our upper bounds use a multilevel hashing scheme, while our lower bounds reduce sparse QROM to state preparation and use counting arguments for adaptive Clifford+$T$ circuits. The lower bounds thus hold even when mid-circuit measurements and classically controlled operations are allowed. As applications, we obtain matching $T$-count bounds $\Theta(\sqrt{sn} + \sqrt{s\log(1/\varepsilon)} + \log(1/\varepsilon))$ for $s$-sparse state preparation and $\Theta( \sqrt{2^n sn} + \sqrt{2^n s\log(s/\varepsilon_{\mathrm{BE}})} + \log(s/\varepsilon_{\mathrm{BE}}))$ for block encoding of $s$-sparse matrices, where $\varepsilon$ and $\varepsilon_{\mathrm{BE}}$ are the precision of state preparation and block encoding, respectively.

discussion (0)

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

Reference graph

Works this paper leans on

68 extracted references · 13 canonical work pages

  1. [1]

    Berry, Ian D

    Ryan Babbush, Dominic W. Berry, Ian D. Kivlichan, Annie Y. Wei, Peter J. Love, and Al´ an Aspuru-Guzik. Exponentially more precise quantum simulation of fermions I: quantum chem- istry in second quantization.New J. Phys., 18:033032, 2016. doi: 10.1088/1367-2630/18/3/ 033032. URLhttps://doi.org/10.1088/1367-2630/18/3/033032

    work page doi:10.1088/1367-2630/18/3/ 2016

  2. [2]

    Berry, Nathan Wiebe, Jarrod McClean, Alexandru Paler, Austin Fowler, and Hartmut Neven

    Ryan Babbush, Craig Gidney, Dominic W. Berry, Nathan Wiebe, Jarrod McClean, Alexandru Paler, Austin Fowler, and Hartmut Neven. Encoding electronic spectra in quantum circuits with linear T complexity.Phys. Rev. X, 8:041015, Oct 2018. doi: 10.1103/PhysRevX.8.041015. URLhttps://link.aps.org/doi/10.1103/PhysRevX.8.041015

    doi:10.1103/physrevx.8.041015 2018

  3. [3]

    Bennett, Richard Cleve, David P

    Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A. Smolin, and Harald Weinfurter. Elementary gates for quantum computation.Phys. Rev. A, 52:3457–3467, Nov 1995. doi: 10.1103/PhysRevA.52

    doi:10.1103/physreva.52 1995

  4. [4]

    Berry, Andrew M

    Dominic W. Berry, Andrew M. Childs, and Robin Kothari. Hamiltonian simulation with nearly optimal dependence on all parameters. In2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS ’15, pages 792–809, USA, 2015. IEEE Computer Society. ISBN 9781467381918. doi: 10.1109/FOCS.2015.54. URLhttps://doi.org/10.1109/FOCS.2015. 54

    doi:10.1109/focs.2015.54 2015

  5. [5]

    Berry, Andrew M

    Dominic W. Berry, Andrew M. Childs, Aaron Ostrander, and Guoming Wang. Quantum algorithm for linear differential equations with exponentially improved dependence on preci- sion.Commun. Math. Phys., 356:1057–1081, 2017. doi: 10.1007/s00220-017-3002-y. URL https://doi.org/10.1007/s00220-017-3002-y

    doi:10.1007/s00220-017-3002-y 2017

  6. [6]

    Lower bounds on the non-Clifford resources for quantum computations.Quantum Sci

    Michael Beverland, Earl Campbell, Mark Howard, and Vadym Kliuchnikov. Lower bounds on the non-Clifford resources for quantum computations.Quantum Sci. Technol., 5(3):035009, may 2020. doi: 10.1088/2058-9565/ab8963. URLhttps://doi.org/10.1088/2058-9565/ ab8963

    doi:10.1088/2058-9565/ab8963 2020

  7. [7]

    Universal quantum computation with ideal Clifford gates and noisy ancillas.Phys

    Sergey Bravyi and Alexei Kitaev. Universal quantum computation with ideal Clifford gates and noisy ancillas.Phys. Rev. A, 71:022316, Feb 2005. doi: 10.1103/PhysRevA.71.022316. URLhttps://link.aps.org/doi/10.1103/PhysRevA.71.022316

    doi:10.1103/physreva.71.022316 2005

  8. [8]

    Explicit quantum circuits for block encodings of certain sparse matrices.SIAM J

    Daan Camps, Lin Lin, Roel Van Beeumen, and Chao Yang. Explicit quantum circuits for block encodings of certain sparse matrices.SIAM J. Matrix Anal. Appl., 45(1):801–827, March 2024. ISSN 0895-4798. doi: 10.1137/22M1484298. URLhttps://doi.org/10.1137/22M1484298

    doi:10.1137/22m1484298 2024

  9. [9]

    Resource-state quantum RAM for fast and error-correctable queries.Nat

    Francesco Cesa, Hannes Bernien, and Hannes Pichler. Resource-state quantum RAM for fast and error-correctable queries.Nat. Commun., June 2026. doi: 10.1038/s41467-026-73275-x. URLhttps://www.nature.com/articles/s41467-026-73275-x. 41

    work page doi:10.1038/s41467-026-73275-x 2026

  10. [10]

    Quantum regularized least squares.Quantum, 7:988, April 2023

    Shantanav Chakraborty, Aditya Morolia, and Anurudh Peduri. Quantum regularized least squares.Quantum, 7:988, April 2023. ISSN 2521-327X. doi: 10.22331/q-2023-04-27-988. URL https://doi.org/10.22331/q-2023-04-27-988

    doi:10.22331/q-2023-04-27-988 2023

  11. [11]

    Quantum algorithm for discrete Gaussian sampling, 2026

    Cl´ emence Chevignard, Yixin Shen, and Andr´ e Schrottenloher. Quantum algorithm for discrete Gaussian sampling, 2026. URLhttps://arxiv.org/abs/2605.20133

    Pith/arXiv arXiv 2026

  12. [12]

    Childs, Robin Kothari, and Rolando D

    Andrew M. Childs, Robin Kothari, and Rolando D. Somma. Quantum algorithm for systems of linear equations with exponentially improved dependence on precision.SIAM J. Com- put., 46(6):1920–1950, 2017. doi: 10.1137/16M1087072. URLhttps://doi.org/10.1137/ 16M1087072

    doi:10.1137/16m1087072 1920

  13. [13]

    David Clader, Bryan C

    B. David Clader, Bryan C. Jacobs, and Chad R. Sprouse. Preconditioned quantum linear system algorithm.Phys. Rev. Lett., 110:250504, 2013. doi: 10.1103/PhysRevLett.110.250504. URLhttps://doi.org/10.1103/PhysRevLett.110.250504

    doi:10.1103/physrevlett.110.250504 2013

  14. [14]

    David Clader, Alexander M

    B. David Clader, Alexander M. Dalzell, Nikitas Stamatopoulos, Grant Salton, Mario Berta, and William J. Zeng. Quantum resources required to block-encode a matrix of classical data. IEEE Trans. Quantum Eng., 3:1–23, 2022. doi: 10.1109/TQE.2022.3231194. URLhttps: //doi.org/10.1109/TQE.2022.3231194

    arXiv 2022

  15. [15]

    Costa, Dong An, Yuval R

    Pedro C.S. Costa, Dong An, Yuval R. Sanders, Yuan Su, Ryan Babbush, and Dominic W. Berry. Optimal scaling quantum linear-systems solver via discrete adiabatic theorem.PRX Quantum, 3:040303, Oct 2022. doi: 10.1103/PRXQuantum.3.040303. URLhttps://link. aps.org/doi/10.1103/PRXQuantum.3.040303

    doi:10.1103/prxquantum.3.040303 2022

  16. [16]

    Tiago M. L. de Veras, Leon D. da Silva, and Adenilton J. da Silva. Double sparse quantum state preparation.Quantum Information Processing, 21(6):204, June 2022. ISSN 1573-1332. doi: 10.1007/s11128-022-03549-y. URLhttps://doi.org/10.1007/s11128-022-03549-y

    work page doi:10.1007/s11128-022-03549-y 2022

  17. [17]

    Fault-tolerant resource estimation of quantum random-access memories.IEEE Trans

    Olivia Di Matteo, Vlad Gheorghiu, and Michele Mosca. Fault-tolerant resource estimation of quantum random-access memories.IEEE Trans. Quantum Eng., 1:1–13, 2020. doi: 10.1109/ TQE.2020.2965803. URLhttps://doi.org/10.1109/TQE.2020.2965803

    arXiv 2020

  18. [18]

    RecSplit: minimal perfect hashing via recursive splitting

    Emmanuel Esposito, Thomas Mueller Graf, and Sebastiano Vigna. RecSplit: minimal perfect hashing via recursive splitting. In2020 Proceedings of the Symposium on Algorithm Engineer- ing and Experiments (ALENEX), pages 175–185. SIAM, 2020. doi: 10.1137/1.9781611976007

    work page doi:10.1137/1.9781611976007 2020

  19. [19]

    Halving the cost of quantum addition.Quantum, 2:74, June 2018

    Craig Gidney. Halving the cost of quantum addition.Quantum, 2:74, June 2018. ISSN 2521- 327X. doi: 10.22331/q-2018-06-18-74. URLhttps://doi.org/10.22331/q-2018-06-18-74

    doi:10.22331/q-2018-06-18-74 2018

  20. [20]

    URLhttps://epubs.siam.org/doi/abs/10.1137/1.9781611976007.14

    work page doi:10.1137/1.9781611976007.14

  21. [21]

    Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics

    Andr´ as Gily´ en, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pages 193–204, New York, NY, USA, 2019. Association for Computing Machinery. ISBN 9781450367059. do...

    arXiv 2019

  22. [22]

    Magic state cultivation: growing T states as cheap as CNOT gates, 2024

    Craig Gidney, Noah Shutty, and Cody Jones. Magic state cultivation: growing T states as cheap as CNOT gates, 2024. URLhttps://arxiv.org/abs/2409.17595

    Pith/arXiv arXiv 2024

  23. [23]

    Quantum random access memory

    Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Quantum random access memory. Phys. Rev. Lett., 100:160501, Apr 2008. doi: 10.1103/PhysRevLett.100.160501. URLhttps: //link.aps.org/doi/10.1103/PhysRevLett.100.160501

    doi:10.1103/physrevlett.100.160501 2008

  24. [24]

    Architectures for a quantum random access memory.Phys

    Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Architectures for a quantum random access memory.Phys. Rev. A, 78:052310, 2008. doi: 10.1103/PhysRevA.78.052310. URL https://link.aps.org/doi/10.1103/PhysRevA.78.052310

    doi:10.1103/physreva.78.052310 2008

  25. [25]

    Multi-qubit Toffoli with exponentially fewer T gates, 2025

    David Gosset, Robin Kothari, and Chenyi Zhang. Multi-qubit Toffoli with exponentially fewer T gates, 2025. URLhttps://arxiv.org/abs/2510.07223

    arXiv 2025

  26. [26]

    An efficient algorithm for sparse quantum state preparation

    Niels Gleinig and Torsten Hoefler. An efficient algorithm for sparse quantum state preparation. In2021 58th ACM/IEEE Design Automation Conference (DAC), pages 433–438, 2021. doi: 10. 1109/DAC18074.2021.9586240. URLhttps://doi.org/10.1109/DAC18074.2021.9586240

    arXiv 2021

  27. [27]

    The Heisenberg representation of quantum computers, 1998

    Daniel Gottesman. The Heisenberg representation of quantum computers, 1998. URLhttps: //arxiv.org/abs/quant-ph/9807006

    Pith/arXiv arXiv 1998

  28. [28]

    Quantum state preparation with optimal T- count

    David Gosset, Robin Kothari, and Kewen Wu. Quantum state preparation with optimal T- count. InProceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3378–3406. SIAM, 2026. doi: 10.1137/1.9781611978971.122. URLhttps: //epubs.siam.org/doi/abs/10.1137/1.9781611978971.122

    doi:10.1137/1.9781611978971.122 2026

  29. [29]

    Hann, Gideon Lee, S.M

    Connor T. Hann, Gideon Lee, S.M. Girvin, and Liang Jiang. Resilience of quantum random ac- cess memory to generic noise.PRX Quantum, 2:020311, Apr 2021. doi: 10.1103/PRXQuantum. 2.020311. URLhttps://link.aps.org/doi/10.1103/PRXQuantum.2.020311

    doi:10.1103/prxquantum 2021

  30. [30]

    Space-time opti- mized table lookup, 2022

    Thomas H¨ aner, Vadym Kliuchnikov, Martin Roetteler, and Mathias Soeken. Space-time opti- mized table lookup, 2022. URLhttps://arxiv.org/abs/2211.01133

    Pith/arXiv arXiv 2022

  31. [31]

    Samuel Jaques and Arthur G. Rattew. QRAM: a survey and critique.Quantum, 9:1922, December 2025. ISSN 2521-327X. doi: 10.22331/q-2025-12-02-1922. URLhttps://doi.org/ 10.22331/q-2025-12-02-1922

    doi:10.22331/q-2025-12-02-1922 1922

  32. [32]

    Harrow, Avinatan Hassidim, and Seth Lloyd

    Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for solving linear systems of equations.Phys. Rev. Lett., 103(15):150502, 2009. doi: 10.1103/PhysRevLett.103. 150502. URLhttps://doi.org/10.1103/PhysRevLett.103.150502

    doi:10.1103/physrevlett.103 2009

  33. [33]

    Kim and Tuomas Laakkonen

    Isaac H. Kim and Tuomas Laakkonen. Any Clifford+T circuit can be controlled with constant T-depth overhead, 2025. URLhttps://arxiv.org/abs/2512.24982

    arXiv 2025

  34. [34]

    Whitfield, Alejandro Perdomo-Ortiz, Man-Hong Yung, and Al´ an Aspuru-Guzik

    Ivan Kassal, James D. Whitfield, Alejandro Perdomo-Ortiz, Man-Hong Yung, and Al´ an Aspuru-Guzik. Simulating chemistry using quantum computers.Annu. Rev. Phys. Chem., 62:185–207, 2011. doi: 10.1146/annurev-physchem-032210-103512. URLhttps://doi.org/ 10.1146/annurev-physchem-032210-103512

    doi:10.1146/annurev-physchem-032210-103512 2011

  35. [35]

    Nearly optimal circuit size for sparse quantum state prepara- tion

    Lvzhou Li and Jingquan Luo. Nearly optimal circuit size for sparse quantum state prepara- tion. In52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025), volume 334 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 113:1– 113:19. Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik, 2025. doi: 10.4230/LIPIcs.ICA...

    doi:10.4230/lipics.icalp 2025

  36. [36]

    Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem

    Greg Kuperberg. Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem. In Simone Severini and Fernando Brandao, editors,8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013), vol- ume 22 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 20–34, Dagstuhl, Germany, 201...

    work page doi:10.4230/lipics.tqc.2013.20 2013

  37. [37]

    Magic state distillation: not as costly as you think.Quantum, 3:205, December

    Daniel Litinski. Magic state distillation: not as costly as you think.Quantum, 3:205, December

  38. [38]

    Improved dual attack and trapdoor sampling via quantum rejection sampling, 2026

    Cong Ling, Hao Yan, and Nicholas Zhao. Improved dual attack and trapdoor sampling via quantum rejection sampling, 2026. URLhttps://arxiv.org/abs/2605.24798

    Pith/arXiv arXiv 2026

  39. [39]

    Trading T gates for dirty qubits in state preparation and unitary synthesis.Quantum, 8:1375, June 2024

    Guang Hao Low, Vadym Kliuchnikov, and Luke Schaeffer. Trading T gates for dirty qubits in state preparation and unitary synthesis.Quantum, 8:1375, June 2024. ISSN 2521-327X. doi: 10.22331/q-2024-06-17-1375. URLhttps://doi.org/10.22331/q-2024-06-17-1375

    doi:10.22331/q-2024-06-17-1375 2024

  40. [40]

    Quantum circuits for sparse isometries

    Emanuel Malvetti, Raban Iten, and Roger Colbeck. Quantum circuits for sparse isometries. Quantum, 5:412, Mar 2021. ISSN 2521-327X. doi: 10.22331/q-2021-03-15-412. URLhttps: //doi.org/10.22331/q-2021-03-15-412

    work page doi:10.22331/q-2021-03-15-412 2021

  41. [41]

    Guang Hao Low and Isaac L. Chuang. Hamiltonian simulation by qubitization.Quantum, 3: 163, July 2019. ISSN 2521-327X. doi: 10.22331/q-2019-07-12-163. URLhttps://doi.org/ 10.22331/q-2019-07-12-163

    doi:10.22331/q-2019-07-12-163 2019

  42. [42]

    Quantum algorithms and the finite element method

    Ashley Montanaro and Sam Pallister. Quantum algorithms and the finite element method. Phys. Rev. A, 93:032324, 2016. doi: 10.1103/PhysRevA.93.032324. URLhttps://doi.org/ 10.1103/PhysRevA.93.032324

    doi:10.1103/physreva.93.032324 2016

  43. [43]

    Halving the cost of QROM, 2026

    Danial Motlagh and Matthew Pocrnic. Halving the cost of QROM, 2026. URLhttps:// arxiv.org/abs/2605.20334

    Pith/arXiv arXiv 2026

  44. [44]

    Toward optimal circuit size for sparse quantum state preparation.Phys

    Rui Mao, Guojing Tian, and Xiaoming Sun. Toward optimal circuit size for sparse quantum state preparation.Phys. Rev. A, 110:032439, Sep 2024. doi: 10.1103/PhysRevA.110.032439. URLhttps://link.aps.org/doi/10.1103/PhysRevA.110.032439

    work page doi:10.1103/physreva.110.032439 2024

  45. [45]

    Quantum rejection sampling.ACM Trans

    Maris Ozols, Martin Roetteler, and J´ er´ emie Roland. Quantum rejection sampling.ACM Trans. Comput. Theory, 5(3), August 2013. ISSN 1942-3454. doi: 10.1145/2493252.2493256. URLhttps://doi.org/10.1145/2493252.2493256

    arXiv 2013

  46. [46]

    Hash and displace: efficient evaluation of minimal perfect hash functions

    Rasmus Pagh. Hash and displace: efficient evaluation of minimal perfect hash functions. In Frank Dehne, J¨ org-R¨ udiger Sack, Arvind Gupta, and Roberto Tamassia, editors,Algorithms and Data Structures, pages 49–54, Berlin, Heidelberg, 1999. Springer Berlin Heidelberg. ISBN 978-3-540-48447-9. URLhttps://doi.org/10.1007/3-540-48447-7_5

    work page doi:10.1007/3-540-48447-7_5 1999

  47. [47]

    Efficient deterministic preparation of quantum states using decision diagrams.Phys

    Fereshte Mozafari, Giovanni De Micheli, and Yuxiang Yang. Efficient deterministic preparation of quantum states using decision diagrams.Phys. Rev. A, 106:022617, Aug 2022. doi: 10.1103/ PhysRevA.106.022617. URLhttps://link.aps.org/doi/10.1103/PhysRevA.106.022617

    work page doi:10.1103/physreva.106.022617 2022

  48. [48]

    Lefterovici, and Antonio F

    Debora Ramacciotti, Andreea I. Lefterovici, and Antonio F. Rotundo. Simple quantum algo- rithm to efficiently prepare sparse states.Phys. Rev. A, 110:032609, Sep 2024. doi: 10.1103/ PhysRevA.110.032609. URLhttps://link.aps.org/doi/10.1103/PhysRevA.110.032609

    doi:10.1103/physreva.110.032609 2024

  49. [49]

    Ross and Peter Selinger

    Neil J. Ross and Peter Selinger. Optimal ancilla-free Clifford+T approximation of Z-rotations. Quantum Info. Comput., 16(11–12):901–953, September 2016. ISSN 1533-7146. URLhttps: //dl.acm.org/doi/abs/10.5555/3179330.3179331

    arXiv 2016

  50. [50]

    Parallelising the queries in bucket brigade quantum RAM.Phys

    Alexandru Paler, Oumarou Oumarou, and Robert Basmadjian. Parallelising the queries in bucket brigade quantum RAM.Phys. Rev. A, 102:032608, 2020. doi: 10.1103/PhysRevA.102. 032608. URLhttps://link.aps.org/doi/10.1103/PhysRevA.102.032608. 44

    doi:10.1103/physreva.102 2020

  51. [51]

    Sanders, Guang Hao Low, Artur Scherer, and Dominic W

    Yuval R. Sanders, Guang Hao Low, Artur Scherer, and Dominic W. Berry. Black-box quan- tum state preparation without arithmetic.Phys. Rev. Lett., 122:020502, Jan 2019. doi: 10. 1103/PhysRevLett.122.020502. URLhttps://link.aps.org/doi/10.1103/PhysRevLett. 122.020502

    doi:10.1103/physrevlett 2019

  52. [52]

    Xiaoming Sun, Guojing Tian, Shuai Yang, Pei Yuan, and Shengyu Zhang. Asymptotically opti- mal circuit depth for quantum state preparation and general unitary synthesis.IEEE Transac- tions on Computer-Aided Design of Integrated Circuits and Systems, 42(10):3301–3314, 2023. doi: 10.1109/TCAD.2023.3244885. URLhttps://doi.org/10.1109/TCAD.2023.3244885

    arXiv 2023

  53. [53]

    Sparse quantum state preparation with improved Toffoli cost, 2026

    Felix Rupprecht and Sabine W¨ olk. Sparse quantum state preparation with improved Toffoli cost, 2026. URLhttps://arxiv.org/abs/2601.09388

    arXiv 2026

  54. [54]

    Temme, T

    K. Temme, T. J. Osborne, K. G. Vollbrecht, D. Poulin, and F. Verstraete. Quantum Metropolis sampling.Nature, 471(7336):87–90, March 2011. ISSN 1476-4687. doi: 10.1038/nature09770. URLhttps://doi.org/10.1038/nature09770

    doi:10.1038/nature09770 2011

  55. [55]

    Quantum data fitting.Phys

    Nathan Wiebe, Daniel Braun, and Seth Lloyd. Quantum data fitting.Phys. Rev. Lett., 109:050505, 2012. doi: 10.1103/PhysRevLett.109.050505. URLhttps://doi.org/10.1103/ PhysRevLett.109.050505

    doi:10.1103/physrevlett.109.050505 2012

  56. [56]

    Block-encoding structured matrices for data input in quantum computing.Quantum, 8:1226, January 2024

    Christoph S¨ underhauf, Earl Campbell, and Joan Camps. Block-encoding structured matrices for data input in quantum computing.Quantum, 8:1226, January 2024. ISSN 2521-327X. doi: 10.22331/q-2024-01-11-1226. URLhttps://doi.org/10.22331/q-2024-01-11-1226

    doi:10.22331/q-2024-01-11-1226 2024

  57. [57]

    Dictionary-based block encoding of sparse matrices with low subnormalization and circuit depth.Quantum, 9:1805, July 2025

    Chunlin Yang, Zexian Li, Hongmei Yao, Zhaobing Fan, Guofeng Zhang, and Jianshe Liu. Dictionary-based block encoding of sparse matrices with low subnormalization and circuit depth.Quantum, 9:1805, July 2025. ISSN 2521-327X. doi: 10.22331/q-2025-07-22-1805. URL https://doi.org/10.22331/q-2025-07-22-1805

    doi:10.22331/q-2025-07-22-1805 2025

  58. [58]

    Reducing circuit depth in quantum state preparation for quantum simulation using measurements and feedforward

    Hyeonjun Yeo, Ha Eum Kim, IlKwon Sohn, and Kabgyun Jeong. Reducing circuit depth in quantum state preparation for quantum simulation using measurements and feedforward. Phys. Rev. Appl., 23:054066, May 2025. doi: 10.1103/PhysRevApplied.23.054066. URLhttps: //link.aps.org/doi/10.1103/PhysRevApplied.23.054066

    work page doi:10.1103/physrevapplied.23.054066 2025

  59. [59]

    Fat-Tree QRAM: A high-bandwidth shared quan- tum random access memory for parallel queries

    Shifan Xu, Alvin Lu, and Yongshan Ding. Fat-Tree QRAM: A high-bandwidth shared quan- tum random access memory for parallel queries. InProceedings of the 30th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Vol- ume 2, pages 390–406, New York, NY, USA, 2025. ACM. doi: 10.1145/3676641.3716256. URL https...

    arXiv 2025

  60. [60]

    Circuit complexity of quantum access models for en- coding classical data.npj Quantum Inf., 10(1):42, April 2024

    Xiao-Ming Zhang and Xiao Yuan. Circuit complexity of quantum access models for en- coding classical data.npj Quantum Inf., 10(1):42, April 2024. ISSN 2056-6387. doi: 10.1038/s41534-024-00835-8. URLhttps://doi.org/10.1038/s41534-024-00835-8

    work page doi:10.1038/s41534-024-00835-8 2024

  61. [61]

    Quantum state preparation with opti- mal circuit depth: implementations and applications.Phys

    Xiao-Ming Zhang, Tongyang Li, and Xiao Yuan. Quantum state preparation with opti- mal circuit depth: implementations and applications.Phys. Rev. Lett., 129:230504, Nov

  62. [62]

    Block encoding of sparse matrices with a periodic diagonal structure,

    Alessandro Andrea Zecchi, Claudio Sanavio, Luca Cappelli, Simona Perotto, Alessandro Rog- gero, and Sauro Succi. Block encoding of sparse matrices with a periodic diagonal structure,

  63. [63]

    Constant-depth quantum circuits for arbitrary quantum state preparation via measurement and feedback, 2025

    Wei Zi, Junhong Nie, and Xiaoming Sun. Constant-depth quantum circuits for arbitrary quantum state preparation via measurement and feedback, 2025. URLhttps://arxiv.org/ abs/2503.16208. 46

    Pith/arXiv arXiv 2025

  64. [67]

    Unified architecture for quantum lookup tables.Phys

    Shuchen Zhu, Aarthi Sundaram, and Guang Hao Low. Unified architecture for quantum lookup tables.Phys. Rev. Res., 7:043230, Dec 2025. doi: 10.1103/d896-mktn. URLhttps: //link.aps.org/doi/10.1103/d896-mktn

    work page doi:10.1103/d896-mktn 2025

  65. [2019]

    doi: 10.22331/q-2019-12-02-205

    ISSN 2521-327X. doi: 10.22331/q-2019-12-02-205. URLhttps://doi.org/10.22331/ q-2019-12-02-205

    doi:10.22331/q-2019-12-02-205 2019

  66. [2022]

    URLhttps://link.aps.org/doi/10.1103/ PhysRevLett.129.230504

    doi: 10.1103/PhysRevLett.129.230504. URLhttps://link.aps.org/doi/10.1103/ PhysRevLett.129.230504

    doi:10.1103/physrevlett.129.230504

  67. [2026]

    URLhttps://arxiv.org/abs/2602.10589. 45

    arXiv

  68. [3457]

    URLhttps://link.aps.org/doi/10.1103/PhysRevA.52.3457

    doi:10.1103/physreva.52.3457