Pith. sign in

REVIEW 2 major objections 3 minor 2 cited by

A distillation-teleportation protocol for fault-tolerant QRAM

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

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

Pith's one-line read The paper proves that a noisy QRAM device, queried polynomially many times, can implement the logical QRAM operation to arbitrary accuracy using only polynomial fault-tolerant quantum resources, at the price of an exponential classical…

desk verdict A genuine advance: first FT-QRAM protocol with poly(n) quantum overhead and 1/poly(n)-fidelity hardware, conditional on an honestly-flagged noise model; worth refereeing seriously. read the letter →

arxiv 2505.20265 v1 pith:MJNCTU3D submitted 2025-05-26 quant-ph

Alexander M. Dalzell , András Gilyén , Connor T. Hann , Sam McArdle , Grant Salton , Quynh T. Nguyen , Aleksander Kubica , Fernando G.S.L. Brandão This is my paper
classification quant-ph MSC 81P6868Q12 PACS 03.67.Lx03.67.Pp
keywords quantumrandomaccessmemoryfault-tolerantcomputationgateteleportationmagicstatedistillationpurityamplificationCliffordhierarchyQRAMresourcestatesclassicalupdaterule
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 tries to establish that a faulty, specialized QRAM device can be promoted to a fault-tolerant logical QRAM operation at only polynomial quantum cost, even when the device's fidelity is as low as $1/\operatorname{poly}(n)$. The protocol prepares many noisy $n$-qubit QRAM resource states, encodes and distills them on a small fault-tolerant processor, then teleports the logical QRAM gate into the computation. Because each teleportation leaves a correction that is itself a QRAM gate one level lower in the Clifford hierarchy, $n$ rounds of adaptive classical updates finish the job. If this works, the exponential quantum resources usually spent on error-correcting every component of a QRAM can be replaced by exponential classical computation, which may be much cheaper in practice.

What carries the argument

The central objects are the QRAM resource state $|\Psi(g)\rangle=V(g)|+\rangle^{\otimes n}$ and the update rule $\mathrm{UR}(g,m)=g\oplus g_{\oplus m}$, where $g_{\oplus m}(x)=g(x\oplus m)$. The update rule cancels the highest-degree monomials of $g$, so if $\deg(g)=d$ then $\deg(\mathrm{UR}(g,m))\le d-1$; hence $V(\mathrm{UR}(g,m))$ sits one level lower in the Clifford hierarchy and after $n$ rounds the correction becomes identity. Twirling with the partial Clifford set generated by $X$, $Z$, $CX$, and $CZ$ makes the prepared state's principal eigenvector exactly $|\Psi(g)\rangle$ with eigenvalue at least $F_{\min}$ under dataset-independent noise. Distillation uses state-agnostic quantum purity amplification: the iterated swap test for high-fidelity inputs, and a new streaming protocol based on density matrix exponentiation (a quantum PCA primitive) that matches the optimal $1/\varepsilon$ sample complexity in the low-fidelity regime.

What would settle it

Construct a bucket-brigade-style QRAM in which a stored bit 1 has a measurably different readout error rate from a stored bit 0, run the protocol's twirled preparation, and check whether the distilled state's principal eigenvector remains $|\Psi(g)\rangle$ with eigenvalue at least $1/\operatorname{poly}(n)$. A $g$-dependent noise channel that violates the factorization would make the eigenvalue guarantee fail for some $g$, and the teleportation channel would deviate from $V(f)$ by an amount detectable in diamond distance.

Watch

Extended reading notes

Core claim

Under the assumption that the physical QRAM device's noise is independent of the queried data table $g$ (Definition 1), the paper proves that for any $f$ and any $\varepsilon>0$ the logical diagonal QRAM operation $V(f)$ can be implemented up to diamond-norm error $\varepsilon$ using $O\!\left(\frac{n(1-F)}{F^2}\left(\frac{n}{\varepsilon}+\frac{1}{F}\right)\right)$ physical QRAM queries with fidelity $F\ge 1/\operatorname{poly}(n)$, plus $O(n^2 Q)$ fault-tolerant gates (Theorem 2). The key is to prepare resource states $|\Psi(g)\rangle=V(g)|+\rangle^{\otimes n}$ with the ideal state as principal eigenvector (via partial Clifford twirling), distill them, teleport the gate, and correct by the classical update rule $g\leftarrow g\oplus g_{\oplus m}$, whose degree drops by at least one each round. After at most $n$ rounds the correction is $\pm$ identity, so the protocol terminates. The exponential quantum savings come at the price of $n$ applications of an $O(2^n)$-cost classical update rule (plus $\operatorname{poly}(n)\,2^n$ twirling operations), exposing the open question of whether truly $\operatorname{poly}(n)$-cost fault-tolerant QRAM exists.

Load-bearing premise

The protocol collapses if the physical QRAM device's noise depends on which data table it is queried with; the whole argument assumes the noisy channel factorizes as $\mathcal{N}_2\circ\mathcal{V}(g)\circ\mathcal{N}_1$ with $\mathcal{N}_1,\mathcal{N}_2$ independent of $g$.

Editorial extensions

If this is right

  • If correct, any quantum algorithm that calls the QRAM operation $T=\operatorname{poly}(n)$ times can be run fault-tolerantly with $\operatorname{poly}(n)$ quantum resources, at the cost of taking $1/\varepsilon=O(T)$ and paying an overall $O(T^2)$ factor from distillation.
  • The protocol removes the need to actively error-correct all $\Omega(2^n)$ components of the QRAM; the exponential footprint moves into classical RAM and a physical QRAM device that only needs fidelity $1/\operatorname{poly}(n)$.
  • The $n$-round descent through the Clifford hierarchy is what circumvents the earlier no-go theorem against non-adaptive distillation-teleportation QRAM: each round queries a different, adaptively updated dataset.
  • The $b$-bit generalization (Appendix A) allows coherent reads of $b$ classical bits per address using resource states on $n+b$ qubits whose underlying Boolean function has degree at most $n+1$.
  • In cryptanalysis and chemistry applications, the protocol trades an exponential number of fault-tolerant Toffoli gates for classical computation, though currently with larger constant overhead than direct QROM circuits.

Reading between the lines

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

  • The paper's Fourier picture suggests a general principle: any fault-tolerant QRAM protocol that hides which address is being queried must globally update all $2^n$ entries of the classical dataset (or equivalently perform a fast Fourier transform over binary strings), hinting at a lower bound for fully $\operatorname{poly}(n)$-cost QRAM; this is our inference, not the paper's claim.
  • If an $\varepsilon$-independent or $\operatorname{polylog}(1/\varepsilon)$ distillation scheme for QRAM resource states is ever found, the $T^2$ bottleneck in applications disappears and the protocol would become competitive with existing QROM circuits; the paper lists this as desirable, and we flag it as the natural next target.
  • The new streaming purity-amplification protocol matches the optimal sample complexity with only two qudits of memory; outside QRAM, it may serve as a general tool for distilling other non-Clifford resource states, a transfer the paper does not develop.
  • One can test the noise model experimentally before building the full device: prepare the same physical QRAM with two different datasets $g$ and $g'$ and compare the output noise statistics; if the noise depends on the data, the assumed factorization $\mathcal{N}_2\circ\mathcal{V}(g)\circ\mathcal{N}_1$ fails and the protocol's guarantee breaks.
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

