Pith. sign in

REVIEW 2 major objections 3 minor 134 references

Sparse Quantum State Preparation with Sublinear T-Count

T0 review · 2 major / 3 minor · reviewed 2026-08-15 · deepseek-v4-flash

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

Pith's one-line read For any $n$-qubit $s$-sparse state, constant-error preparation costs $\widetilde{O}(\min\{s, n^{3/4}\sqrt{s}\})$ T gates, and some states require $\Omega(\min\{s,\sqrt{ns}\})$.

desk verdict A genuinely new sublinear T-count upper bound for sparse state preparation, with a lower-bound theorem that is slightly overclaimed as written. read the letter →

arxiv 2608.00414 v1 pith:DEPLQUUP submitted 2026-08-01 quant-ph

Jingquan Luo , Lvzhou Li This is my paper · ORCID
classification quant-ph MSC 68Q1281P68 PACS 03.67.Lx
keywords quantumstatepreparationsparsestatesT-countClifford+TcircuitsToffolicomplexityBooleanfunctionsstabilizernullity
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 asks whether the fault-tolerant cost of preparing an $n$-qubit state supported on at most $s$ computational-basis states must grow linearly with $s$. It shows that once the support is large enough the answer is no: any $s$-sparse state can be prepared up to constant error with $\widetilde{O}(\min\{s, n^{3/4}\sqrt{s}\})$ T gates, which is sublinear in $s$ when $s$ is much larger than $n^{3/2}$. It also proves a lower bound of $\Omega(\min\{s, \sqrt{ns}\})$ T gates for some $s$-sparse states, showing that linear cost is unavoidable when $s=O(n)$ and that a dependence on $n$ persists across the whole range. The practical consequence is that T gates are the expensive fault-tolerant resource, so moving from linear to $\widetilde{O}(n^{3/4}\sqrt{s})$ changes which sparse superpositions can plausibly be initialized on early error-corrected machines.

What carries the argument

The load-bearing object is a support-aware synthesis theorem for sparse Boolean functions (Theorem 8). For $F:\{0,1\}^n\to\{0,1\}^b$ with $|\operatorname{supp}(F)|=s$, it gives NCT implementations with $O(s+n)$ Toffoli gates when $s\le n^{3/2}\log n$, and $\widetilde{O}(n^{3/4}\sqrt{s} + n^{1/4}\sqrt{bs})$ Toffoli gates when $s>n^{3/2}\log n$. The recursive algorithm fixes a prefix length $r=\lceil\log(s/\lceil\sqrt{n}\rceil)\rceil$; if few $r$-bit prefixes are active, it injectively relabels them, shortening the input length while keeping the support size fixed, and if many are active, it peels one supported input from each active prefix, cutting the support by $\Omega(s/\sqrt{n})$. Choosing the balance parameter $c=\lceil\sqrt{n}\rceil$ makes the two costs meet at $\widetilde{O}(n^{3/4}\sqrt{s})$. On the lower-bound side the machinery is stabilizer nullity: a rank bound for stabilizer subgroups with large overlap on $|W_s\rangle|0^{n-s}\rangle$ gives $\Omega((1-\epsilon^2)s)$ T gates in the small-support regime, and a packing lemma for uniform sparse states combined with the counting bound for states preparable with $t$ T gates gives $\Omega(\sqrt{ns})$ in the large-support regime.

What would settle it

Implement the relabeling map $\gamma_G$ for a worst-case $s$-sparse support with few active prefixes and count the Toffoli gates needed; if any instance costs more than $O(\sqrt{(r-1)2^r})$ Toffoli gates, the recursive Step-1 cost accounting in Lemma 11 fails and the $\widetilde{O}(n^{3/4}\sqrt{s})$ upper bound collapses.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is a two-sided T-count characterization for sparse state preparation. The upper-bound side says that every $n$-qubit $s$-sparse state can be $\epsilon$-approximately prepared from $|0^n\rangle$ by a Clifford+T circuit using $\widetilde{O}(\min\{s, n^{3/4}\sqrt{s}\} + \sqrt{s\log(1/\epsilon)} + \log(1/\epsilon))$ T gates, with the sublinear term active once $s>n^{3/2}\log n$. The lower-bound side says that for every $0<\epsilon\le 1/6$ and $2\le s\le 2^{n/2}$ there exists an $s$-sparse state requiring $\Omega(\min\{s, \sqrt{ns}\})$ T gates for $\epsilon$-approximate preparation. Together these show that the earlier linear-in-$s$ construction is optimal in the small-support regime, while in the large-support regime a sublinear dependence on $s$ is possible and comes with an unavoidable factor depending on $n$.

Load-bearing premise

The recursive cost accounting assumes each relabeling step costs only $O(\sqrt{(r-1)2^r})$ Toffoli gates, each peeling step only $O(\sqrt{(m-r)2^r}+\sqrt{b2^{r+1}}+m)$, and that all temporary ancillas can be reused in a single scratch space across recursive levels.

Editorial extensions

