Pith. sign in

REVIEW 5 minor 68 references

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

T0 review · 0 major / 5 minor · reviewed 2026-07-31 · grok-4.5

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

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

desk verdict 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. read the letter →

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

Tongyang Li , Fengning Ou , Xinzhao Wang , Penghui Yao , Pei Yuan , Shengyu Zhang This is my paper · ORCID
classification quant-phcs.CCcs.DS
keywords sparseQROMT-countClifford+Tstatepreparationblockencodingmultilevelhashingadaptivecircuitsquantumsingularvaluetransformation
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

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.

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)).

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

Extended reading notes

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.

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.

Editorial extensions

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.

Reading between the lines

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.
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

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 · score 0.0 of 10

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.

Assumptions & free parameters 0 free parameters · 6 assumptions · 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.

assumptions (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
    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
    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.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Optimal T Counts under Sparsity: from QROM to State Preparation and Block Encoding." pith.science (2026). https://pith.science/paper/5MWQOXEZ

@misc{pith2026260728260,
  author       = {Pith},
  title        = {Pith review of: Optimal T Counts under Sparsity: from QROM to State Preparation and Block Encoding},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5MWQOXEZ}},
  note         = {Machine review of arXiv:2607.28260}
}
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). Continue with ORCID to comment.

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

Show all 68 references
  1. [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

    2026 doi

  2. [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

    2023 doi

  3. [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

    2026 arXiv

  4. [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

    1920 doi

  5. [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

    2013 doi

  6. [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.11...

    2022

  7. [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/PRXQua...

    2022 doi

  8. [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

    2022 doi

  9. [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

    2020

  10. [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

    2020 doi

  11. [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

    2018 doi

  12. [20]

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

    doi

  13. [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 ...

    2019

  14. [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

    2024 arXiv

  15. [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

    2008 doi

  16. [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

    2008 doi

  17. [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

    2025

  18. [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

    2021

  19. [27]

    The Heisenberg representation of quantum computers, 1998

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

    1998 arXiv

  20. [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.1...

    2026 doi

  21. [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

    2021 doi

  22. [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

    2022 arXiv

  23. [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

    1922 doi

  24. [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

    2009 doi

  25. [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

    2025

  26. [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-03...

    2011 doi

  27. [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. Sc...

    2025 doi

  28. [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 Intern...

    2013 doi

  29. [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

  30. [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

    2026 arXiv

  31. [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

    2024 doi

  32. [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

    2021 doi

  33. [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

    2019 doi

  34. [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

    2016 doi

  35. [43]

    Halving the cost of QROM, 2026

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

    2026 arXiv

  36. [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

    2024 doi

  37. [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

    2013

  38. [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 97...

    1999 doi

  39. [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

    2022 doi

  40. [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

    2024 doi

  41. [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

    2016

  42. [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

    2020 doi

  43. [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

    2019 doi

  44. [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:...

    2023

  45. [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

    2026

  46. [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

    2011 doi

  47. [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

    2012 doi

  48. [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

    2024 doi

  49. [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/1...

    2025 doi

  50. [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/1...

    2025 doi

  51. [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, page...

    2025

  52. [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

    2024 doi

  53. [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

  54. [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,

  55. [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

    2025 arXiv

  56. [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

    2025 doi

  57. [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

    2019 doi

  58. [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

  59. [2026]

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

  60. [3457]

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

    doi

Pith tools

Reviewed July 31, 2026 · model on record in the stance chip above.