2 major / 3 minor

Summary. The paper presents an adaptive distillation–teleportation protocol for implementing a logical QRAM operation V(f) fault-tolerantly, using only poly(n) fault-tolerant quantum resources plus poly(n) queries to a specialized physical QRAM device whose noise is independent of the queried dataset. The protocol prepares noisy physical resource states, encodes them into a QEC code, applies a partial Clifford twirl, distills them with a streaming state-agnostic purity-amplification procedure, and then teleports the resource state into the computation. A classical update rule reduces the degree of the correction function by at least one per round, so after at most n rounds no correction remains. The main theorem (Theorem 2) states a query complexity Q = O(n(1-F)/F^2(n/ε + 1/F)) and a fault-tolerant gate overhead O(n^2 Q), assuming the physical QRAM device has fidelity at least F = 1/poly(n) under dataset-independent noise. The paper also analyzes the classical complexity of the update rule, connects it to the Walsh–Hadamard transform and sparse matrix-vector multiplication, and discusses applications in state preparation, machine learning, cryptanalysis, and chemistry.

Significance. If the central derivation is correct, this is a significant conceptual result: it is the first rigorous protocol showing that a specialized, noisy QRAM device with only 1/poly(n) fidelity can supply fault-tolerant logical QRAM with poly(n) quantum resources, at the price of exponential classical computation. The paper contains a long and mostly careful chain of proofs, explicitly tracks error propagation, and gives a new streaming quantum purity-amplification procedure that is of independent interest. The assumptions are stated transparently, and the protocol involves no fitted parameters: the resource counts are derived from the physical fidelity F, the noise rate p, and the target error ε. The main weaknesses are an internal inconsistency in the partial-Clifford-twirling identity (Proposition 3) and the load-bearing, physically unproven dataset-independence assumption (Definition 1). Both are fixable in principle, but they must be corrected before the stated theorem is established as written.

major comments (2)
  1. [Section 4.3, Proposition 3 (Eqs. (34)–(36))] There is an internal inconsistency in the twirling identity that is load-bearing for the protocol. The statement asserts |Ψ(g)⟩ = C|Ψ(g_C)⟩, but the proof in Eq. (36) establishes C|Ψ(g)⟩ = |Ψ(g_C)⟩: the identity M_A† X^u V(g) X^u M_A = V(g′) with g′(x) = g(Ax⊕u) conjugates in the opposite direction, and the displayed calculation C V(g)|+⟩ = V(g_C)|+⟩ is exactly the reversed relation. These two identities differ whenever C^2 ≠ I, which occurs already for n = 2 with A of order 3 and u = v = B = 0. Section 4.3.2 applies C after querying g_C and Eq. (43) defines the twirled state as E_C C ϕ(g_C) C†; this is correct only under the stated, unproved direction. Under the proved direction, the ideal post-C state has principal eigenvector C^2|Ψ(g)⟩ rather than |Ψ(g)⟩, so Proposition 5 and the correctness part of Theorem 2 are not established as written. The fix appears local—apply C† instead of C, or redefine the update g → g_C with the inverse affine transformation; because the uniform distribution over T is invariant under inversion, the subsequent spectral analysis should survive—but the manuscript must correct this and re-derive the affected claims.
  2. [Section 3.1, Definition 1] The dataset-independent noise assumption is load-bearing for the main theorem: Proposition 5 uses it to ensure that |Ψ(g)⟩ is the principal eigenvector of every twirled encoded state, and without this property the state-agnostic distillation step has no guarantee of converging to the correct resource state. The paper defends Definition 1 via the g-independent structure of routing and unrouting and gives a dead-router example, but Section 3.1 explicitly leaves the microscopic derivation to future work. In particular, readout noise that distinguishes the I gate from the X gate at a memory cell violates Eq. (13), and because the twirling set T is not the full Clifford group, the heuristic claim that partial Clifford twirling 'should remove dependence' of the noise on g is not proved. This does not invalidate the conditional theorem, but it means the advertised physical significance rests on an unproven modeling premise; a concrete architecture satisfying Definition 1, or a formal argument covering g-dependent readout errors, would substantially strengthen the claim.
minor comments (3)
  1. [Section 6.4] The text refers to 'Theorem 3' when discussing the scaling of the generalized protocol, but the manuscript states only Theorem 1 and Theorem 2; please label the generalized result or fix the reference.
  2. [Throughout] There are several copyediting issues: the author affiliation reads 'A WS Center' instead of 'AWS Center'; Section 4.5 contains 'obfuscatedured' instead of 'obfuscated'; and Appendix A has 'straightoforwardly' instead of 'straightforwardly'.
  3. [Circuit (42)] The circuit diagram for the twirling step is visually ambiguous: it appears to contain two C gates and the label 'C ϕ(g_C) C†' is hard to parse. Please clarify the gate order and, in light of the major comment above, specify explicitly whether the correction is C or C†.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central theorem is a conditional construction whose resource counts follow from explicit error propagation; the dataset-independent noise assumption is a stated model, not a conclusion derived from itself.

full rationale

The derivation chain is self-contained relative to its stated assumptions. Theorem 1/2 is explicitly conditional on Definition 1 (dataset-independent QRAM noise), and the paper does not claim to derive that assumption; Section 3.1 defends its plausibility and leaves microscopic derivation to future work, which is a validity caveat rather than circularity. Proposition 5 obtains the top-eigenvector property by partial Clifford twirling under that assumption, with the uniformity of Pauli spreading proven in Proposition 4 rather than assumed. The distillation step is state-agnostic (Section 4.4): it takes arbitrary mixed states and amplifies the principal eigenvector, and the copy counts in Propositions 6 and 10 are derived from density-matrix exponentiation and phase-estimation error bounds. Teleportation correctness (Proposition 11) is a direct channel-monotonicity argument, and the Clifford-hierarchy descent used by the update rule is proved self-contained in Appendix D. Resource counts Q and Q' are obtained by propagating errors through these steps with no fitted parameters; the Section 6 application estimates use explicit example values (e.g., F=50%) and are not presented as predictions. The cited prior work, including the no-go theorem used for motivation and the general encoding theorem (Ref. [59]), supplies external technical lemmas whose assumptions do not include the target protocol, so the central claim retains independent content.

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

The protocol's theorem is conditional on stated engineering assumptions (device noise independent of the dataset, reloadable device, transport of output qubits without significant degradation) and on standard FTQC background (threshold theorems, the general-code fault-tolerant encoding result of Ref. [59] quoted as Proposition 2). There are no fitted free parameters: F, p, and ε are inputs, and the query count Q and all error bounds are derived from them. The hidden constants in the threshold conditions (p below p0, pn^2 below a separate constant) are not quantified, which is standard for asymptotic FTQC analyses. No new physical entities are postulated: the QRAM resource state of Eq. (9) is a standard superposition state and the partial Clifford twirling set of Definition 4 is a mathematical construction.

