Approximation by Quantum Circuits

E. Knill

REVIEW

Approximation by Quantum Circuits

E. Knill

Quantum Physics · Submitted 8 Aug 1995

Pith's verdict: The counting argument is right and the approximation lower bound is the real result; the abstract's closing sentence about 'almost all problems' is broader than what the theorems actually prove.

T0 · AI review

How this review was made: An AI referee (selfhosted/deepseek-v4.1-flash) read the paper on November 11, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

T0 AI review An AI read the paper and answered a fixed list of questions.
T1 Audit Automatic checks that the references and files the paper relies on exist and match.
T2 Compute The paper's code or calculations re-run with the same results.
T3 Formal statement The claims written out in a formal math language a computer can read.
T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 3 major objections · 5 minor · Ask about this paper · The compiled record · Read the full review →

Challenge this review Comment (0) Read on arXiv ↗

Cite ▾

arXiv IDquant-ph/9508006 (version 1)

Pith ID7JW3VF2H, Pith's permanent record of this paper and its review

CitationE. Knill. "Approximation by Quantum Circuits." arXiv:quant-ph/9508006 (1995). https://pith.science/paper/7JW3VF2H

Cite this reviewBibTeX for Pith's review of this paper

Claim paper

Why Pith says this

Highlight any text to comment on it.

Editor's note

read the letter

The thing to take away: Knill's counting argument against polynomial approximability by g-qubit gates is correct, and it settles the question Deutsch, Barenco and Ekert raised. The reachable set of a b-gate circuit sits in a manifold of dimension roughly 9b + 3n + 1 inside a 4^n-dimensional unitary group, and the epsilon-ball volume estimate in Lemma 4.3 closes the argument. Corollary 4.2 follows cleanly: if b log b = o(k 2^n), the approximable set has measure zero. That is the paper, and it holds up. The companion density-matrix bound (Theorem 4.5) uses the same template, and the authors are upfront that it is not tight — they say so themselves right after Corollary 4.6. The improvement of the exact-synthesis upper bound to O(n 4^n) in Theorem 3.3 is a genuine, if smaller, contribution, and the construction is spelled out rather than gestured at. The measure lemmas are proved in the appendix with explicit Stirling bounds, so the volume estimates are checkable rather than asserted. Two soft spots, neither load-bearing. First, the abstract's last sentence — 'almost all problems are hard to solve with quantum circuits' — is doing more work than the theorems license. The theorems are about the uniform measure on U_n and on truth tables; the paper never argues that uniform is the right notion of 'typical,' and its own citation of Shor shows structured problems can be easy. The body is more careful than the abstract; this is a wording problem, not a math problem, but it is the sentence people will quote. Second, the exact-representation lower bound in Theorem 3.4 leans on Lemmas 3.5–3.7, which assert effective dimension contributions of 12 and 9 per gate via a local coordinate decomposition that is sketched, not counted out. The paper is explicit that this formalizes Barenco et al. rather than originating it, so the burden is lighter than it looks. Who should read it: anyone working on quantum circuit complexity or unitary synthesis, and anyone who wants the counting framework in its original form. Worth a serious referee — the central argument is sound and the fixes are editorial.

Referee report

Major objections (3)