If this is right

  • For $s=O(n)$, the linear $O(s)$ upper bound is tight up to constants, so no sublinear T-count algorithm exists in the small-support regime.
  • For $\Omega(n)\le s\le 2^{n/2}$, the new construction matches the lower bound up to an $\widetilde{O}(n^{1/4})$ factor.
  • The sparse Boolean synthesis theorem stands on its own: any sparse Boolean function with $b$-bit output has the stated Toffoli and ancilla bounds in the NCT model.
  • Approximate preparation inherits the bounds with an added $\sqrt{s\log(1/\epsilon)}+\log(1/\epsilon)$ term.

Reading between the lines

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

  • Inference: the same prefix-compression and support-peeling recursion may transfer to sparse isometry synthesis and to coherent data-loading tasks where the support is known in advance, potentially giving sublinear non-Clifford cost there as well.
  • Inference: the W-state stabilizer argument suggests that other highly symmetric sparse families, such as Dicke states of fixed Hamming weight, may yield similar approximate lower bounds and could test optimality at intermediate $s$.
  • Inference: varying the balance parameter $c$ away from $\lceil\sqrt{n}\rceil$ could reveal whether the crossover near $s\approx n^{3/2}$ is an artifact of this particular choice or a genuine feature of the problem.
  • Inference: a partial Boolean-function synthesis that only needs correctness on the support might close part of the gap; the paper notes its current construction does not exploit this relaxation in the large-support regime.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 3 minor

Summary. The paper studies approximate preparation of s-sparse n-qubit pure states in the Clifford+T model, using T-count as the cost. It proves an upper bound (Theorem 9/Corollary 2) of O~(min{s, n^{3/4} sqrt(s)}) T gates for constant error, via a reduction in which a dense label state is prepared, the support strings are loaded by a sparse Boolean function synthesis theorem (Theorem 8), and the label register is erased by implementing the zero-extension of the inverse labeling map. Theorem 8 is proved by a small-support compression argument and a large-support recursive prefix-compression/peeling algorithm. The paper also proves lower bounds (Theorem 12): for 0<epsilon<=1/6 and 2<=s<=2^{n/2}, some s-sparse state requires Omega(min{s, sqrt(ns)}) T gates. The small-support lower bound uses the stabilizer nullity of W states and an overlap bound for stabilizer subgroups; the large-support lower bound uses a packing of uniform superpositions together with a counting argument from [GKW26]. A gap in the proof of the lower-bound range is identified below.

Significance. If the results hold, the paper gives the first sublinear-in-s T-count for sparse states with sufficiently large support, and establishes that linear T-count is unavoidable for s=O(n) and that an Omega(sqrt(ns)) barrier persists up to s=2^{n/2}; in the large-support regime the gap between upper and lower bounds is only an n^{1/4} factor. The support-aware synthesis theorem for sparse Boolean functions (Theorem 8) is a useful contribution in its own right, and the reduction from state preparation to label-prepare/load/erase is clean. The lower-bound machinery is standard but carefully applied. The main weakness is the proof gap in Theorem 12; because that gap is easily closed, the substantive contributions appear sound.

major comments (2)
  1. [Section 5.2, proof of Theorem 12] The second lower bound is not established over the full stated range 2<=s<=2^{n/2}. The proof splits into Lemma 18 (which requires s<=n) and Lemma 15 (which requires s>=Cn for an absolute constant C), so the interval n<s<Cn is not covered by either lemma. In this interval the claimed bound is Omega(min{s,sqrt(ns)})=Omega(n), whereas the first claim of Theorem 12 gives only Omega(sqrt(s log(1/epsilon)))=Omega(sqrt(n)). The small constant range 2<=s<4/(1-epsilon^2) is also not covered by Lemma 18, although there the first claim already provides a constant lower bound and this part is harmless. Because the abstract and conclusion repeat the universal claim, the proof must be repaired. A simple repair is to observe that for n<=s<Cn, the n-qubit state |W_n> has support size n<=s and is therefore s-sparse, and Lemma 18 with s=n gives, for large enough n, T_epsilon(|W_n>)=Omega(n)=Omega(min{s,sqrt(ns)}); the authors should add this case explicitly.
  2. [Section 5.2, proof of Theorem 12] The sentence 'The case s=O(n) is proved in Section 5.2, see Theorem 18' is inaccurate, since Lemma 18 has the hypothesis s<=n rather than s=O(n); the intermediate regime n<s<Cn is therefore not covered by the cited lemma. Please correct the split and reconcile the numbering (the result is Lemma 18, not Theorem 18).
minor comments (3)
  1. [Section 3, proof of Theorem 9] The text says 'By Theorem 7' where Lemma 7 is meant; the same numbering confusion appears in Section 5, where 'Theorem 18' refers to Lemma 18, and in Section 4, where 'Theorems 10 and 11' refer to Lemmas 10 and 11.
  2. [Section 4.1, Lemma 10] The claim that unary iteration implements H with O(2^{ell+1}) Toffoli gates and O(log s) ancillas could benefit from a precise construction or citation, because standard unary iteration uses a one-hot register of size 2^{ell+1}; if the intended method is the low-ancilla QROM variant of [KG25], a sentence describing the register reuse would remove ambiguity.
  3. [Section 3, proof of Theorem 9] In the simplification leading to Eq. (13), the term n^{1/4} sqrt(ell s) is dropped; a one-line justification of its dominance over n^{3/4} sqrt(s log(s/sqrt(n))) in the regime s>n^{3/2} log n, or keeping the unsimplified expression, would improve rigor.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the upper and lower bounds are derived from external synthesis/counting theorems and self-contained lemmas; the authors' earlier work is background only.