assumptions (6)
  • domain assumption Dataset-independent QRAM noise (Definition 1): the noisy physical QRAM channel decomposes as eV(g) = N2 ∘ V(g) ∘ N1 with N1, N2 independent of the queried function g.
    Load-bearing for Proposition 5: partial Clifford twirling makes |Ψ(g)⟩ the principal eigenvector with eigenvalue at least Fmin. Defended by the routing and unrouting structure of shallow QRAM and a dead-router example (Section 3.1), but not derived from microscopic device models; the paper leaves this to future work.
  • domain assumption The physical QRAM device can be reloaded with a new dataset between queries, and the n-qubit output state can be moved to the main fault-tolerant processor without significant fidelity loss (Section 3).
    Required for the adaptive rounds (Section 4.6) and for transferring resource states from the device to the QEC processor. Stated as an assumption; no engineering analysis is provided.
  • standard math The main processor is subject to circuit-level stochastic noise (Definition 2), and the QEC code family has a threshold against local stochastic noise (Section 3.3, Eq. 18).
    Standard FTQC framework (Refs. 87 to 93); used to justify polylog suppression of logical errors and to apply the encoding result of Ref. [59] (Proposition 2).
  • standard math Fault-tolerant encoding with error ε_enc ≤ Γ(E) + 2√(cpn) + 2|E|(cp)^k exists for general codes (Proposition 2, from Ref. [59], Appendix B).
    External theorem used to derive Corollary 1, the multiplicative fidelity bound (1 - O(np) - O(n√p))F that connects physical fidelity to encoded fidelity.
  • standard math V(h) lies in the d-th level of the Clifford hierarchy when deg(h) = d, and deg(f XOR f XOR m) < deg(f); degree-0 functions give V proportional to I (Appendix D, Proposition 12).
    Algebraic facts proven in the paper that guarantee the correction gates descend the hierarchy and the protocol terminates after at most n rounds.
  • standard math Bucket-brigade QRAM noise resilience, overall infidelity O(qn^2) for per-component error q (Ref. [36]).
    Cited in Section 2.5.2 to estimate the per-component error requirement q = O(1/n^2) for the protocol to be practical at n near 36; not needed for the main theorem.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A distillation-teleportation protocol for fault-tolerant QRAM." pith.science (2026). https://pith.science/paper/MJNCTU3D

@misc{pith2026250520265,
  author       = {Pith},
  title        = {Pith review of: A distillation-teleportation protocol for fault-tolerant QRAM},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MJNCTU3D}},
  note         = {Machine review of arXiv:2505.20265}
}
abstract

We present a protocol for fault-tolerantly implementing the logical quantum random access memory (QRAM) operation, given access to a specialized, noisy QRAM device. For coherently accessing classical memories of size $2^n$, our protocol consumes only $\mathrm{poly}(n)$ fault-tolerant quantum resources (logical gates, logical qubits, quantum error correction cycles, etc.), avoiding the need to perform active error correction on all $\Omega(2^n)$ components of the QRAM device. This is the first rigorous conceptual demonstration that a specialized, noisy QRAM device could be useful for implementing a fault-tolerant quantum algorithm. In fact, the fidelity of the device can be as low as $1/\mathrm{poly}(n)$. The protocol queries the noisy QRAM device $\mathrm{poly}(n)$ times to prepare a sequence of $n$-qubit QRAM resource states, which are moved to a general-purpose $\mathrm{poly}(n)$-size processor to be encoded into a QEC code, distilled, and fault-tolerantly teleported into the computation. To aid this protocol, we develop a new gate-efficient streaming version of quantum purity amplification that matches the optimal sample complexity in a wide range of parameters and is therefore of independent interest. The exponential reduction in fault-tolerant quantum resources comes at the expense of an exponential quantity of purely classical complexity: each of the $n$ iterations of the protocol requires adaptively updating the $2^n$-size classical dataset and providing the noisy QRAM device with access to the updated dataset at the next iteration. While our protocol demonstrates that QRAM is more compatible with fault-tolerant quantum computation than previously thought, the need for significant classical computational complexity exposes potentially fundamental limitations to realizing a truly $\mathrm{poly}(n)$-cost fault-tolerant QRAM.

Figures

Figures reproduced from arXiv: 2505.20265 by the authors.