[Abstract (abstract:s5)] The abstract's final sentence, 'The overall conclusion is that almost all problems are hard to solve with quantum circuits' (abstract:s5), is broader than what the theorems establish. Theorem 4.1 and Corollary 4.2 are statements about the uniform measure μ_k on k orthonormal states (Section 2, 'Measures for U_n'), and Theorems 5.1 and 5.3 are statements about uniformly random decision problems and functions. The paper does not defend the uniform measure as the right notion of a 'typical problem,' and the abstract does not qualify 'almost all.' The body is more careful (Section 5 counts problems over a domain D), but the abstract's summary is the paper's headline claim. I recommend qualifying the abstract to say 'almost all unitaries' or 'almost all problems under the uniform measure,' and adding a sentence in Section 5 or the conclusion explaining why the uniform measure is the relevant notion of typicality.
[§3, Lemmas 3.6 and 3.7] The dimension-counting argument in Lemmas 3.6 and 3.7 is load-bearing for Theorem 3.4's lower bound, but the proof is sketched. The claim that a gate with one input from another gate contributes at most 12 dimensions (Lemma 3.6) and a gate with both inputs from other gates at most 9 dimensions (Lemma 3.7) relies on a local parametrization of U(4) (the citation to Warner, p. 120) and on 'moving the W's to the previous gate.' The latter step needs to be made rigorous: the decomposition must be shown to be consistent across the whole circuit, and the finite union of local restrictions must be shown to cover the range of f_S without increasing its dimension. As written, the argument is a sketch rather than a proof. I recommend expanding the proof of Lemmas 3.6 and 3.7, or explicitly stating that Theorem 3.4 is a formalization modulo this local argument.
[§5, proof of Theorem 5.1] In the proof of Theorem 5.1, the step 'if ε < 1/q, then W either does not decide any decision problem with domain D with advantage q or it decides f with advantage q' is not correct as stated. The bound v_l(W|b>, V|b>) ≤ 4ε means that if V decides f with advantage q and W is within 4ε of V in total variation, then W decides f with advantage q' satisfying 1/q' = 1/q - 8ε; the advantage is degraded, not preserved. With the covering radius ε = 1/(bq) used in the proof, the advantage is not preserved. The asymptotic conclusion of Theorem 5.1 survives if the covering radius is reduced by a constant factor (e.g., ε = 1/(10 b q)), but the stated constants and the logical step need correction. I recommend fixing the constant and stating the degraded-advantage step explicitly.

Minor objections (5)

[§3, proof of Theorem 3.4] The dimension count 'All gates contribute 9 dimensions for a total of 9b dimensions. At most n inputs do not come from a previous gate. Those n inputs effectively contribute 3n + 1 dimensions' is not fully explained. Since the input states are fixed standard basis vectors, it is not obvious why they contribute 3n + 1 free dimensions to the range of f_S. The paper should explain how the 3n + 1 term arises and why it does not double-count with the 9b term.
[§3, Theorem 3.3] The O(n) construction of the controlled gates Λ_{n-1}(V_b) is cited to Barenco et al. [1], which is listed as 'Submitted to Physical Review A' and is therefore unpublished. The paper should either reproduce the construction or note that it is standard and give a published reference.
[§4, Theorem 4.1] The factor 2^{4g} in the exponent of Theorem 4.1 is not explained. It comes from the 2·4^g real parameters of U(2^g), and a parenthetical remark would help the reader.
[§2, Lemma 2.5] The proof of Lemma 2.5 in the appendix uses an orthant decomposition and a projection argument that is terse. A sentence explaining why the intersection of the ε-ball with the simplex decomposes into the stated orthant pieces would improve readability.
[§4, Corollary 4.6] The authors acknowledge that Corollary 4.6 is not tight (the minimum average total variation distance is 2/e > 1/2) and suggest improving Lemma 2.5. This is an honest limitation, and I encourage the authors to state the gap explicitly in the corollary so that readers do not mistake the bound for a tight characterization.

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

Knill proves that for any fixed g, all but a vanishing fraction of n-qubit unitary operations need exponentially many g-qubit gates to approximate to fixed accuracy, refuting the suggestion that polynomial-size circuits could approximate an

The reading

Deutsch, Barenco and Ekert had suggested that a fixed two-qubit gate might approximate an arbitrary unitary operation on n qubits using only polynomially many gates. Knill argues the opposite and backs it with counting: the set of unitaries reachable by b gates is a finite union of smooth images whose dimension and volume can be bounded, so once b is sub-exponential in n it covers a vanishing fraction of all unitaries. The paper also revisits exact representation, lowering the known upper bound on the number of two-qubit gates needed to build any n-qubit unitary from $O(n^3 4^n)$ to $O(n 4^n)$ and formalizing the matching lower-bound argument. It then counts decision problems and functions that b-gate circuits can solve or guess with an advantage, and finds those sets exponentially small as well. The point for a reader is a ceiling on what short quantum circuits can be asked to do uniformly: most operations, and most problems, are simply not reachable.