full rationale

I traced the derivation chain of the central claims. Theorem 9 reduces sparse-state preparation to dense label-state preparation on an O(log s)-qubit register using the external result [GKW26], support-string loading and label erasure implemented through Theorem 8, and the [RW26] sparse-support indexing lemma in the small-support case. Theorem 8 is proved from Lemma 10 and Lemma 11: Lemma 10 uses the [RW26] indexing circuit plus unary iteration, and Lemma 11 is a recursive prefix-compression/support-peeling argument whose non-recursive costs are bounded with the external Boolean-synthesis theorem [LKS24], the flag-decomposition bound [KG25], and leaf applications of Theorem 10 or Theorem 5. The lower bound Theorem 12 uses the external dense-state lower bound [GKW26], the external counting lemma [GKW26, Lem. 13], the external stabilizer-nullity fact [BCHK20], and the paper's own packing and stabilizer-overlap lemmas (Lemmas 14 and 17). None of these steps defines a target quantity in terms of the claimed outcome, and no parameter is fitted to data and then presented as a prediction. The authors' prior works [LL25, LLL25] appear only as background citations in the introduction and are not invoked anywhere in the proofs. The potential range gap for n < s < Cn identified by the skeptic is a correctness or quantification concern about the proof lemmas, not a circularity, so it does not affect the circularity score.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The paper introduces no new entities and no fitted parameters. It relies on external synthesis and counting theorems (GKW26, LKS24, RW26, BCHK20) which are cited and not rederived. The only algorithm parameter c = ⌈√n⌉ is a design choice, not a fit to data.

assumptions (6)
  • domain assumption Lemma 13 (GKW26): any family of ϵ-separated n-qubit states preparable with t T gates has size at most 2^{O(n²+t²)}.
    Used in Section 5.1 to derive the Ω(√(ns)) lower bound. External result taken as given.
  • domain assumption Theorem 4.1 (GKW26): worst-case T-count for n-qubit state preparation is Ω(√(2^n log(1/ε)) + log(1/ε)).
    Used in Theorem 12 first claim to get a lower bound for sparse states via a dense m-qubit state.
  • domain assumption BCHK20: the exact T-count of a pure state is at least its stabilizer nullity.
    Used in Lemma 18 to lower-bound the approximate T-count of W states.
  • domain assumption Lemma 5 (LKS24): any Boolean function F:{0,1}^n → {0,1}^b has an NCT implementation with O(√(b 2^n)) Toffoli gates and ancillas.
    Workhorse in the load step and in the recursive subroutines of the synthesis theorem.
  • domain assumption Lemma 6 (RW26): sparse-support indexing circuit W_S with O(s) Toffoli gates and O(log s) ancillas.
    Used in Lemma 10 and in the state-preparation erasure step.
  • standard math Each Toffoli gate has a constant-size Clifford+T decomposition.
    Standard fact used to convert all Toffoli-count bounds into T-count bounds.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Sparse Quantum State Preparation with Sublinear T-Count." pith.science (2026). https://pith.science/paper/DEPLQUUP

@misc{pith2026260800414,
  author       = {Pith},
  title        = {Pith review of: Sparse Quantum State Preparation with Sublinear T-Count},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/DEPLQUUP}},
  note         = {Machine review of arXiv:2608.00414}
}
abstract

We study the fault-tolerant cost of preparing sparse quantum states, measured by $T$-count in the Clifford+$T$ model. Here an $n$-qubit state is called $s$-sparse if it is supported on at most $s$ computational-basis states. For arbitrary $n$-qubit states, the optimal $T$-count is $\Theta(\sqrt{2^n\log(1/\epsilon)}+\log(1/\epsilon))$, but for $s$-sparse states the best previous upper bounds remained linear in $s$. We show that any $n$-qubit $s$-sparse state can be prepared up to error $\epsilon$ using $\widetilde{O}(\min\{s,\ n^{3/4}\sqrt{s}\}+\sqrt{s\log(1/\epsilon)}+\log(1/\epsilon))$ $T$ gates, giving the first sublinear dependence on $s$ once the support is sufficiently large. Our approach is based on a support-aware synthesis theorem for sparse Boolean functions, which may be of independent interest. We also prove that, for every $0<\epsilon\le 1/6$ and $2\le s\le 2^{n/2}$, sparse-state preparation requires $\Omega(\min\{s,\sqrt{ns}\})$ $T$ gates, showing that linear dependence on $s$ is unavoidable in the small-support regime and substantially narrowing the gap between the known upper and lower bounds within this parameter range.

Figures

Figures reproduced from arXiv: 2608.00414 by the authors.