Figure 1
Figure 1. (a) Ideally, the physical QRAM operation [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Quantum circuit depiction of the protocol for implementing the logical diagonal QRAM operation [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗
Figure 3
Figure 3. Diagrammatic representation [98], and simplification of the four terms in Eq. (60). For a derivation by direct computation consider that TrS2 [(ς ⊗ ϱ)(IA ⊗ S)] = P i P (IAS1 ⊗ ⟨i|)(ς ⊗ ϱ)(IA ⊗ S)(IAS1 ⊗ |i⟩) which is i (ς(IA ⊗ |i⟩)) ⊗ (⟨i|ϱ) = P i ς(IA ⊗ |i⟩⟨i|ϱ) = ς(IA ⊗ ϱ). single-qubit gates |0⟩⟨0| ⊗ (cos(t)I − i sin(t)S) + |1⟩⟨1| ⊗ (i sin(t)I + cos(t)S) = −(eiθ+Y ⊗ I) CS (e−iθ−XZe iθ−X ⊗ I) CS (e−iθ+Y Ze iθ+Y ⊗ … view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: A simple procedure based on density matrix exponentiation for extracting the top eigenstate of an [PITH_FULL_IMAGE:figures/full_fig_p029_4.png]
Figure 5
Figure 5. Figure 5: Step-by-step action of the O(n)-depth classical circuit that implements the update rule g 7→ h = g⊕g ⊕m, for a particular n = 3 example input with m = (1, 0, 1). Each box stores one bit of information, and each step modifies some subset of these bits with parallelized …

Discussion (0). Sign in to comment.

Forward citations

Cited by 2 Pith papers

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

  1. Quantum and classical algorithms for SOCP based on the multiplicative weights update method

    quant-ph 2025-07 conditional novelty 7.0 of 10

    A quantum algorithm solves SOCPs with O~(√r γ^5 + √m γ^4) queries and a classical algorithm uses O~(n γ^4 + m γ^6) samples, nearly matching LP complexity.

  2. The vast world of quantum advantage

    quant-ph 2025-08 conditional novelty 4.0 of 10

    Assuming quantum computers are strictly more powerful than classical ones, the problem of deciding whether a given quantum circuit beats a specific classical simulation heuristic is solvable by quantum computers but n...

Reference graph

Works this paper leans on

130 extracted references · 16 canonical work pages · cited by 2 Pith papers

  1. [8]

    QRAM: A survey and critique

    Jaques, S. and Rattew, A. G. “QRAM: A survey and critique.” arXiv:2305.10310 (2023)

    arXiv 2023

  2. [1]

    Electronic digital computers

    Williams, F. C. and Kilburn, T. “Electronic digital computers.”Nature 162 (1948), 487–487

    1948

  3. [2]

    A storage system for use with binary-digital computing machines

    C., W. F. and T., K. “A storage system for use with binary-digital computing machines.”Proceedings of the IEE—part II: power engineering96 (1949), 183–200

    1949

  4. [3]

    Milestones: Manchester University “Baby”’ computer and its derivatives, 1948–1951

    Engineering and Technology History Wiki. Milestones: Manchester University “Baby”’ computer and its derivatives, 1948–1951. https : / / ethw . org / Milestones : Manchester _ University _ %22Baby % 22 _ Computer_and_its_Derivatives,_1948-1951, accessed 2025-03-17. (2022)

    2022

  5. [4]

    Full stack optimization of transformer inference

    Kim, S., Hooper, C., Wattanawong, T., Kang, M., Yan, R., Genc, H., Dinh, G., Huang, Q., Keutzer, K., Mahoney, M. W., Shao, S., and Gholami, A. “Full stack optimization of transformer inference.” In:Archi- tecture and System Support for Transformer Models (ASSYST)(2023). https://openreview.net/forum? id=GtyQbLUUagE, accessed: 2025-03-17. arXiv:2302.14017

    arXiv 2023

  6. [5]

    Asurveyondeeplearninghardwareacceleratorsforheterogeneous HPC platforms

    Silvano,C.,Ielmini,D.,Ferrandi,F.,etal.“Asurveyondeeplearninghardwareacceleratorsforheterogeneous HPC platforms.” ACM Comput. Surv.(2025). arXiv:2306.15552

    arXiv 2025

  7. [6]

    CY7C1069G-10BVXIT

    Infineon. CY7C1069G-10BVXIT. https://www.infineon.com/cms/en/product/memories/sram-static- ram/asynchronous-sram/cy7c1069g-10bvxit/, accessed: 2025-03-17. (2025)

    2025

  8. [7]

    Quantum random access memory

    Giovannetti, V., Lloyd, S., and Maccone, L. “Quantum random access memory.”Phys. Rev. Lett.100 (2008), 160501. arXiv:0708.1879. 63

    arXiv 2008

Show all 130 references
  1. [9]

    Quantum machine learning: A classical perspective

    Ciliberto, C., Herbster, M., Ialongo, A. D., Pontil, M., Rocchetto, A., Severini, S., and Wossnig, L. “Quantum machine learning: A classical perspective.”Proc. R. Soc. A474 (2018), 20170551. arXiv:1707.08561

    2018 arXiv

  2. [10]

    Quantum machine learning

    Biamonte, J., Wittek, P., Pancotti, N., Rebentrost, P., Wiebe, N., and Lloyd, S. “Quantum machine learning.” Nature 549 (2017), 195–202. arXiv:1611.09347

    2017 arXiv

  3. [11]

    M., McArdle, S., Berta, M., Bienias, P., Chen, C.-F., Gilyén, A., Hann, C

    Dalzell, A. M., McArdle, S., Berta, M., Bienias, P., Chen, C.-F., Gilyén, A., Hann, C. T., Kastoryano, M. J., Khabiboulline, E. T., Kubica, A., Salton, G., Wang, S., and Brandão, F. G. S. L.Quantum algorithms: A survey of applications and end-to-end complexities. Cambridge Uni...

    2025 arXiv

  4. [12]

    Quantum support vector machine for big data classification

    Rebentrost, P., Mohseni, M., and Lloyd, S. “Quantum support vector machine for big data classification.” Phys. Rev. Lett.113 (2014), 130503. arXiv:1307.0471

    2014 arXiv

  5. [13]

    Quantum-assisted Gaussian process regression

    Zhao, Z., Fitzsimons, J. K., and Fitzsimons, J. F. “Quantum-assisted Gaussian process regression.”Phys. Rev. A99 (2019), 052331. arXiv:1512.03929

    2019 arXiv

  6. [14]

    Quantum recommendation systems

    Kerenidis, I. and Prakash, A. “Quantum recommendation systems.” In: ITCS (2017), 49:1–49:21. arXiv:1603.08675

    2017 arXiv

  7. [15]

    High-order quantum algorithm for solving linear differential equations

    Berry, D. W. “High-order quantum algorithm for solving linear differential equations.”J. Phys. A47 (2014), 105301. arXiv:1010.2745

    2014 arXiv

  8. [16]

    Quantum algorithm for linear differential equa- tions with exponentially improved dependence on precision

    Berry, D. W., Childs, A. M., Ostrander, A., and Wang, G. “Quantum algorithm for linear differential equa- tions with exponentially improved dependence on precision.”Commun. Math. Phys.356 (2017), 1057–1081. arXiv:1701.03684

    2017 arXiv

  9. [17]

    Quantum spectral methods for differential equations

    Childs, A. M. and Liu, J.-P. “Quantum spectral methods for differential equations.”Commun. Math. Phys. 375 (2020), 1427–1457. arXiv:1901.00961

    2020 arXiv

  10. [18]

    Improved quantum algorithms for linear and nonlinear differential equations

    Krovi, H. “Improved quantum algorithms for linear and nonlinear differential equations.”Quantum 7 (2023),

    2023

  11. [19]

    The cost of solving linear differential equations on a quantum computer: Fast-forwarding to explicit resource counts

    Jennings, D., Lostaglio, M., Lowrie, R. B., Pallister, S., and Sornborger, A. T. “The cost of solving linear differential equations on a quantum computer: Fast-forwarding to explicit resource counts.”Quantum 8 (2024), 1553. arXiv:2309.07881

    2024 arXiv

  12. [20]

    Quantum algorithm for time-dependent differential equations using Dyson series

    Berry, D. W. and C. S. Costa, P. “Quantum algorithm for time-dependent differential equations using Dyson series.” Quantum 8 (2024), 1369. arXiv:2212.03544

    2024 arXiv

  13. [21]

    Quantum algorithm for linear systems of equations

    Harrow, A. W., Hassidim, A., and Lloyd, S. “Quantum algorithm for linear systems of equations.”Phys. Rev. Lett.103 (2009), 150502. arXiv:0811.3171

    2009 arXiv

  14. [22]

    Quantum speed-ups for solving semidefinite programs

    Brandão, F. G. S. L. and Svore, K. M. “Quantum speed-ups for solving semidefinite programs.” In:FOCS (2017), 415–426. arXiv:1609.05537

    2017 arXiv

  15. [23]

    Quantum SDP solvers: Large speed-ups, optimality, and applications to quantum learning

    Brandão, F. G. S. L., Kalev, A., Li, T., Lin, C. Y.-Y., Svore, K. M., and Wu, X. “Quantum SDP solvers: Large speed-ups, optimality, and applications to quantum learning.” In: ICALP (2019), 27:1–27:14. arXiv:1710.02581

    2019 arXiv

  16. [24]

    Quantum SDP-solvers: Better upper and lower bounds

    van Apeldoorn, J., Gilyén, A., Gribling, S., and de Wolf, R. “Quantum SDP-solvers: Better upper and lower bounds.” Quantum 4 (2020), 230. Earlier version inFOCS’17. arXiv:1705.01843

    2020 arXiv

  17. [25]

    Quantum algorithms for zero-sum games

    van Apeldoorn, J. and Gilyén, A. “Quantum algorithms for zero-sum games.” arXiv:1904.03180 (2019)

    2019 arXiv

  18. [26]

    Improvements in quantum SDP-solving with applications

    van Apeldoorn, J. and Gilyén, A. “Improvements in quantum SDP-solving with applications.” In:ICALP (2019), 99:1–99:15. arXiv:1804.05058

    2019 arXiv

  19. [27]

    A quantum interior point method for LPs and SDPs

    Kerenidis, I. and Prakash, A. “A quantum interior point method for LPs and SDPs.”ACM Trans. Quantum Comput. 1 (2020). arXiv:1808.09266

    2020 arXiv

  20. [28]

    Quantum algorithms for second-order cone programming and support vector machines

    Kerenidis, I., Prakash, A., and Szilágyi, D. “Quantum algorithms for second-order cone programming and support vector machines.”Quantum 5 (2021), 427. arXiv:1908.06720

    2021 arXiv

  21. [29]

    Quantum interior point methods for semidef- inite optimization

    Augustino, B., Nannicini, G., Terlaky, T., and Zuluaga, L. F. “Quantum interior point methods for semidef- inite optimization.” Quantum 7 (2023), 1110. arXiv:2112.06025

    2023 arXiv

  22. [30]

    Quantum algorithms for portfolio optimization

    Kerenidis, I., Prakash, A., and Szilágyi, D. “Quantum algorithms for portfolio optimization.” In:AFT (2019), 147–155. arXiv:1908.08040

    2019 arXiv

  23. [31]

    End-to-end resource analysis for quantum interior-point methods and portfolio optimization

    Dalzell, A. M., Clader, B. D., Salton, G., Berta, M., Lin, C. Y.-Y., Bader, D. A., Stamatopoulos, N., Schuetz, M. J. A., Brandão, F. G. S. L., Katzgraber, H. G., and Zeng, W. J. “End-to-end resource analysis for quantum interior-point methods and portfolio optimization.”PRX Qu...

    2023 arXiv

  24. [32]

    On the robustness of bucket brigade quantum RAM

    Arunachalam, S., Gheorghiu, V., Jochym-O’Connor, T., Mosca, M., and Srinivasan, P. V. “On the robustness of bucket brigade quantum RAM.”New J. Phys.17 (2015), 123010. arXiv:1502.03450

    2015 arXiv

  25. [33]

    Racinginparallel:Quantumversusclassical

    Steiger,D.S.andTroyer,M.“Racinginparallel:Quantumversusclassical.” In: APS March Meeting Abstracts (2016), H44–010. 64

    2016

  26. [34]

    Fault-tolerant resource estimation of quantum random-access memories

    Di Matteo, O., Gheorghiu, V., and Mosca, M. “Fault-tolerant resource estimation of quantum random-access memories.” IEEE Trans. Quantum Eng.1 (2020), 1–13. arXiv:1902.01329

    2020 arXiv

  27. [35]

    Parallelizing the queries in a bucket-brigade quantum random access memory

    Paler, A., Oumarou, O., and Basmadjian, R. “Parallelizing the queries in a bucket-brigade quantum random access memory.” Phys. Rev. A102 (2020), 032608. arXiv:2002.09340

    2020 arXiv

  28. [36]

    Resilience of quantum random access memory to generic noise

    Hann, C. T., Lee, G., Girvin, S., and Jiang, L. “Resilience of quantum random access memory to generic noise.” PRX Quantum2 (2021), 020311. arXiv:2012.05340

    2021 arXiv

  29. [37]

    A quantum random access memory (qram) using a polynomial encoding of binary strings

    Mukhopadhyay, P. “A quantum random access memory (qram) using a polynomial encoding of binary strings.” Sci. Rep.15 (2025), 11002. arXiv:2408.16794

    2025 arXiv

  30. [38]

    Trading T gates for dirty qubits in state preparation and unitary synthesis

    Low, G. H., Kliuchnikov, V., and Schaeffer, L. “Trading T gates for dirty qubits in state preparation and unitary synthesis.”Quantum 8 (2024), 1375. arXiv:1812.00954

    2024 arXiv

  31. [39]

    Jaeger, R. C. and Blalock, T. N.Microelectronic circuit design. McGraw-Hill New York (2016)

    2016

  32. [40]

    Fundamental causal bounds of quantum random access memories

    Wang, Y., Alexeev, Y., Jiang, L., Chong, F. T., and Liu, J. “Fundamental causal bounds of quantum random access memories.” npj Quant. Inf.10 (2024), 71. arXiv:2307.13460

    2024 arXiv

  33. [41]

    Semi-Clifford operations, structure ofCk hierarchy, and gate com- plexity for fault-tolerant quantum computation

    Zeng, B., Chen, X., and Chuang, I. L. “Semi-Clifford operations, structure ofCk hierarchy, and gate com- plexity for fault-tolerant quantum computation.”Phys. Rev. A77 (2008), 042313. arXiv:0712.2084

    2008 arXiv

  34. [42]

    Distillation with sublogarithmic overhead

    Hastings, M. B. and Haah, J. “Distillation with sublogarithmic overhead.” Phys. Rev. Lett. 120 (2018), 050504. arXiv:1709.03543

    2018 arXiv

  35. [43]

    Universal transversal gates with color codes: A simplified approach

    Kubica, A. and Beverland, M. E. “Universal transversal gates with color codes: A simplified approach.”Phys. Rev. A91 (2015), 032330. arXiv:1410.0069

    2015 arXiv

  36. [44]

    The smallest code with transversal T

    Koutsioumpas, S., Banfield, D., and Kay, A. “The smallest code with transversal T.” arXiv:2210.14066 (2022)

    2022 arXiv

  37. [45]

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

    Kuperberg, G. “Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem.” In: TQC (2013), 20–34. arXiv:1112.3333

    2013 arXiv

  38. [46]

    Diagonal gates in the Clifford hierarchy

    Cui, S. X., Gottesman, D., and Krishna, A. “Diagonal gates in the Clifford hierarchy.”Phys. Rev. A95 (2017), 012329. arXiv:1608.06596

    2017 arXiv

  39. [47]

    Surface code quantum computing by lattice surgery

    Horsman, D., Fowler, A. G., Devitt, S., and Meter, R. V. “Surface code quantum computing by lattice surgery.” New J. Phys.14 (2012), 123011. arXiv:1111.4022

    2012 arXiv

  40. [48]

    A magic state’s fidelity can be superior to the operations that created it

    Li, Y. “A magic state’s fidelity can be superior to the operations that created it.”New J. Phys.17 (2015), 023037. arXiv:1410.7808

    2015 arXiv

  41. [49]

    Simple scheme for encoding and decoding a qubit in unknown state for various topological codes

    Łodyga, J., Mazurek, P., Grudka, A., and Horodecki, M. “Simple scheme for encoding and decoding a qubit in unknown state for various topological codes.”Sci. Rep.5 (2015), 8975. arXiv:1404.2495

    2015 arXiv

  42. [50]

    Magic state distillation: Not as costly as you think

    Litinski, D. “Magic state distillation: Not as costly as you think.”Quantum 3 (2019), 205. arXiv:1905.06903

    2019 arXiv

  43. [51]

    Universal quantum computation with ideal Clifford gates and noisy ancillas

    Bravyi, S. and Kitaev, A. “Universal quantum computation with ideal Clifford gates and noisy ancillas.” Phys. Rev. A71 (2005), 022316. arXiv:quant-ph/0403025

    2005 arXiv

  44. [52]

    Fault-tolerant postselected quantum computation: Schemes

    Knill, E. “Fault-tolerant postselected quantum computation: Schemes.” arXiv:quant-ph/0402171 (2004)

    2004 arXiv

  45. [53]

    Topological quantum distillation

    Bombín, H. and Martin-Delgado, M. A. “Topological quantum distillation.” Phys. Rev. Lett. 97 (2006), 180501. arXiv:quant-ph/0605138

    2006 arXiv

  46. [54]

    Unfolding the color code

    Kubica, A., Yoshida, B., and Pastawski, F. “Unfolding the color code.”New J. Phys.17 (2015), 083026. arXiv:1503.02065

    2015 arXiv

  47. [55]

    Transversal Clifford gates on folded surface codes

    Moussa, J. E. “Transversal Clifford gates on folded surface codes.” Phys. Rev. A 94 (2016), 042316. arXiv:1603.02286

    2016 arXiv

  48. [56]

    A game of surface codes: large-scale quantum computing with lattice surgery

    Litinski, D. “A game of surface codes: large-scale quantum computing with lattice surgery.” Quantum 3 (2019), 128. arXiv:1808.02892

    2019 arXiv

  49. [57]

    Flexible layout of surface code computations using AutoCCZ states

    Gidney, C. and Fowler, A. G. “Flexible layout of surface code computations using AutoCCZ states.” arXiv:1905.08916 (2019)

    2019 arXiv

  50. [58]

    Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations

    Gottesman, D. and Chuang, I. L. “Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations.”Nature 402 (1999), 390–393. arXiv:quant-ph/9908010

    1999 arXiv

  51. [59]

    Fault-tolerant quantum input/output

    Christandl, M., Fawzi, O., and Goswami, A. “Fault-tolerant quantum input/output.” arXiv: 2408.05260 (2024)

    2024

  52. [60]

    Constant-overhead magic state distillation

    Wills, A., Hsieh, M.-H., and Yamasaki, H. “Constant-overhead magic state distillation.” arXiv:2408.07764 (2024)

    2024 arXiv

  53. [61]

    Good binary quantum codes with transversal ccz gate

    Nguyen, Q. T. “Good binary quantum codes with transversal ccz gate.” arXiv:2408.10140 (2024)

    2024 arXiv

  54. [62]

    Asymptotically good quantum codes with transversal non-Clifford gates

    Golowich, L. and Guruswami, V. “Asymptotically good quantum codes with transversal non-Clifford gates.” arXiv:2408.09254 (2024)

    2024 arXiv

  55. [63]

    Optimal purification of single qubits

    Cirac, J. I., Ekert, A. K., and Macchiavello, C. “Optimal purification of single qubits.”Phys. Rev. Lett.82 (1999), 4344–4347. arXiv:quant-ph/9812075. 65

    1999 arXiv

  56. [64]

    The rate of optimal purification procedures

    Keyl, M. and Werner, R. F. “The rate of optimal purification procedures.”Annales Henri Poincaré2 (2001), 1–26. arXiv:quant-ph/9910124

    2001 arXiv

  57. [65]

    Optimal probabilistic cloning and purification of quantum states

    Fiurášek, J. “Optimal probabilistic cloning and purification of quantum states.” Phys. Rev. A70 (2004), 032308. arXiv:quant-ph/0403165

    2004 arXiv

  58. [66]

    Quantum state purification

    Fu, H. “Quantum state purification.” MA thesis: University of Waterloo (2016)

    2016

  59. [67]

    Streaming quantum state purification

    Childs, A. M., Fu, H., Leung, D., Li, Z., Ozols, M., and Vyas, V. “Streaming quantum state purification.” Quantum 9 (2025), 1603. arXiv:2309.16387

    2025 arXiv

  60. [68]

    Optimal quantum purity amplification

    Li, Z., Fu, H., Isogawa, T., and Chuang, I. “Optimal quantum purity amplification.” arXiv: 2409.18167 (2024)

    2024

  61. [69]

    Streaming quantum state purification for general mixed states

    Grier, D., Leung, D., Li, Z., Pashayan, H., and Schaeffer, L. “Streaming quantum state purification for general mixed states.” arXiv:2503.22644 (2025)

    2025 arXiv

  62. [70]

    Quantum search-to-decision reductions and the state synthesis problem

    Irani, S., Natarajan, A., Nirkhe, C., Rao, S., and Yuen, H. “Quantum search-to-decision reductions and the state synthesis problem.” In:CCC (2022). arXiv:2111.02999

    2022 arXiv

  63. [71]

    Quantum principal component analysis

    Lloyd, S., Mohseni, M., and Rebentrost, P. “Quantum principal component analysis.”Nat. Phys.10 (2014), 631–633. arXiv:1307.0401

    2014 arXiv

  64. [72]

    Hamiltonian simulation with optimal sample complexity

    Kimmel, S., Lin, C. Y.-Y., Low, G. H., Ozols, M., and Yoder, T. J. “Hamiltonian simulation with optimal sample complexity.”npj Quant. Inf.3 (2017), 13. arXiv:1608.00281

    2017 arXiv

  65. [73]

    Focus beyond quadratic speedups for error-corrected quantum advantage

    Babbush, R., McClean, J. R., Newman, M., Gidney, C., Boixo, S., and Neven, H. “Focus beyond quadratic speedups for error-corrected quantum advantage.”PRX Quantum2 (2021), 010103. arXiv:2011.04149

    2021 arXiv

  66. [74]

    Encoding electronic spectra in quantum circuits with linear T complexity

    Babbush, R., Gidney, C., Berry, D. W., Wiebe, N., McClean, J., Paler, A., Fowler, A., and Neven, H. “Encoding electronic spectra in quantum circuits with linear T complexity.”Phys. Rev. X8 (2018), 041015. arXiv:1805.03662

    2018 arXiv

  67. [75]

    Architectures for a quantum random access memory

    Giovannetti, V., Lloyd, S., and Maccone, L. “Architectures for a quantum random access memory.”Phys. Rev. A78 (2008), 052310. arXiv:0807.4994

    2008 arXiv

  68. [76]

    Nielsen, M. A. and Chuang, I. L.Quantum computation and quantum information. Cambridge University Press (2000)

    2000

  69. [77]

    Quantum random access memory architectures using 3d superconducting cavities

    Weiss, D., Puri, S., and Girvin, S. “Quantum random access memory architectures using 3d superconducting cavities.” PRX Quantum5 (2024), 020312. arXiv:2310.08288

    2024 arXiv

  70. [78]

    Hardware- efficient quantum random access memory with hybrid quantum acoustic systems

    Hann, C. T., Zou, C.-L., Zhang, Y., Chu, Y., Schoelkopf, R. J., Girvin, S. M., and Jiang, L. “Hardware- efficient quantum random access memory with hybrid quantum acoustic systems.”Phys. Rev. Lett. 123 (2019), 250501. arXiv:1906.11340

    2019 arXiv

  71. [79]

    Quantum random access memory with transmon-controlled phonon routing

    Wang, Z., Qiao, H., Cleland, A. N., and Jiang, L. “Quantum random access memory with transmon-controlled phonon routing.” arXiv:2411.00719 (2024)

    2024 arXiv

  72. [80]

    A transmon based quantum switch for a quantum random access memory

    Sala Cadellans, A. “A transmon based quantum switch for a quantum random access memory.” MA thesis: Leiden University (2015)

    2015

  73. [81]

    Scalable and high-fidelity quantum random access memory in spin-photon networks

    Chen, K. C., Dai, W., Errando-Herranz, C., Lloyd, S., and Englund, D. “Scalable and high-fidelity quantum random access memory in spin-photon networks.”PRX Quantum2 (2021), 030319. arXiv:2103.07623

    2021 arXiv

  74. [82]

    Robust quantum random access memory

    Hong, F.-Y., Xiang, Y., Zhu, Z.-Y., Jiang, L.-z., and Wu, L.-n. “Robust quantum random access memory.” Phys. Rev. A86 (2012), 010306. arXiv:1201.2250

    2012 arXiv

  75. [83]

    Fast and error-correctable quantum RAM

    Cesa, F., Bernien, H., and Pichler, H. “Fast and error-correctable quantum RAM.” arXiv:2503.19172 (2025)

    2025 arXiv

  76. [84]

    Pseudorandom quantum states

    Ji, Z., Liu, Y.-K., and Song, F. “Pseudorandom quantum states.” In: CRYPTO (2018), 126–152. arXiv:1711.00385

    2018 arXiv

  77. [85]

    (Pseudo) random quantum states with binary phase

    Brakerski, Z. and Shmueli, O. “(Pseudo) random quantum states with binary phase.” In:Theory of Cryp- tography (2019), 229–250. arXiv:1906.10611

    2019 arXiv

  78. [86]

    Optimal algorithms for learning quantum phase states

    Arunachalam, S., Bravyi, S., Dutt, A., and Yoder, T. J. “Optimal algorithms for learning quantum phase states.” In: TQC (2023), 3:1–3:24. arXiv:2208.07851

    2023 arXiv

  79. [87]

    Fault-tolerant quantum computation with constant error rate

    Aharonov, D. and Ben-Or, M. “Fault-tolerant quantum computation with constant error rate.” SIAM J. Comp. 38 (2008), 1207–1282. Earlier version inSTOC’97. arXiv:quant-ph/9906129

    2008 arXiv

  80. [88]

    Fault-tolerant quantum computation

    Shor, P. W. “Fault-tolerant quantum computation.” In:FOCS (1996), 56–65. arXiv:quant-ph/9605011

    1996 arXiv

  81. [89]

    Fault-tolerant quantum computation with constant overhead

    Gottesman, D. “Fault-tolerant quantum computation with constant overhead.”Quantum Inf. Comput.14 (2014), 1338–1372. arXiv:1310.2984

    2014 arXiv

  82. [90]

    An introduction to quantum error correction and fault-tolerant quantum computation

    Gottesman, D. “An introduction to quantum error correction and fault-tolerant quantum computation.” In: Proceedings of Symposia in Applied Mathematics(2010), 13–58. arXiv:0904.2557

    2010 arXiv

  83. [91]

    Constant overhead quantum fault tolerance with quantum expander codes

    Fawzi, O., Grospellier, A., and Leverrier, A. “Constant overhead quantum fault tolerance with quantum expander codes.” Commun. ACM 64 (2020), 106–114. Earlier version inFOCS’18. arXiv:1808.03821. 66

    2020 arXiv

  84. [92]

    Time-efficient constant-space-overhead fault-tolerant quantum computation

    Yamasaki, H. and Koashi, M. “Time-efficient constant-space-overhead fault-tolerant quantum computation.” Nat. Phys.20 (2024), 247–253. arXiv:2207.08826

    2024 arXiv

  85. [93]

    Quantum fault tolerance with constant-space and logarithmic-time overheads

    Nguyen, Q. T. and Pattison, C. A. “Quantum fault tolerance with constant-space and logarithmic-time overheads.” arXiv:2411.03632 (2024)

    2024 arXiv

  86. [94]

    Efficientsimulationofrandomquantumstatesandoperators

    Dankert,C.“Efficientsimulationofrandomquantumstatesandoperators.” arXiv: quant-ph/0512217(2005)

    2005 arXiv

  87. [95]

    Efficient estimation of Pauli channels

    Flammia, S. T. and Wallman, J. J. “Efficient estimation of Pauli channels.”ACM Trans. Quantum Comput. 1 (2020). arXiv:1907.12976

    2020 arXiv

  88. [96]

    Noise tailoring for scalable quantum computation via randomized compil- ing

    Wallman, J. J. and Emerson, J. “Noise tailoring for scalable quantum computation via randomized compil- ing.” Phys. Rev. A94 (2016), 052325. arXiv:1512.01098

    2016 arXiv

  89. [97]

    Analysis and suppression of errors in quantum random access memory errors under extended noise models

    Mehta, R., Lee, G., and Jiang, L. “Analysis and suppression of errors in quantum random access memory errors under extended noise models.” arXiv:2412.10318 (2024)

    2024 arXiv

  90. [98]

    Tensor networks and graphical calculus for open quantum systems

    Wood, C. J., Biamonte, J. D., and Cory, D. G. “Tensor networks and graphical calculus for open quantum systems.” Quantum Inf. Comput.15 (2015), 759–811. arXiv:1111.6950

    2015 arXiv

  91. [99]

    Quantummeasurementsandtheabelianstabilizerproblem

    Kitaev,A.Y.“Quantummeasurementsandtheabelianstabilizerproblem.” arXiv: quant-ph/9511026(1995)

    1995 arXiv

  92. [100]

    Notes on super-operator norms induced by Schatten norms

    Watrous, J. “Notes on super-operator norms induced by Schatten norms.”Quantum Inf. Comput.5 (2005), 58–68. arXiv:quant-ph/0411077

    2005 arXiv

  93. [101]

    A quantum speed-up for approximating the top eigenvectors of a matrix

    Chen, Y., Gilyén, A., and de Wolf, R. “A quantum speed-up for approximating the top eigenvectors of a matrix.” In: SODA (2025), 994–1036. arXiv:2405.14765

    2025 arXiv

  94. [102]

    Tight bounds for quantum phase estimation and related problems

    Mande, N. S. and de Wolf, R. “Tight bounds for quantum phase estimation and related problems.” In:ESA (2023), 81:1–81:16. arXiv:2305.04908

    2023 arXiv

  95. [103]

    Efficient Bayesian phase estimation

    Wiebe, N. and Granade, C. “Efficient Bayesian phase estimation.” Phys. Rev. Lett.117 (2016), 010503. arXiv:1508.00869

    2016 arXiv

  96. [104]

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

    Gilyén, A., Su, Y., Low, G. H., and Wiebe, N. “Quantum singular value transformation and beyond: Exponential improvements for quantum matrix arithmetics.” In: STOC (2019), 193–204. Full version in arXiv:1806.01838

    2019 arXiv

  97. [105]

    Ground-state preparation and energy estimation on early fault-tolerant quantum computers via quantum eigenvalue transformation of unitary matrices

    Dong, Y., Lin, L., and Tong, Y. “Ground-state preparation and energy estimation on early fault-tolerant quantum computers via quantum eigenvalue transformation of unitary matrices.”PRX Quantum3 (2022), 040305. arXiv:2204.05955

    2022 arXiv

  98. [106]

    On quantum computation theory

    van Dam, W. “On quantum computation theory.” PhD thesis: Universiteit van Amsterdam (2002)

    2002

  99. [107]

    AnO(n log n) sorting network

    Ajtai, M., Komlós, J., and Szemerédi, E. “AnO(n log n) sorting network.” In:STOC (1983), 1–9

    1983

  100. [108]

    Efficient distributed quantum computing

    Beals, R., Brierley, S., Gray, O., Harrow, A. W., Kutin, S., Linden, N., Shepherd, D., and Stather, M. “Efficient distributed quantum computing.”Proc. R. Soc. A469 (2013), 20120686. arXiv:1207.2307

    2013 arXiv

  101. [109]

    Quantum re- sources required to block-encode a matrix of classical data

    Clader, B. D., Dalzell, A. M., Stamatopoulos, N., Salton, G., Berta, M., and Zeng, W. J. “Quantum re- sources required to block-encode a matrix of classical data.”IEEE Trans. Quantum Eng.3 (2022), 1–23. arXiv:2206.03505

    2022 arXiv

  102. [110]

    Lecture notes on quantum algorithms for scientific computation

    Lin, L. “Lecture notes on quantum algorithms for scientific computation.” arXiv:2201.08309 (2022)

    2022 arXiv

  103. [111]

    A quantum-inspired classical algorithm for recommendation systems

    Tang, E. “A quantum-inspired classical algorithm for recommendation systems.” In:STOC (2019), 217–228. arXiv:1807.04271

    2019 arXiv

  104. [112]

    Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions

    Tang, E. “Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions.” Phys. Rev. Lett.127 (2021), 060503. arXiv:1811.00414

    2021 arXiv

  105. [113]

    Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning

    Chia, N.-H., Gilyén, A. P., Li, T., Lin, H.-H., Tang, E., and Wang, C. “Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning.”J. ACM69 (2022), 1–72. Earlier version inSTOC’20. arXiv:1910.06151

    2022 arXiv

  106. [114]

    Faster quantum-inspired algorithms for solving linear systems

    Shao, C. and Montanaro, A. “Faster quantum-inspired algorithms for solving linear systems.”ACM Trans. Quantum Comput.3 (2022). arXiv:2103.10309

    2022 arXiv

  107. [115]

    Dequantizing algorithms to understand quantum advantage in machine learning

    Tang, E. “Dequantizing algorithms to understand quantum advantage in machine learning.”Nat. Rev. Phys. 4 (2022), 692–693

    2022

  108. [116]

    Quantum machine learning without any quantum

    Tang, E. “Quantum machine learning without any quantum.” PhD thesis: University of Washington (2023)

    2023

  109. [117]

    Learning with optimized random features: Exponential speedup by quantum machine learning without sparsity and low-rank assumptions

    Yamasaki, H., Subramanian, S., Sonoda, S., and Koashi, M. “Learning with optimized random features: Exponential speedup by quantum machine learning without sparsity and low-rank assumptions.” In:NeurIPS (2020), 13674–13687. arXiv:2004.10756

    2020 arXiv

  110. [118]

    Methods of conjugate gradients for solving linear systems

    Hestenes, M. R. and Stiefel, E. “Methods of conjugate gradients for solving linear systems.”J. Res. Natl. Bur. Stand.49 (1952), 409–435

    1952

  111. [119]

    Iterative solution of large sparse systems of equations

    Hackbusch, W. Iterative solution of large sparse systems of equations. Springer (2016)

    2016

  112. [120]

    On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number

    Orsucci, D. and Dunjko, V. “On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number.”Quantum 5 (2021), 573. arXiv:2101.11868. 67

    2021 arXiv

  113. [121]

    Windowed quantum arithmetic

    Gidney, C. “Windowed quantum arithmetic.” arXiv:1905.07682 (2019)

    2019 arXiv

  114. [122]

    How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits

    Gidney, C. and Ekerå, M. “How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits.” Quantum 5 (2021), 433. arXiv:1905.09749

    2021 arXiv

  115. [123]

    Improved quantum circuits for elliptic curve discrete logarithms

    Häner, T., Jaques, S., Naehrig, M., Roetteler, M., and Soeken, M. “Improved quantum circuits for elliptic curve discrete logarithms.” In:PQCrypto (2020), 425–444. arXiv:2001.09580

    2020 arXiv

  116. [124]

    How to compute a 256-bit elliptic curve private key with only 50 million Toffoli gates

    Litinski, D. “How to compute a 256-bit elliptic curve private key with only 50 million Toffoli gates.” arXiv:2306.08585 (2023)

    2023 arXiv

  117. [125]

    Qubitization of arbitrary basis quan- tum chemistry leveraging sparsity and low rank factorization

    Berry, D. W., Gidney, C., Motta, M., McClean, J. R., and Babbush, R. “Qubitization of arbitrary basis quan- tum chemistry leveraging sparsity and low rank factorization.”Quantum 3 (2019), 208. arXiv:1902.02134

    2019 arXiv

  118. [126]

    Quantum computing enhanced computational catalysis

    von Burg, V., Low, G. H., Häner, T., Steiger, D. S., Reiher, M., Roetteler, M., and Troyer, M. “Quantum computing enhanced computational catalysis.”Phys. Rev. Res.3 (2021), 033055. arXiv:2007.14460

    2021 arXiv

  119. [127]

    Even more efficient quantum computations of chemistry through tensor hypercontraction

    Lee, J., Berry, D. W., Gidney, C., Huggins, W. J., McClean, J. R., Wiebe, N., and Babbush, R. “Even more efficient quantum computations of chemistry through tensor hypercontraction.”PRX Quantum 2 (2021), 030305. arXiv:2011.03494

    2021 arXiv

  120. [128]

    Fault-tolerant resource estimate for quantum chemical simulations: Case study on Li-ion battery electrolyte molecules

    Kim, I. H., Liu, Y.-H., Pallister, S., Pol, W., Roberts, S., and Lee, E. “Fault-tolerant resource estimate for quantum chemical simulations: Case study on Li-ion battery electrolyte molecules.”Phys. Rev. Res.4 (2022), 023019. arXiv:2104.10653

    2022 arXiv

  121. [129]

    Introduction to Haar measure tools in quantum information: A beginner’s tutorial

    Mele, A. A. “Introduction to Haar measure tools in quantum information: A beginner’s tutorial.”Quantum 8 (2024), 1340. arXiv:2307.08956

    2024 arXiv

  122. [130]

    The information-disturbance tradeoff and the continuity of Stinespring’s representation

    Kretschmann, D., Schlingemann, D., and Werner, R. F. “The information-disturbance tradeoff and the continuity of Stinespring’s representation.” IEEE Trans. Inf. Theory 54 (2008), 1708–1717. arXiv:quant-ph/0605009. 68

    2008 arXiv

Pith tools

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