What carries the argument

Two counting devices carry the argument. The first is volumetric: replace each g-qubit gate by a finite net of size roughly $(2/delta)^{2^{4g}}$ (Lemma 4.4), so the number of distinct circuits becomes finite and the approximable set becomes a union of eps-balls around exactly representable operators. The ball volume in the weak two-norm is bounded in Lemma 4.3 using the sphere-cap estimate of Lemma 2.4, giving roughly $(1-eps^2/2)^{-k}(eps sqrt{1-eps^2/4})^{k 2^n}$; multiplying by the circuit count and taking logs produces the theorem. The second device is dimension counting for exact representation: Lemmas 3.5 to 3.7 show each two-qubit gate adds at most 9 real dimensions to the reachable manifold (15 for the first gate, 12 when one input comes from another gate), plus $3n+1$ dimensions for the input wires and global phase, so a b-gate circuit sweeps a manifold of dimension at most $9b+3n+1$ inside a target manifold of dimension $k(2^{n+1}-k)$.

Extended reading notes

Core claim

The central claim is a lower bound on approximation. For fixed g and accuracy $0<eps<sqrt{2}$, the measure of n-qubit unitaries that some circuit of b g-qubit gates can approximate to within eps in the weak two-norm on k basis vectors is bounded by an explicit expression that goes to zero whenever $b log b = o(k 2^n)$. Since $sqrt{2}$ is roughly the distance from a random state to a fixed state, the bound says short circuits do no better than a random unitary at carrying $|0>$ to a typical target state. A companion theorem replaces the state metric with total variation distance on the measurement statistics of l bits, giving $b log b = o(k 2^l)$ as the threshold; the author states plainly that this second bound is not tight in the same way the first is. Section 3 supplies the exact-representation counterpart: preparing an arbitrary n-qubit state takes $O(n 2^n)$ two-qubit gates, which through the paper's decomposition theorem yields $O(n 4^n)$ for a full unitary, a factor of $n^2$ better than the earlier $O(n^3 4^n)$, while a dimension count gives the lower bound $b(2,n,k) >= (k/9)(2^{n+1}-k) - n/3 - 1/9$.

Load-bearing premise

The step from 'the approximable set has measure zero' to 'almost all problems are hard' treats the uniform measure on n-qubit unitaries as the right notion of a typical problem, so the theorems constrain random unitaries and say nothing by themselves about a specific structured operation or a decision problem with a short description.

Editorial extensions

If this is right

No polynomial-size family of two-qubit gates can approximate a Haar-typical n-qubit unitary to fixed accuracy; the required gate count grows like $2^n$ up to logarithmic factors.
Approximate state conversion is exponentially hard for almost all pairs of states, so a quantum analogue of classical relative information distance cannot be computed by short circuits.
The same covering count bounds probabilistic solution of decision problems and guessing of checkable functions: the fraction of problems on a domain D solvable with advantage q by b gates is at most $exp_2((log b + log q + log n) b 2^{4g} + 1 - |D|)$.
Exact synthesis of an arbitrary n-qubit unitary now sits between about $4^n/9$ and $n 4^n$ two-qubit gates, narrowing the known gap to a factor of order n.

Reading between the lines

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

The theorem is a statement about a continuum under a uniform measure, so it cannot by itself separate 'hard because unstructured' from 'hard because the measure is spread thin'; a complexity-class separation would need a bound that survives restriction to unitaries with short classical descriptions.
The threshold $b log b = o(k 2^n)$ is close to the cost of writing down $2^n$ amplitudes, which suggests reading the result as an information-counting statement: a b-gate circuit carries only $O(b log b)$ bits of description and so cannot pin down more amplitudes than that.
The state-conversion corollary implies that two quantum states can be close in a divergence sense yet require exponentially many gates to convert, so any proposed quantum information distance obeying a triangle inequality over circuit cost must fail for generic states.
Nothing here bears on Shor-style algorithms, which exploit one specific structured unitary; the hardness is about generic targets, so the conclusion is a ceiling on the model rather than a claim about its usefulness.