Figure 1
Figure 1. Schematic relation between the known constant-error bounds on the worst-case [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Action of the sparse-support indexing circuit [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. High-level circuit for the small-support implementation of [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Prefix-compression step in Case 1 of the large-support recursion. The circuit computes [PITH_FULL_IMAGE:figures/full_fig_p011_4.png]
Figure 5
Figure 5. Figure 5: Support-peeling step in Case 2 of the large-support recursion. The circuit XORs [PITH_FULL_IMAGE:figures/full_fig_p012_5.png]

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

134 extracted references · 58 canonical work pages

  1. [1]

    Physical Review X , volume=

    Encoding electronic spectra in quantum circuits with linear T complexity , author=. Physical Review X , volume=. 2018 , publisher=

    2018

  2. [2]

    Physical Review A , volume=

    Advantages of using relative-phase Toffoli gates with an application to multiple control Toffoli optimization , author=. Physical Review A , volume=. 2016 , publisher=

    2016

  3. [3]

    the electronic journal of combinatorics , pages=

    An improved bound on the minimal number of edges in color-critical graphs , author=. the electronic journal of combinatorics , pages=

  4. [4]

    Resource-Efficient Synthesis of Sparse Quantum States

    Resource-Efficient Synthesis of Sparse Quantum States , author=. arXiv preprint arXiv:2508.05386 , year=

    work page Pith review arXiv

  5. [5]

    arXiv preprint arXiv:2601.09388 , year=

    Sparse quantum state preparation with improved Toffoli cost , author=. arXiv preprint arXiv:2601.09388 , year=

    arXiv

  6. [6]

    Quantum , volume=

    A game of surface codes: Large-scale quantum computing with lattice surgery , author=. Quantum , volume=. 2019 , publisher=

    2019

  7. [7]

    Problemy kibernetiki , volume=

    On the complexity of schemes in some bases containing nontrivial elements with zero weights , author=. Problemy kibernetiki , volume=

  8. [8]

    International Conference on Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes , pages=

    The multiplicative complexity of Boolean functions , author=. International Conference on Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes , pages=. 1988 , organization=

    1988

Show all 134 references
  1. [9]

    Quantum Science & Technology , volume=

    Lower bounds on the non-Clifford resources for quantum computations , author=. Quantum Science & Technology , volume=. 2020 , publisher=

    2020

  2. [10]

    arXiv e-prints , pages=

    Faster State Preparation with Randomization , author=. arXiv e-prints , pages=

  3. [11]

    arXiv preprint arXiv:2510.08518 , year=

    Randomized truncation of quantum states , author=. arXiv preprint arXiv:2510.08518 , year=

  4. [12]

    2010 , publisher=

    Quantum computation and quantum information , author=. 2010 , publisher=

    2010

  5. [13]

    Physical Review A—Atomic, Molecular, and Optical Physics , volume=

    Magic-state distillation with low overhead , author=. Physical Review A—Atomic, Molecular, and Optical Physics , volume=. 2012 , publisher=

    2012

  6. [14]

    Quantum , volume=

    Rise of conditionally clean ancillae for efficient quantum circuit constructions , author=. Quantum , volume=. 2025 , publisher=

    2025

  7. [15]

    Nature Communications , volume=

    Polylogarithmic-depth controlled-NOT gates without ancilla qubits , author=. Nature Communications , volume=. 2024 , publisher=

    2024

  8. [16]

    arXiv preprint arXiv:2402.05053 , year=

    Quantum circuit for multi-qubit toffoli gate with optimal resource , author=. arXiv preprint arXiv:2402.05053 , year=

    arXiv

  9. [17]

    IEEE Transactions on Quantum Engineering , volume=

    Quantum resources required to block-encode a matrix of classical data , author=. IEEE Transactions on Quantum Engineering , volume=. 2022 , publisher=

    2022

  10. [18]

    arXiv preprint arXiv:2506.16964 , year=

    Space-time tradeoff for sparse quantum state preparation , author=. arXiv preprint arXiv:2506.16964 , year=

    arXiv

  11. [19]

    arXiv preprint arXiv:2508.14470 , year=

    Preparation of Hamming-Weight-Preserving Quantum States with Log-Depth Quantum Circuits , author=. arXiv preprint arXiv:2508.14470 , year=

    arXiv

  12. [20]

    Eigenvalues and eigenfunctions of a linear chain of atoms , author=

    On the theory of metals, I. Eigenvalues and eigenfunctions of a linear chain of atoms , author=. Selected Works Of Hans A Bethe: (With Commentary) , pages=. 1997 , publisher=

    1997

  13. [21]

    Physical Review A , volume=

    Boundary energy of a Bose gas in one dimension , author=. Physical Review A , volume=. 1971 , publisher=

    1971

  14. [22]

    Journal of Soviet Mathematics , volume=

    Spectrum and scattering of excitations in the one-dimensional isotropic Heisenberg model , author=. Journal of Soviet Mathematics , volume=. 1984 , publisher=

    1984

  15. [23]

    1997 , publisher=

    Quantum inverse scattering method and correlation functions , author=. 1997 , publisher=

    1997

  16. [24]

    Journal of Physics A: Mathematical and General , volume=

    Boundary conditions for integrable quantum systems , author=. Journal of Physics A: Mathematical and General , volume=. 1988 , publisher=

    1988

  17. [25]

    arXiv preprint arXiv:2202.00054 , year=

    Quantum machine learning with subspace states , author=. arXiv preprint arXiv:2202.00054 , year=

    arXiv

  18. [26]

    Physical Review A , volume=

    Simulating physical phenomena by quantum networks , author=. Physical Review A , volume=. 2002 , publisher=

    2002

  19. [27]

    Physical Review A , volume=

    Solving strongly correlated electron models on a quantum computer , author=. Physical Review A , volume=. 2015 , publisher=

    2015

  20. [28]

    npj Quantum Information , volume=

    Alignment between initial state and mixer improves QAOA performance for constrained optimization , author=. npj Quantum Information , volume=. 2023 , publisher=

    2023

  21. [29]

    Trainability and expressivity of

    Monbroussou, L. Trainability and expressivity of. Quantum , volume=. 2025 , publisher=

    2025

  22. [30]

    2020 IEEE 50th International Symposium on Multiple-Valued Logic (ISMVL) , pages=

    Automatic uniform quantum state preparation using decision diagrams , author=. 2020 IEEE 50th International Symposium on Multiple-Valued Logic (ISMVL) , pages=. 2020 , organization=

    2020

  23. [31]

    arXiv preprint arXiv:2407.01671 , year=

    Quantum State Preparation via Free Binary Decision Diagram , author=. arXiv preprint arXiv:2407.01671 , year=

    arXiv

  24. [32]

    arXiv preprint arXiv:2507.17170 , year=

    Advancing Quantum State Preparation using LimTDD , author=. arXiv preprint arXiv:2507.17170 , year=

    arXiv

  25. [33]

    arXiv preprint arXiv:2507.14496 , year=

    Quantum State Preparation Based on LimTDD , author=. arXiv preprint arXiv:2507.14496 , year=

    arXiv

  26. [34]

    Local, expressive, quantum-number-preserving VQE ans

    Anselmetti, Gian-Luca R and Wierichs, David and Gogolin, Christian and Parrish, Robert M , journal=. Local, expressive, quantum-number-preserving VQE ans. 2021 , publisher=

    2021

  27. [35]

    Quantum , volume=

    Deterministic Bethe state preparation , author=. Quantum , volume=. 2024 , publisher=

    2024

  28. [36]

    Journal of Physics A: Mathematical and Theoretical , volume=

    Preparing exact eigenstates of the open XXZ chain on a quantum computer , author=. Journal of Physics A: Mathematical and Theoretical , volume=. 2022 , publisher=

    2022

  29. [37]

    Quantum , volume=

    The Bethe ansatz as a quantum circuit , author=. Quantum , volume=. 2024 , publisher=

    2024

  30. [38]

    PRX Quantum , volume=

    Preparing Bethe ansatz eigenstates on a quantum computer , author=. PRX Quantum , volume=. 2021 , publisher=

    2021

  31. [39]

    Quantum , volume=

    Algebraic bethe circuits , author=. Quantum , volume=. 2022 , publisher=

    2022

  32. [40]

    Journal of Physics A: Mathematical and Theoretical , volume=

    Bethe states on a quantum computer: success probability and correlation functions , author=. Journal of Physics A: Mathematical and Theoretical , volume=. 2022 , publisher=

    2022

  33. [41]

    Deterministic preparation of

    B. Deterministic preparation of. International Symposium on Fundamentals of Computation Theory , pages=. 2019 , organization=

    2019

  34. [42]

    Short-depth circuits for

    B. Short-depth circuits for. 2022 IEEE International Conference on Quantum Computing and Engineering (QCE) , pages=. 2022 , organization=

    2022

  35. [43]

    Depth-Efficient Quantum Circuit Synthesis for Deterministic

    Yuan, Pei and Zhang, Shengyu , journal=. Depth-Efficient Quantum Circuit Synthesis for Deterministic

  36. [44]

    A divide-and-conquer approach to

    Aktar, Shamminuj and B. A divide-and-conquer approach to. IEEE Transactions on Quantum Engineering , volume=. 2022 , publisher=

    2022

  37. [45]

    Quantum encoder for fixed-

    Farias, Renato MS and Maciel, Thiago O and Camilo, Giancarlo and Lin, Ruge and Ramos-Calderer, Sergi and Aolita, Leandro , journal=. Quantum encoder for fixed-. 2025 , publisher=

    2025

  38. [46]

    Physical Review Applied , volume=

    Reducing circuit depth in quantum state preparation for quantum simulation using measurements and feedforward , author=. Physical Review Applied , volume=. 2025 , publisher=

    2025

  39. [47]

    Quantum , volume=

    State preparation by shallow circuits using feed forward , author=. Quantum , volume=. 2024 , publisher=

    2024

  40. [48]

    arXiv preprint arXiv:2503.16208 , year=

    Constant-depth quantum circuits for arbitrary quantum state preparation via measurement and feedback , author=. arXiv preprint arXiv:2503.16208 , year=

    arXiv

  41. [49]

    arXiv preprint arXiv:2411.02782 , year=

    Practical, optimal preparation of general quantum state with exponentially improved robustness , author=. arXiv preprint arXiv:2411.02782 , year=

  42. [50]

    Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Quantum state preparation with optimal T-count , author=. Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2026 , organization=

    2026

  43. [51]

    Quantum , volume=

    Spacetime-efficient low-depth quantum state preparation with applications , author=. Quantum , volume=. 2024 , publisher=

    2024

  44. [52]

    Quantum , volume=

    Trading T gates for dirty qubits in state preparation and unitary synthesis , author=. Quantum , volume=. 2024 , publisher=

    2024

  45. [53]

    npj Quantum Information , volume=

    Circuit complexity of quantum access models for encoding classical data , author=. npj Quantum Information , volume=. 2024 , publisher=

    2024

  46. [54]

    Quantum , volume=

    Quantum state preparation for multivariate functions , author=. Quantum , volume=. 2025 , publisher=

    2025

  47. [55]

    npj Quantum Information , volume=

    Quantum generative adversarial networks for learning and loading random distributions , author=. npj Quantum Information , volume=. 2019 , publisher=

    2019

  48. [56]

    Physical Review Research , volume=

    Approximate amplitude encoding in shallow parameterized quantum circuits and its application to financial market indicators , author=. Physical Review Research , volume=. 2022 , publisher=

    2022

  49. [57]

    Physical Review Applied , volume=

    Deterministic and entanglement-efficient preparation of amplitude-encoded quantum registers , author=. Physical Review Applied , volume=. 2022 , publisher=

    2022

  50. [58]

    Physical Review A , volume=

    Efficient quantum state preparation with walsh series , author=. Physical Review A , volume=. 2024 , publisher=

    2024

  51. [59]

    Quantum , volume=

    The State Preparation of Multivariate Normal Distributions using Tree Tensor Network , author=. Quantum , volume=. 2025 , publisher=

    2025

  52. [60]

    npj Quantum Information , volume=

    Quantum state preparation of normal distributions using matrix product states , author=. npj Quantum Information , volume=. 2024 , publisher=

    2024

  53. [61]

    Quantum Science and Technology , volume=

    Quantum state preparation using tensor networks , author=. Quantum Science and Technology , volume=. 2023 , publisher=

    2023

  54. [62]

    Query and depth upper bounds for quantum unitaries via

    Rosenthal, Gregory , journal=. Query and depth upper bounds for quantum unitaries via

  55. [63]

    PRX quantum , volume=

    Optimal scaling quantum linear-systems solver via discrete adiabatic theorem , author=. PRX quantum , volume=. 2022 , publisher=

    2022

  56. [64]

    PRX quantum , volume=

    Grand unification of quantum algorithms , author=. PRX quantum , volume=. 2021 , publisher=

    2021

  57. [65]

    Proceedings of the 51st annual ACM SIGACT symposium on theory of computing , pages=

    Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics , author=. Proceedings of the 51st annual ACM SIGACT symposium on theory of computing , pages=

  58. [66]

    arXiv preprint arXiv:2108.06150 , year=

    Asymptotically Optimal Circuit Depth for Quantum State Preparation and General Unitary Synthesis , author=. arXiv preprint arXiv:2108.06150 , year=

    arXiv

  59. [67]

    52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) , pages =

    Li, Lvzhou and Luo, Jingquan , title =. 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) , pages =. 2025 , volume =. doi:10.4230/LIPIcs.ICALP.2025.113 , annote =

    2025 doi

  60. [68]

    Physical Review A , volume =

    Elementary gates for quantum computation , author =. Physical Review A , volume =. 1995 , month =. doi:10.1103/PhysRevA.52.3457 , url =

    1995 doi

  61. [69]

    Physical Review A , volume=

    Efficient deterministic preparation of quantum states using decision diagrams , author=. Physical Review A , volume=. 2022 , publisher=

    2022

  62. [70]

    Quantum Information Processing , volume=

    Double sparse quantum state preparation , author=. Quantum Information Processing , volume=. 2022 , publisher=

    2022

  63. [71]

    Physical Review A , volume=

    Quantum unary approach to option pricing , author=. Physical Review A , volume=. 2021 , publisher=

    2021

  64. [72]

    Physical Review A , volume=

    Toward optimal circuit size for sparse quantum state preparation , author=. Physical Review A , volume=. 2024 , publisher=

    2024

  65. [73]

    Physical Review A , volume=

    Simple quantum algorithm to efficiently prepare sparse states , author=. Physical Review A , volume=. 2024 , publisher=

    2024

  66. [74]

    22nd Annual IEEE Conference on Computational Complexity , pages=

    Quantum versus classical proofs and advice , author=. 22nd Annual IEEE Conference on Computational Complexity , pages=. 2007 , organization=

    2007

  67. [75]

    Classical Proofs and Subset Verification , author=

    Quantum vs. Classical Proofs and Subset Verification , author=. Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science , volume =

  68. [76]

    Proceedings of the 35th Annual Symposium on Foundations of Computer Science , pages=

    Algorithms for quantum computation: discrete logarithms and factoring , author=. Proceedings of the 35th Annual Symposium on Foundations of Computer Science , pages=. 1994 , organization=

    1994

  69. [77]

    Proceedings of the 28th Annual ACM Symposium on Theory of Computing , pages=

    A fast quantum mechanical algorithm for database search , author=. Proceedings of the 28th Annual ACM Symposium on Theory of Computing , pages=

  70. [78]

    Physical Review Letters , volume=

    Quantum algorithm for linear systems of equations , author=. Physical Review Letters , volume=. 2009 , publisher=

    2009

  71. [79]

    SIAM Journal on Computing , volume=

    Quantum algorithm for systems of linear equations with exponentially improved dependence on precision , author=. SIAM Journal on Computing , volume=. 2017 , publisher=

    2017

  72. [80]

    Proceedings of the National Academy of Sciences , volume=

    Toward the first quantum simulation with quantum speedup , author=. Proceedings of the National Academy of Sciences , volume=. 2018 , publisher=

    2018

  73. [81]

    Physical Review Letters , volume=

    Optimal Hamiltonian simulation by quantum signal processing , author=. Physical Review Letters , volume=. 2017 , publisher=

    2017

  74. [82]

    Quantum , volume=

    Hamiltonian simulation by qubitization , author=. Quantum , volume=. 2019 , publisher=

    2019

  75. [83]

    Physical Review Letters , volume=

    Simulating Hamiltonian dynamics with a truncated Taylor series , author=. Physical Review Letters , volume=. 2015 , publisher=

    2015

  76. [84]

    Nature Physics , volume=

    Quantum principal component analysis , author=. Nature Physics , volume=. 2014 , publisher=

    2014

  77. [85]

    Proceedings of the 8th Innovations in Theoretical Computer Science Conference , pages =

    Kerenidis, Iordanis and Prakash, Anupam , title =. Proceedings of the 8th Innovations in Theoretical Computer Science Conference , pages =. 2017 , volume =

    2017

  78. [86]

    Advances in Neural Information Processing Systems , volume=

    q-means: A quantum algorithm for unsupervised machine learning , author=. Advances in Neural Information Processing Systems , volume=

  79. [87]

    Physical Review A , volume=

    Quantum spectral clustering , author=. Physical Review A , volume=. 2021 , publisher=

    2021

  80. [88]

    Physical Review Letters , volume=

    Quantum support vector machine for big data classification , author=. Physical Review Letters , volume=. 2014 , publisher=

    2014

  81. [89]

    Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , pages=

    A quantum-inspired classical algorithm for recommendation systems , author=. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , pages=

  82. [90]

    Journal of the ACM , volume=

    Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning , author=. Journal of the ACM , volume=. 2022 , publisher=

    2022

  83. [91]

    Quantum , volume=

    An improved quantum-inspired algorithm for linear regression , author=. Quantum , volume=. 2022 , publisher=

    2022

  84. [92]

    Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science , pages =

    Chia, Nai-Hui and Li, Tongyang and Lin, Han-Hsuan and Wang, Chunhao , title =. Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science , pages =. 2020 , volume =

    2020

  85. [93]

    Physical Review Letters , volume=

    Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions , author=. Physical Review Letters , volume=. 2021 , publisher=

    2021

  86. [94]

    arXiv preprint quant-ph/0208112 , year=

    Creating superpositions that correspond to efficiently integrable probability distributions , author=. arXiv preprint quant-ph/0208112 , year=

    arXiv

  87. [95]

    Physical Review A , volume=

    Elementary gates for quantum computation , author=. Physical Review A , volume=. 1995 , publisher=

    1995

  88. [96]

    Physical Review A , volume=

    Quantum circuits with uniformly controlled one-qubit gates , author=. Physical Review A , volume=. 2005 , publisher=

    2005

  89. [97]

    Proceedings of the 2005 Asia and South Pacific Design Automation Conference , pages=

    Synthesis of quantum logic circuits , author=. Proceedings of the 2005 Asia and South Pacific Design Automation Conference , pages=

    2005

  90. [98]

    Physical Review A , volume=

    Quantum-state preparation with universal gate decompositions , author=. Physical Review A , volume=. 2011 , publisher=

    2011

  91. [99]

    Physical Review A , volume=

    Quantum circuits for isometries , author=. Physical Review A , volume=. 2016 , publisher=

    2016

  92. [100]

    Proceedings of the 58th ACM/IEEE Design Automation Conference , pages=

    An efficient algorithm for sparse quantum state preparation , author=. Proceedings of the 58th ACM/IEEE Design Automation Conference , pages=. 2021 , organization=

    2021

  93. [101]

    Quantum , volume=

    Quantum circuits for sparse isometries , author=. Quantum , volume=. 2021 , publisher=

    2021

  94. [102]

    IEEE Transactions on Quantum Engineering , volume=

    Efficient boolean methods for preparing uniform quantum states , author=. IEEE Transactions on Quantum Engineering , volume=. 2021 , publisher=

    2021

  95. [103]

    IEEE Transactions on Computers , volume=

    Circuit-based quantum random access memory for classical data with continuous amplitudes , author=. IEEE Transactions on Computers , volume=. 2020 , publisher=

    2020

  96. [104]

    Scientific Reports , volume=

    Circuit-based quantum random access memory for classical data , author=. Scientific Reports , volume=. 2019 , publisher=

    2019

  97. [105]

    Physical Review Letters , volume=

    Probabilistic quantum memories , author=. Physical Review Letters , volume=. 2001 , publisher=

    2001

  98. [106]

    Physical Review Letters , volume=

    Quantum state preparation with optimal circuit depth: Implementations and applications , author=. Physical Review Letters , volume=. 2022 , publisher=

    2022

  99. [107]

    IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , year=

    Asymptotically optimal circuit depth for quantum state preparation and general unitary synthesis , author=. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , year=

  100. [108]

    Quantum , volume=

    Optimal (controlled) quantum state preparation and improved unitary synthesis by quantum circuits with any number of ancillary qubits , author=. Quantum , volume=. 2023 , publisher=

    2023

  101. [109]

    Craig Gidney , title =

  102. [110]

    Proceedings Design, Automation and Test in Europe Conference and Exhibition , volume=

    Smaller two-qubit circuits for quantum communication and computation , author=. Proceedings Design, Automation and Test in Europe Conference and Exhibition , volume=. 2004 , organization=

    2004

  103. [111]

    npj Quantum Information , volume=

    Nearest centroid classification on a trapped ion quantum computer , author=. npj Quantum Information , volume=. 2021 , publisher=

    2021

  104. [112]

    arXiv preprint quant-ph/0210077 , year=

    Quantum NP-a survey , author=. arXiv preprint quant-ph/0210077 , year=

    arXiv

  105. [113]

    Proceedings of the 38th Annual ACM Symposium on Theory of Computing , pages=

    A polynomial quantum algorithm for approximating the Jones polynomial , author=. Proceedings of the 38th Annual ACM Symposium on Theory of Computing , pages=

  106. [114]

    SIAM Journal on Computing , volume=

    Strengths and weaknesses of quantum computing , author=. SIAM Journal on Computing , volume=. 1997 , publisher=

    1997

  107. [115]

    Quantum Information and Computation , volume=

    Optimal synthesis of linear reversible circuits , author=. Quantum Information and Computation , volume=. 2008 , publisher=

    2008

  108. [116]

    Journal of Computer and System Sciences , volume=

    On asymptotic gate complexity and depth of reversible circuits without additional memory , author=. Journal of Computer and System Sciences , volume=. 2017 , publisher=

    2017

  109. [117]

    2001 , publisher=

    Quantum computation and quantum information , author=. 2001 , publisher=

    2001

  110. [118]

    SIAM Journal on Computing , volume=

    Parallel quantum computation and quantum codes , author=. SIAM Journal on Computing , volume=. 2001 , publisher=

    2001

  111. [119]

    International Journal of Theoretical Physics , volume=

    Simulating physics with computers , author=. International Journal of Theoretical Physics , volume=

  112. [120]

    Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms , pages=

    Optimal space-depth trade-off of CNOT circuits in quantum logic synthesis , author=. Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2020 , organization=

    2020

  113. [121]

    Physical Review Letters , volume=

    Black-box quantum state preparation without arithmetic , author=. Physical Review Letters , volume=. 2019 , publisher=

    2019

  114. [122]

    Proceedings of IEEE International Conference on Quantum Computing and Engineering , pages=

    Efficient quantum circuits for accurate state preparation of smooth, differentiable functions , author=. Proceedings of IEEE International Conference on Quantum Computing and Engineering , pages=. 2020 , organization=

    2020

  115. [123]

    Quantum , volume=

    Efficient quantum amplitude encoding of polynomial functions , author=. Quantum , volume=. 2024 , publisher=

    2024

  116. [124]

    Quantum Information Processing , volume=

    Fast black-box quantum state preparation based on linear combination of unitaries , author=. Quantum Information Processing , volume=. 2021 , publisher=

    2021

  117. [125]

    Quantum , volume=

    Fast black-box quantum state preparation , author=. Quantum , volume=. 2022 , publisher=

    2022

  118. [126]

    IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , year=

    Low-rank quantum state preparation , author=. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , year=

  119. [127]

    arXiv preprint arXiv:2205.00519 , year=

    Preparing arbitrary continuous functions in quantum registers with logarithmic complexity , author=. arXiv preprint arXiv:2205.00519 , year=

    arXiv

  120. [128]

    Physical Review Research , volume=

    Quantum algorithms for approximate function loading , author=. Physical Review Research , volume=. 2023 , publisher=

    2023

  121. [129]

    arXiv preprint arXiv:2210.14892 , year=

    Quantum state preparation without coherent arithmetic , author=. arXiv preprint arXiv:2210.14892 , year=

    arXiv

  122. [130]

    Quantum Science and Technology , volume=

    Linear-depth quantum circuits for loading Fourier approximations of arbitrary functions , author=. Quantum Science and Technology , volume=. 2023 , publisher=

    2023

  123. [131]

    arXiv preprint arXiv:2302.06074 , year=

    Asymptotically optimal synthesis of reversible circuits , author=. arXiv preprint arXiv:2302.06074 , year=

    arXiv

  124. [132]

    ACM Computing Surveys , volume=

    Synthesis and optimization of reversible circuits—a survey , author=. ACM Computing Surveys , volume=. 2013 , publisher=

    2013

  125. [133]

    2018 , publisher=

    The theory of groups , author=. 2018 , publisher=

    2018

  126. [134]

    Journal of High Energy Physics , volume=

    How to build the thermofield double state , author=. Journal of High Energy Physics , volume=. 2019 , publisher=

    2019

Pith tools

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