Original abstract

In a recent preprint by Deutsch et al. [1995] the authors suggest the possibility of polynomial approximability of arbitrary unitary operations on $n$ qubits by 2-qubit unitary operations. We address that comment by proving strong lower bounds on the approximation capabilities of g-qubit unitary operations for fixed g. We consider approximation of unitary operations on subspaces as well as approximation of states and of density matrices by quantum circuits in several natural metrics. The ability of quantum circuits to probabilistically solve decision problem and guess checkable functions is discussed. We also address exact unitary representation by reducing the upper bound by a factor of n^2 and by formalizing the argument given by Barenco et al. [1995] for the lower bound. The overall conclusion is that almost all problems are hard to solve with quantum circuits.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-23: 1 request, 4,923 input tokens.

What the abstract itself states, as probabilities: claims first 0.04 · states limitation 0.31 · human participants 0.01 · controlled comparison 0.05 · randomized assignment 0.01 · states quantitative result 0.69 · compares with prior results 0.91 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v1. Results and the main claim are underlined; show every role.

In a recent preprint by Deutsch et al. [1995] the authors suggest the possibility of polynomial approximability of arbitrary unitary operations on $n$ qubits by 2-qubit unitary operations. We address that comment by proving strong lower bounds on the approximation capabilities of g-qubit unitary operations for fixed g. We consider approximation of unitary operations on subspaces as well as approximation of states and of density matrices by quantum circuits in several natural metrics. The ability of quantum circuits to probabilistically solve decision problem and guess checkable functions is discussed. We also address exact unitary representation by reducing the upper bound by a factor of n^2 and by formalizing the argument given by Barenco et al. [1995] for the lower bound. The overall conclusion is that almost all problems are hard to solve with quantum circuits.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	In a recent preprint by Deutsch et al. [1995] the authors suggest the possibility of polynomial approximability of arbitrary unitary operations on $n$ qubits by 2-qubit unitary operations.	background 1.00	0.03	0.02	hedged possibility 1.00
s1	We address that comment by proving strong lower bounds on the approximation capabilities of g-qubit unitary operations for fixed g.	contribution 0.93	0.92	0.07	asserted 1.00
s2	We consider approximation of unitary operations on subspaces as well as approximation of states and of density matrices by quantum circuits in several natural metrics.	contribution 0.94	0.76	0.03	asserted 0.63
s3	The ability of quantum circuits to probabilistically solve decision problem and guess checkable functions is discussed.	contribution 0.99	0.47	0.02	unclear 0.60
s4	We also address exact unitary representation by reducing the upper bound by a factor of n^2 and by formalizing the argument given by Barenco et al. [1995] for the lower bound.	contribution 0.51	0.87	0.04	asserted 1.00
s5	The overall conclusion is that almost all problems are hard to solve with quantum circuits.	interpretation 0.87	0.72	0.95	asserted 0.99

What kind of paper the classifier reports this is: theoretical result 0.99 · evidence from proof or derivation 1.00.

What was examined, and what was not

sources read

arXiv listing abstract v1

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

References

Forward citations

Cited by 29 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. OpenAlex reports about 147 citations worldwide. Full citation record

Measurement-Induced Phase Transitions in the Dynamics of Entanglement
cond-mat.stat-mech 2018-08 accept novelty 8.0 of 10

Repeated projective measurements drive a continuous transition in a quantum circuit's entanglement, from volume-law to area-law, with a numerically determined correlation-length exponent of about 2.03 in one spatial d...
Local random quantum circuits are approximate polynomial-designs
quant-ph 2012-08 conditional novelty 8.0 of 10

Random nearest-neighbor quantum circuits of polynomial length form approximate unitary t-designs for all t up to poly(n), settling a long-open conjecture.
Quantum Computation of Scattering in Scalar Quantum Field Theories
hep-th 2011-12 accept novelty 8.0 of 10

A quantum algorithm computes scattering amplitudes in massive phi-fourth theory in four or fewer spacetime dimensions in time polynomial in particle number, energy, and precision, at both weak and strong coupling.
Black-box Hamiltonian simulation and unitary implementation
quant-ph 2009-10 accept novelty 8.0 of 10

A quantum-walk method simulates sparse Hamiltonians with query cost linear in sparsity and time, and implements an arbitrary N-by-N black-box unitary in about N to the two-thirds power queries.
Multivariate quantum state preparation with optimized tensor networks
quant-ph 2026-09 accept novelty 7.0 of 10

SCENT uses spectral clustering on pairwise entanglement metrics to discover optimal tree tensor network structures, enabling high-fidelity quantum state preparation of multivariate functions with greatly reduced circu...

Show 24 more citing papers

Practical Tests and Witnesses of Fermionic non-Gaussianity
quant-ph 2026-05 unverdicted novelty 7.0 of 10

Introduces practical witnesses of fermionic non-Gaussianity via antiflatness from covariance matrices, with two efficient measurement protocols, a purity-corrected version for mixed states, and experimental results on...
Three Hamiltonians are Sufficient for Unitary $k$-Design in Temporal Ensemble
quant-ph 2026-04 accept novelty 7.0 of 10

A three-step quench protocol with fixed Hamiltonians and random times forms unitary k-designs for arbitrary k; the two-step protocol cannot.
Realizing Unitary $k$-designs with a Single Quench
quant-ph 2025-11 conditional novelty 7.0 of 10

A single quench between two independent random Hamiltonians at the Thouless time generates unitary k-designs.
Trading T gates for dirty qubits in state preparation and unitary synthesis
quant-ph 2018-12 accept novelty 7.0 of 10

A data-lookup circuit called SelectSwap trades a tunable number of dirty qubits for T gates, cutting the T-count for arbitrary state preparation to O(sqrt(N)) in the best case, with a matching lower bound.
Circuit-centric quantum classifiers
quant-ph 2018-04 conditional novelty 7.0 of 10

A parametrized quantum circuit with only O(log N) trainable gate angles classifies N-dimensional data at accuracy comparable to classical neural networks, with analytic gradients estimated from repeated circuit runs.
Quantum algorithm for simulating real time evolution of lattice Hamiltonians
quant-ph 2018-01 accept novelty 7.0 of 10

Time evolution of a geometrically local lattice Hamiltonian can be simulated with O(nT polylog(nT/epsilon)) gates and depth O(T polylog(nT/epsilon)), and this is optimal up to logarithmic factors.
Chaos and complexity by design
quant-ph 2016-10 conditional novelty 7.0 of 10

The ensemble average of the squared 2k-point out-of-time-order correlator equals the kth frame potential, tying quantum chaos to unitary k-designs and yielding a counting lower bound on circuit complexity.
Computational Complexity and Black Hole Horizons
hep-th 2014-02 conditional novelty 7.0 of 10

The distance from a black hole horizon is proposed to be dual to the computational complexity of the black hole state, which makes creating firewalls an extremely hard, often exponentially hard, task.
A geometric approach to quantum circuit lower bounds
quant-ph 2005-02 conditional novelty 7.0 of 10

Minimal geodesic length in a right-invariant Finsler metric on SU(2^n) lower-bounds exact quantum circuit size, and for diagonal unitaries the minimal Pauli geodesic reduces to a closest-vector-in-a-lattice problem.
Efficient High-Dimensional Quantum Circuit Synthesis: From Multi-Controlled Gates to Isometries and Quantum Channels
quant-ph 2026-07 accept novelty 6.5 of 10

Multi-controlled single-qudit gates can be synthesized with O(n²) CINC gates (O(n) for special unitaries), enabling improved qudit isometry and channel circuits and, for prime d, equivalent SUM-gate circuits.
Einstein Metrics and Quantum Control on Symmetric Tensor Product Quotients
quant-ph 2026-10 accept novelty 6.0 of 10

For all sufficiently large n the quotient space M_n carries exactly two invariant Einstein metrics up to scaling, both with diameter approaching pi/sqrt(3), while typical two-qubit circuit size remains exponential.
State Preparation Protocols for Entangled States via Open Quantum Walks
quant-ph 2026-08 conditional novelty 6.0 of 10

Open quantum walks on a ring and on two nodes prepare ensembles of Dicke and GHZ states, with a closed-form spectral gap for the Dicke walk.
A Compass on the Quantum State Sphere: The Hopf Ansatz for Arbitrary Pure-State Optimization
quant-ph 2026-07 conditional novelty 6.0 of 10

The Hopf binary-tree ansatz provides universal state preparation plus an explicit inverse map, diagonal metric, and exact tangent-state gradients, organizing gradient access into O(log N) circuit families.
Cartan-Khaneja-Glaser decomposition of $SU(2^n)$ via involutive automorphisms
quant-ph 2025-09 conditional novelty 6.0 of 10

Reformulation of Cartan-Khaneja-Glaser decomposition for SU(2^n) via involutive automorphisms and symmetric Lie algebra decompositions yields a stable recursive factorization with open-source Python code validated on ...
Quantum AIXI: Universal Intelligence via Quantum Information
quant-ph 2025-05 conditional novelty 6.0 of 10

The paper introduces Quantum AIXI, a channel-based formulation of universal intelligence over quantum environments, and argues that contextuality, measurement back-action, and no-cloning fundamentally limit any such agent.
Scalable Quantum Simulations of Scattering in Scalar Field Theory on 120 Qubits
quant-ph 2024-11 conditional novelty 6.0 of 10

Variational circuits on 120 superconducting qubits reproduce the qualitative dynamics of wavepacket scattering in 1+1D scalar field theory, with a new vacuum-evolution error mitigation scheme.
Quantum Monte Carlo algorithm for option pricing and its complexity analysis
quant-ph 2023-01 unverdicted novelty 6.0 of 10

A quantum Monte Carlo algorithm solves multidimensional Black-Scholes PDEs for option pricing with polynomial complexity in dimension d and accuracy 1/ε, with rigorous error bounds and a claimed speedup over classical...
Complexity and Shock Wave Geometries
hep-th 2014-06 conditional novelty 6.0 of 10

The complexity of a two-sided black hole state is proportional to the maximal spatial volume of its Einstein-Rosen bridge, and this volume reproduces the scrambling-time delays expected from a quantum circuit model in...
Parallelism for Quantum Computation with Qudits
quant-ph 2006-03 conditional novelty 6.0 of 10

Parallel scheduling of Givens rotations on a qudit achieves logical depth equal to the height of a binary computation tree, and nonlocal two-qudit gates can be parallelized to O(d^2) steps using O(d^3) entangled qubit pairs.
Experimental Observation of Error-Resilience Phase Transition on Superconducting Quantum Processor
quant-ph 2026-10 conditional novelty 5.0 of 10

A 26-qubit superconducting experiment reports finite-size signatures of the predicted error-resilience phase transition at a critical coherent-noise angle near 1.01 radians, below the ideal Haar-random prediction of 1.14.
Approximate Quantum Circuit Synthesis for Diagonal Unitary
quant-ph 2024-12 conditional novelty 4.0 of 10

A heuristic phase-gadget ordering algorithm approximates diagonal unitaries with fewer CNOT gates, claiming a utility ratio of 3.2 between CNOT savings and fidelity loss.
Introduction to UniversalQCompiler
quant-ph 2019-04 conditional novelty 4.0 of 10

An open-source Mathematica package compiles arbitrary quantum operations into single-qubit rotations and CNOT gates, implementing published near-optimal decomposition schemes with LaTeX and OpenQASM export.
Standard Model Physics and the Digital Quantum Revolution: Thoughts about the Interface
quant-ph 2021-07 conditional novelty 3.0 of 10

The authors argue that entanglement works as both a diagnostic and an organizing tool linking quantum many-body and field theory to near-term quantum simulation of Standard Model physics.
Statistical and Algorithmic Foundations of Probing Quantum Systems with Compressive Measurements: A Review
quant-ph 2026-05 unverdicted novelty 2.0 of 10

A survey of structured quantum state tomography covering compact representations, measurement design, and optimization algorithms, connected to compressive sensing for sample efficiency.

How later papers used it

70 later papers cite it

Evidence: substantial. 70 of the citing papers share no author with it, and 9 of those carry a confident label from Pith's citation classifier.

Pith read 26 of the 99 citing sentences, choosing only those whose citation markers point at this paper alone, and wrote the paraphrases from them. The summary, the counts, the evidence level, the links and the quotes come from code; the summary counts the papers listed below. A later paper is listed under a label when Pith's citation classifier gives one of its sentences that label at probability 0.8 or more (0.95 for support), Pith's reading finds that the citing paper itself did it, and a second check confirms the paraphrase against the sentence. This section lists uses only. It does not list criticism or disagreement, so their absence here says nothing about how the paper has been received. Papers that share an author with this one are listed apart, under "By the same authors". A quote is the citing authors' own sentence, shown when their paper's licence is CC BY, CC BY-SA or CC0. JSON

2 later papers by other authors are listed below: 2 used its method or tool.

Uses its method or tool 2 of 4 papers with this label

Combined this paper's decomposition scheme for isometries with a state preparation scheme.

Quantum Circuits for Isometries (2015) · 0.84 · paraphrased: the licence does not allow quoting
Based its argument on an adaption of a technique of this paper.

On the complexity of implementing Trotter steps (2022) · 0.95 · paraphrased: the licence does not allow quoting

How the literature uses it

67 arXiv papers cite this in 96 sentences

Each citing sentence is taken from the citing paper's LaTeX source and typed by Pith's classifier. A label appears at probability 0.8 or more (0.95 for support), a contest at 0.7 or more; the quoted words are the citing authors'. How each label was checked · JSON

Papers citing it · 69 sentences without a confident label

Uses its method or tool 4 papers

In this section we combine the decomposition scheme for isometries of Knill [ref] and the state preparation scheme described in [ref] .

Quantum Circuits for Isometries · Decomposition of isometries using the decomposition scheme of Knill · 0.84
Using the dense state preparation scheme from [ref] one can merge some gates as described in [ref] for Knill's decomposition [ref] .

Quantum Circuits for Sparse Isometries · Dense isometries · 0.90
Our argument is based on an adaption of a technique of Knill [ref] .

On the complexity of implementing Trotter steps · Circuit lower bound · 0.95

Compares with it 3 papers

By contrast, using the decompositions of [ref] , which also work one column at a time, the operations performed to replace the first column typically remove all of the sparseness elsewhere.

Quantum Circuits for Sparse Isometries · Introduction · 0.97
Without allowing ancillae, only weaker $Õ(2^n)$ upper bounds are known; see, for example, [ref] .

Quadratic Lower bounds on the Approximate Stabilizer Rank: A Probabilistic Approach · Trading $T$ gates for Clifford operations · 0.83
In contrast to previous algorithms for quantum state preparation [ref] , which require $Θ(N)$ depth or width, our proposed solution may take as low as $(logN)$ depth for some instances, and always $(logN)$ qubits.

Quantum Signal Processing, Phase Extraction, and Proportional Sampling · Introduction · 1.00

Cites it as support 2 papers

Even in the quantum setting, implementing Haar random unitaries requires exponential resources as shown in some counting arguments [ref] .

Random Projection using Random Quantum Circuits · Introduction · 0.96
The vast majority of states cannot even be approximated by an efficient quantum algorithm [ref] .

The Quantum Frontier · Exponential size of quantum state space? · 0.97

Cites it as background 16 papers

The decomposition of arbitrary isometries has been considered in [ref] .

Quantum Circuits for Sparse Isometries · Introduction · 0.93
Prescriptive (matrix decomposition-based) numerical methods for the general isometry synthesis problem are known [ref] and are also available in public software packages [ref] .

Numerical circuit synthesis and compilation for multi-state preparation · Introduction · 0.80
It is well known that any unitary operator can be decomposed into, or in other words synthesized from, a sequence of single- and two-qubit gates, provided that the elementary gate set is universal [ref] .

Numerical analysis of quantum circuits for state preparation and unitary operator synthesis · Introduction · 0.95

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.