Fault Tolerant Quantum Computation with Constant Error

Computer Science; Dorit Aharonov (Physics; Hebrew Univ.); Michael Ben-Or (Computer science

REVIEW

Fault Tolerant Quantum Computation with Constant Error

Dorit Aharonov (Physics, Computer Science, Hebrew Univ.), Michael Ben-Or (Computer science

Quantum Physics · Submitted 14 Nov 1996 · 25 references

Pith's verdict: The paper that turned the threshold theorem into a real target — concatenation plus 'proper codes' — and the core argument holds, though the appendix proof is a sketch and one linchpin is asserted more than shown.

T0 · AI review

How this review was made: An AI referee (selfhosted/deepseek-v4.1-flash) read the paper on November 13, 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 →

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

Challenge this review Comment (0) Read on arXiv ↗

Cite ▾

arXiv IDquant-ph/9611025 (version 2)

CitationComputer Science, Dorit Aharonov (Physics, Hebrew Univ.), Michael Ben-Or (Computer science. "Fault Tolerant Quantum Computation with Constant Error." arXiv:quant-ph/9611025 (1996). https://pith.science/paper/quant-ph/9611025

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

This is the 1996 preprint that, alongside Kitaev and Knill-Laflamme-Zurek, made constant-noise fault tolerance believable. The genuinely new machinery is the concatenation argument plus the 'proper code' definition (Definition 4): gate, init, read, and correction procedures must stay inside the protected gate set, and correction must map any state to a codeword. That second condition is what lets the multi-level induction close, and it is the right abstraction. The two explicit families — linear codes over F_p and polynomial codes generalizing Ben-Or-Goldwasser-Wigderson secret sharing — are real constructions, not hand-waving, and the qupit generalization is a clean piece of work. Theorem 2 is the result everyone remembers, and it is correct. Credit where due: the step from Shor's polylog threshold to a constant one is the step that mattered, and the induction skeleton in Appendix C is the skeleton later proofs still use. On the stress-test concern: it lands on the write-up, not on the theorem. Appendix D(2) describes a per-qubit reset triggered when the syndrome weight exceeds d, and a state with d+1 errors whose syndrome mimics a weight-1 error gets 'corrected' into a non-codeword with no reset firing. So claim 3 of Appendix C is asserted rather than demonstrated. But this is a fixable presentation gap — a full-block reset or a cleaner statement of the branch closes it, and the journal version does close it. I would not treat it as a hole in the result. Two other soft spots worth naming. First, the polynomial-code universality leans on Solovay-Yao [21], listed as 'in preparation'; that is a real dependency on an unpublished source, and it is the one place where the paper's own footing is thin. Second, the 10^-6 threshold: the arithmetic is never displayed, and the abstract's 'about 10^-6' becomes 'shown to be larger than' in section 6 — a small overclaim, easily fixed by showing the numbers. The nearest-neighbor claim is a single sentence credited to Cleve; fine as a remark, thin as a result. Who should read it: anyone working on fault tolerance, and anyone who wants to see where the threshold theorem actually came from. It deserves a serious referee — the result is foundational and the gaps are the kind referees exist to catch.

Referee report

Significance

If correct, this is a foundational result: it establishes the threshold theorem for quantum computation and moves fault tolerance from a polylogarithmic to a constant noise requirement, which is the form in which the result is now standard. The scheme is pleasingly general — it is parameterized by abstract code properties (distance d, spread l, procedure size a) rather than by a particular code, so the threshold is derived from code parameters and not fitted to any data, and the prediction (existence of a constant η0) is falsifiable. The two explicit code families, the nearest-neighbor extension, and the measurement-free computation are genuine strengths. The authors are candid that η0 ≈ 10^-6 is far from practical and that the polylogarithmic depth blowup is not reduced to a constant; these acknowledged limitations are appropriately framed as motivation for better codes rather than as defects of the existence proof.

Major objections (4)

[Definition 4(2) and Appendix D(2)] The properness condition — that the correction procedure takes any density matrix, not merely one close to a codeword, to some word in the code — is the linchpin of the multi-level induction, since it is exactly what is invoked at the base case of claim 3 in Appendix C ('Claim 3 is satisfied by the extra restriction on the error correction which a proper code satisfies'). The only verification is Appendix D(2), which is compressed and, as written, does not establish the property. The text says the procedure computes 'whether the number of faults according to the syndrome is larger than d' and then 'replaces the qubit with a qubit from the state |s0> if the number of faults is indeed larger that d.' Two things need to be pinned down. First, for a code correcting d errors the decoder's coset leader has weight at most d whenever the syndrome is that of a correctable error, so the reset branch may never fire; consider a codeword corrupted by d+1 errors whose syndrome coincides with that of a weight-1 Pauli — the decoder applies the weight-1 correction, the reset does not trigger, and the output is a codeword plus a residual error, not a codeword. Second, 'replaces the qubit' (singular) suggests per-qubit replacement, which does not obviously yield a codeword; a full-block reset to |s0> would. Please state explicitly whether the reset is per-qubit or full-block, and prove that the post-correction state is exactly a codeword (or, if only approximately, restate Definition 4(2) and redo the base case of claim 3 accordingly).
[Abstract and §4 (Theorem 2)] The headline number η0 ≈ 10^-6 is stated in the abstract and in §1 but is never derived. Theorem 2's condition is (a/(d/2l+1)) η^{d/2l} < 1, which requires the block size m, the distance d, the spread l, and the maximum procedure size a for a specific code; none of these is given for either family. For the linear code of §5.1 one would need at least d, l, and a (the Toffoli procedure of Appendix D(5) is the natural candidate for a), and for the polynomial code of §5.2 one would need the same with m = 4d+1. Without this arithmetic the reader cannot check the 10^-6, and the number functions as an unverified free parameter. Please add a short worked evaluation for one concrete code, even if only to leading order.
[§5.2, Theorem 4] The universality of the polynomial-code gate set rests on two steps: an explicit infinite-order element, and a density argument for the generated group in SU(n), with the exponential approximation rate attributed to reference [21] (Solovay–Yao), which is listed as 'in preparation.' The density argument is sketched in one sentence and the efficiency of gate approximation — which matters because the threshold depends on the procedure size a — is entirely delegated to an unpublished source. This does not threaten Theorem 2, since Theorem 3 supplies an independent proper code over F_2, but as written the polynomial family's claim to be a proper computation code with controlled procedure size is not supported within the manuscript. Either supply the density/approximation argument or state clearly that the polynomial family's efficiency is conditional on [21].
[§6 and abstract] The claim that the result holds for nearest-neighbor circuits is asserted in the abstract and in §6 with the remark that procedures 'can be made, with constant cost, to operate only on nearest neighbors, by adding gates that swap between qubits,' and that 'the bound on η in this case will be smaller.' No argument or estimate is given. Since the swap network increases both the procedure size a and the number of fault locations per procedure, and the threshold depends on a through Theorem 2, the reader cannot tell whether the nearest-neighbor threshold remains a positive constant or how much it degrades. Please give at least a bound on the swap overhead and a resulting (possibly crude) threshold.

Minor objections (7)

[Appendix A, Lemma 3] The proof reads backwards at one point: it says 'When measuring the qubits in A, in σ1, one gets the same answer on all the qubits in one block, since σ1 reduced to A equals ρ1,' but the definition of k-deviation gives agreement on B−A, not on A. The majority in each block is determined by the qubits outside the sparse set, so the argument should refer to B−A throughout. As written the sentence invites the reader to conclude the opposite of what is needed.
[Theorem 1, Theorem 2, Appendix C] The exponent on η is inconsistent across the paper: Theorem 1 gives an effective noise rate of order η^{d/2l+1}, Theorem 2 states the condition with η^{d/2l}, and the proof of Theorem 2 in Appendix C sets (a/(d/2l+1)) η^{d/2l+1} = η^{1+ε}. The stated theorem is the conservative direction, so this is not an error, but the three exponents should be reconciled in one place.
[Appendix E(4)] In the Fourier-transform procedure the text refers to 'the coefficient of xd in this polynomial' where the surrounding computation uses x^{2d}, and writes 'f2d = ∑ ei f(αi)' where the coefficient of x^{2d} is meant. These should be corrected for readability.
[References [2], [3], [21]] Three load-bearing or motivating references are unpublished: [3] ('in preparation') for the mixed-state circuit model, [2] ('Submitted to STOC 97') for the claim in §1 that initializing all qubits at time 0 forces exponential blowup, and [21] ('in preparation') for the approximation rate. The model in §2 is self-contained enough that [3] is supporting rather than essential, but the §1 impossibility claim and the polynomial-code efficiency claim should either be argued in-text or flagged as conditional.
[§4, d=1 remark] The remark that a similar result holds for d=1 with threshold (b/2) η < 1 is terse and does not explain how the concatenation recursion closes when the per-level improvement is linear rather than η^{1+ε}. A sentence or two of explanation would help.
[Throughout] There are numerous typographical errors that impede reading, among them 'deffinition', 'dimentional', 'recovarable', 'efected', 'fualt', 'pitwise', 'dimention', and misspelled author names in the references ('Saqurai' for Sakurai, 'Deutch' for Deutsch, 'Ga'cs' for Gács, 'Preparata'). A careful copy-edit pass is warranted.
[Abstract and §2.2] The abstract's 'no measurements are used during the quantum computation' is consistent with the reading procedure at the end, but the phrase could be misread; a parenthetical clarifying that measurements occur only at readout would remove the ambiguity.

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

The paper

The paper claims

Constant-rate noise can be made survivable for quantum computation.

The reading

The paper asks whether a quantum circuit can keep computing correctly when every qubit and every gate has a fixed, non-negligible chance of failing at every time step. Shor had shown this only when the fault probability falls logarithmically with the circuit size; Aharonov and Ben-Or argue that a constant threshold is enough. Their route is to encode each logical qubit in a block, alternate computation with error correction, and then concatenate the whole simulation several times so that the effective fault rate shrinks exponentially in the number of levels. If the argument holds, a quantum computer built from noisy components could run long computations at polylogarithmic overhead in time and space, provided its physical error rate is below a code-dependent constant that the paper estimates near $10^{-6}$ for its explicit codes.

What carries the argument

The machinery is concatenated simulation by a proper quantum computation code. A code is proper when its gate, initialization, reading, and correction procedures use only gates from the code’s own universal set, and when the correction procedure takes any density matrix—not only one close to a codeword—to some word in the code. Concatenation replaces each qubit of the simulated circuit by a block, each time step by a working period, and each gate by a fault-tolerant procedure; correction stages are inserted between computation stages. Lemma 2 proves by induction on the number of levels $r$ that an $(r,k)$-sparse fault path with $2kl ≤ d$ leaves the state $(r,d/2)$-deviated from the correct one, and the threshold inequality makes such sparse fault paths overwhelmingly likely for $r = O(log log V(M_0))$. The procedures replace measurements with controlled-NOT gates, so no measurement is used during the quantum computation.

Extended reading notes

Core claim

The central claim is a threshold theorem for noisy quantum circuits: for any circuit $M_0$ of size $s$ and depth $t$, and any noise rate $η$ below a constant $η_0$ determined by the chosen code, there is a simulating circuit $M_r$ of size $O(s · polylog(s))$ and depth $O(t · polylog(t))$ that outputs the correct answer with probability at least $2/3$. The threshold condition is $((a)/(d/2l+1)) η^{d/2l} < 1$, where the code corrects $d$ errors, has spread $l$, and all its procedures fit in rectangles of size at most $a$. The paper also supplies two explicit families of “proper” quantum computation codes—linear codes over $F_p$ for $p=2$, and polynomial quantum codes over $F_p$—and estimates the resulting threshold at about $10^{-6}$.

Load-bearing premise

The load-bearing premise is Definition 4’s second condition: the correction procedure must turn any input state, including one far from every codeword, into some codeword; without that closure, the multi-level induction cannot restart at the next level.

Editorial extensions

If this is right

A physical error rate below a code-dependent constant suffices for arbitrarily long quantum computation with polylogarithmic time and space overhead, rather than requiring the error rate to shrink as the computation grows.
The threshold is not fixed by nature: better proper codes with larger distance-to-spread ratios and smaller procedures raise $η_0$, making the practical target easier to meet.
The same construction can be laid out on nearest-neighbor architectures at a lower threshold, so locality costs can be traded against error tolerance.
Because the scheme avoids measurement during computation and is defined for mixed states, it fits a unitary noisy-circuit model in which faults are analyzed as random sparse paths.
The construction leaves open whether the polylogarithmic depth overhead can be reduced to a constant factor, as in the classical fault-tolerance analogy.

Reading between the lines

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

The hard part shifts from “can noise be tolerated at all” to “which codes are proper”: a search for codes with high distance, small spread, and a correction map defined on every state is the practical lever for raising the threshold.
The $10^{-6}$ estimate is a proof-of-concept parameter rather than a barrier, because the threshold depends exponentially on $d/2l$; modest improvements in code parameters could move it by orders of magnitude.
The requirement that correction map every state to a codeword is an attractor-like property, so candidate codes can be tested by deliberately feeding their correction step states far from any codeword and checking whether the output lands back in the code.
Nearest-neighbor layout plus concatenation suggests a hardware-design tradeoff: extra swap gates lower the threshold but preserve the polylogarithmic overhead, so architectural locality can be treated as a parameter in the same threshold calculation.

Original abstract

Recently Shor showed how to perform fault tolerant quantum computation when the error probability is logarithmically small. We improve this bound and describe fault tolerant quantum computation when the error probability is smaller than some constant threshold. The cost is polylogarithmic in time and space, and no measurements are used during the quantum computation. The result holds also for quantum circuits which operate on nearest neighbors only. To achieve this noise resistance, we use concatenated quantum error correcting codes. The scheme presented is general, and works with all quantum codes that satisfy some restrictions, namely that the code is ``proper''. We present two explicit classes of proper quantum codes. The first example of proper quantum codes generalizes classical secret sharing with polynomials. The second uses a known class of quantum codes and converts it to a proper code. This class is defined over a field with p elements, so the elementary quantum particle is not a qubit but a ``qupit''. With our codes, the threshold is about 10^(-6). Hopefully, this paper motivates a search for proper quantum codes with higher thresholds, at which point quantum computation becomes practical.

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, 8,526 input tokens.

What the abstract itself states, as probabilities: claims first 0.07 · states limitation 0.87 · human participants 0.01 · controlled comparison 0.09 · randomized assignment 0.01 · states quantitative result 0.98 · compares with prior results 0.96 · mentions code or data availability 0.02.

The abstract, sentence by sentence

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

Recently Shor showed how to perform fault tolerant quantum computation when the error probability is logarithmically small. We improve this bound and describe fault tolerant quantum computation when the error probability is smaller than some constant threshold. The cost is polylogarithmic in time and space, and no measurements are used during the quantum computation. The result holds also for quantum circuits which operate on nearest neighbors only. To achieve this noise resistance, we use concatenated quantum error correcting codes. The scheme presented is general, and works with all quantum codes that satisfy some restrictions, namely that the code is ``proper''. We present two explicit classes of proper quantum codes. The first example of proper quantum codes generalizes classical secret sharing with polynomials. The second uses a known class of quantum codes and converts it to a proper code. This class is defined over a field with p elements, so the elementary quantum particle is not a qubit but a ``qupit''. With our codes, the threshold is about 10^(-6). Hopefully, this paper motivates a search for proper quantum codes with higher thresholds, at which point quantum computation becomes practical.

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	Recently Shor showed how to perform fault tolerant quantum computation when the error probability is logarithmically small.	background 1.00	0.03	0.03	asserted 1.00
s1	We improve this bound and describe fault tolerant quantum computation when the error probability is smaller than some constant threshold.	contribution 0.90	0.94	0.85	asserted 1.00
s2	The cost is polylogarithmic in time and space, and no measurements are used during the quantum computation.	result 0.94	0.89	0.21	asserted 1.00
s3	The result holds also for quantum circuits which operate on nearest neighbors only.	result 0.96	0.82	0.07	asserted 1.00
s4	To achieve this noise resistance, we use concatenated quantum error correcting codes.	method 1.00	0.87	0.07	asserted 1.00
s5	The scheme presented is general, and works with all quantum codes that satisfy some restrictions, namely that the code is ``proper''.	contribution 0.47	0.82	0.16	asserted 1.00
s6	We present two explicit classes of proper quantum codes.	contribution 0.98	0.93	0.06	asserted 1.00
s7	The first example of proper quantum codes generalizes classical secret sharing with polynomials.	contribution 0.89	0.79	0.03	asserted 1.00
s8	The second uses a known class of quantum codes and converts it to a proper code.	contribution 0.74	0.82	0.03	asserted 1.00
s9	This class is defined over a field with p elements, so the elementary quantum particle is not a qubit but a ``qupit''.	method 0.46	0.44	0.03	asserted 1.00
s10	With our codes, the threshold is about 10^(-6).	result 1.00	0.90	0.16	asserted 0.92
s11	Hopefully, this paper motivates a search for proper quantum codes with higher thresholds, at which point quantum computation becomes practical.	future work 0.99	0.09	0.08	hedged possibility 0.68

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

What was examined, and what was not

sources read

arXiv listing abstract v2

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

Works cited (25)

[21]

R. Solovay and A.C. Yao. in preperation

View on Pith
[1]

D. Aharonov and M. Ben-Or. Polynomial simulations of dec ohered quantum computers. 37th Annual Symposium on Foundations of Computer Science , pages 46–55, 1996

View on Pith 1996
[2]

D. Aharonov, M. Ben-Or, R. Impagliazzo, and N. Nisan. Lim itations of noisy reversible computation. In Submitted to STOC 97 , 1996

View on Pith 1996
[3]

D. Aharonov and N. Nisan. Quantum circuits with mixed sta tes. in preparation

View on Pith
[4]

A.R.Calderbank and P.W.Shor. Good quantum error correc ting codes exist. In phys.Rev.A, to appear , pages quant–ph/9512032, 1995

View on Pith 1995
[5]

M. Ben-Or, S. Goldwasser, and A. Wigderson. Completenes s theorems for fault-tolerant distributed computing. In Proc. 20th ACM Symp. on Theory of Computing , pages 1–10, Chicago, 1988. ACM

View on Pith 1988
[6]

I. L. Chuang, R. Laﬂamme, P. W. Shor, and W. H. Zurek. Quant um computers, factoring and decoherence. Science, 270:1633–1635, 1995

View on Pith 1995
[7]

I. Cirac and P. Zoller. Phys.Rev.Lett, 74:4091, 1995. 11

View on Pith 1995
[8]

D. Deutch. Quantum networks. In Proc. Roy. Soc. Lond, Vol. A400 , 1989

View on Pith 1989
[9]

DiVincenzo. Quantum computation. Science, 270, 1995

View on Pith 1995
[10]

P. Ga’cs. Self correcting two dimentional arrays. In S. Micali, editor, Randomness and Computation , volume 5 of Advances in Computing Research, pages 240–241,246–248. 1989. series editor: F.P.Prepara ta

View on Pith 1989
[11]

I.Chuang, W.C.D. Leung, and Y. Yamamoto. Bosonic quant um codes for amplitude damping. 1996

View on Pith 1996
[12]

J.J.Saqurai. Modern Quantum Mechanics, revised edition. Addison Wesley, 1994

View on Pith 1994
[13]

E. Knill. Non-binary unitary error bases and quantum co des. quant-ph/9608048, 1996

View on Pith Pith review arXiv 1996
[14]

E. Knill, R. Laﬂamme, and W.H. Zurek. Threshold accurac y for quantum computation. quant- ph/9610011, 1996

View on Pith 1996
[15]

R. Laﬂamme, C. Miquel, J.P. Paz, and W.H Zurek. Perfect q uantum error correcting codes. quant- ph/9602019, 1996

View on Pith 1996
[16]

S. Lloyd. A potentially realizable computer. In Science, Vol 261 , pages 1569–1571, 1993

View on Pith 1993
[17]

G. M. Palma, K.A. Suominen, and A. Ekert. Quantum comput ation and dissipation. Proc. Roy. Soc. Lond., 1995

View on Pith 1995
[18]

P. Shor. Scheme for reducing decoherence in quantum com puter memory. Phys.Rev.A, 52(4), 1995

View on Pith 1995
[19]

P. W. Shor. Fault-tolerant quantum computation. In 37th Annual Symposium on Foundations of Com- puter Science, 1996

View on Pith 1996
[20]

P.W. Shor. Algorithms for quantum computation: Discre te logarithms and factoring. In 35th Annual Symposium on Foundations of Computer Science , pages 124–134, 1994

View on Pith 1994
[22]

A.M. Steane. Multiple particle interference and quant um error. In Proc.Roy.Soc.London.Ser, to appear. Also quant-ph/9601029

View on Pith Pith review arXiv
[23]

W. G. Unruh. Maintaining coherence in quantum computer s. Technical report, University of Vancouver,

View on Pith
[24]

W.H.Zurek. Decoherence and the transition from quantu m to classical. In Physics today 44(10) , pages 36–44, 1991

View on Pith 1991
[25]

A. Yao. Quantum circuit complexity. In 34th Annual Symposium on Foundations of Computer Science , pages 352–361, 1993. 8 Appendix A Here we give the proof that the if the ﬁnal density matrix is d−deviated from the correct one, than measuring the qubits and taking majority gives the correct a nswer. Lemma 3 : Let ρ0 be the density matrix of the mixed state...

View on Pith 1993

Forward citations

Cited by 19 Pith papers

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

Unpaired Majorana fermions in quantum wires
cond-mat.mes-hall 2000-10 accept novelty 9.0 of 10

A gapped one-dimensional superconductor whose normal spectrum has an odd number of Fermi points in each half Brillouin zone hosts one unpaired Majorana mode per end, producing two nearly degenerate ground states of op...
A local automaton for the 2D toric code
quant-ph 2024-12 conditional novelty 8.0 of 10

A strictly local measurement-and-feedback decoder for the 2D toric code is built from hierarchical Tsirelson-type automata, preserving a logical qubit for times exponential in system size.
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.
Topological quantum memory
quant-ph 2001-10 accept novelty 8.0 of 10

Surface codes have a nonzero accuracy threshold, below which quantum information can be stored and reliably processed with local gates, and the threshold is set by a phase transition in a quenched three-dimensional Z2...
Fault-tolerant quantum computation by anyons
quant-ph 1997-07 accept novelty 8.0 of 10

Anyons in a two-dimensional system with only local interactions give a quantum computer that is fault-tolerant by physics, realized through the toric code and nonabelian anyon models.

Show 14 more citing papers

Quantum Error Correction via Codes over GF(4)
quant-ph 1996-08 accept novelty 8.0 of 10

Quantum error-correcting codes are equivalent to additive self-orthogonal codes over GF(4) under a trace inner product, enabling classical coding constructions and new bounds.
BQP-completeness of Scattering in Scalar Quantum Field Theory
quant-ph 2017-03 conditional novelty 7.0 of 10

Estimating the vacuum-to-vacuum transition amplitude in (1+1)-dimensional massive phi^4 theory with spacetime-dependent classical sources is BQP-complete.
Fault-tolerant quantum computing with color codes
quant-ph 2011-08 conditional novelty 7.0 of 10

Simulating full syndrome-extraction circuits for 4.8.8 color codes with an integer-program most-likely-error decoder yields an accuracy threshold of 0.082(3)%, about a tenth of the surface-code value under the same no...
Quantum Circuits with Mixed States
quant-ph 1998-06 accept novelty 7.0 of 10

Quantum circuits with density matrices and non-unitary gates are shown equivalent to standard circuits, probabilistic subroutines get a black-box definition that does not increase power, and the diamond norm is introd...
Coset Ensemble Decoder for Quantum Error Correction with Algorithm-Hardware Co-Design
cs.AR 2026-06 unverdicted novelty 6.0 of 10

Presents a coset ensemble decoder with algorithm-hardware co-design that claims better accuracy-latency trade-off and lower FPGA resource use than MWPM and UF baselines under depolarizing noise.
Quantum fault tolerance in small experiments
quant-ph 2016-10 conditional novelty 6.0 of 10

A five-qubit ring running the four-qubit error-detecting code, together with a stated criterion comparing encoded versus unencoded error rates, is the smallest proposed demonstration of fault-tolerant quantum computation.
Noise Threshold for a Fault-Tolerant Two-Dimensional Lattice Architecture
quant-ph 2006-04 conditional novelty 6.0 of 10

A 2D nearest-neighbor architecture using noisy SWAPs for qubit movement has a fault-tolerant noise threshold lower bound of 1.85e-5 for the concatenated [[7,1,3]] code, close to the 3.61e-5 nonlocal threshold.
Minimum weight perfect matching of fault-tolerant topological quantum error correction in average $O(1)$ parallel time
quant-ph 2013-07 conditional novelty 5.0 of 10

The minimum-weight perfect matching decoder for topological quantum codes can run in O(1) average parallel time per error-correction round on a local 2-D processor array, independent of code size.
Complex instruction set computing architecture for performing accurate quantum $Z$ rotations with less magic
quant-ph 2013-02 conditional novelty 5.0 of 10

Direct distillation of Z(π/2^k) magic states with shortened quantum Reed-Muller codes reduces resource-state counts for accurate Z rotations compared with a T-gate RISC architecture, for target errors above roughly 10^-10.
Native Non-Clifford Gates in Quantum LDPC Codes: Conditions, Synthesis, and Scaling Limits
quant-ph 2026-01 reject novelty 4.0 of 10

The main theorem claiming constant-depth logical CCZ gates exist from many 'magic-friendly triples' has mutually inconsistent hypotheses, and its key local-implementation step is unproved.
Fault-tolerant quantum computation
quant-ph 1997-12 accept novelty 3.0 of 10

Fault-tolerant quantum computation is possible in principle if the error rate per gate and per storage step is below a critical accuracy threshold.
Particle Physics Driven by Quantum Technology - Quantum Simulations and Quantum Sensing
hep-ph 2026-09 accept novelty 2.0 of 10

A comprehensive review of quantum simulation and quantum sensing techniques applied to particle physics, covering algorithm development, experimental implementations, and future prospects.
Quantum Error Correction for Quantum Memories
quant-ph 2013-02 accept novelty 2.0 of 10

A comprehensive review that organizes the theory and practice of qubit stabilizer codes, fault tolerance, and 2D surface-code architectures for protecting quantum memories.
An Introduction to Quantum Error Correction and Fault-Tolerant Quantum Computation
quant-ph 2009-04 accept novelty 2.0 of 10

A survey showing how stabilizer codes detect and correct quantum errors, and how fault-tolerant gadgets plus concatenated coding produce a constant physical error-rate threshold below which arbitrarily long quantum co...

How the literature uses it

35 arXiv papers cite this in 45 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 · 26 sentences without a confident label

Uses its method or tool 1 paper

The second strategy takes advantage of the well developed methods of quantum error correction, either employing techniques known as subsystem-, operator-, or Hamiltonian-encoding [ref] that suppress qubit errors using energy penalties, or more fundamentally and systematically, building the Feynman-Kitaev construct from a quantum circuit ${U_L(t)}_t=1^T$ that has quantum error correction and fault tolerance via concatenated encoding [ref] built in as being explained previously in this section.

Monte Carlo Quantum Computing · Universal Quantum Circuits Using Bi-Fermion Rebits · 0.87

Compares with it 3 papers

Also, the present efficiency is compatible with other state of the art protocols [ref] and we believe we can increase its efficiency at higher error rates by properly applying quantum error correction strategies at intermediate corrals [ref] .

Quantum Corralling · Disorder · 0.92
The first was presented in [ref] and later used in [ref] .

Constructing optimal quantum error correcting codes from absolute maximally entangled states · Quantum error correcting codes from AME states · 0.98
The analysis, by definition, has to be completely different from the error analysis in fault tolerant quantum computation, wherein the effect of noise is bounded by counting and weighting different fault paths [ref] .

Noise-resilient preparation of quantum many-body ground states · Introduction · 0.91

Cites it as support 1 paper

Now we know that, provided that the physical error rate per gate and per time step is below some constant threshold value, it is possible to make the logical quantum computation we wish to perform arbitrarily close to correct with overhead that is polylogarithmic in the length of the computation [ref] .

An Introduction to Quantum Error Correction and Fault-Tolerant Quantum Computation · The need for fault tolerance · 0.98

Cites it as background 13 papers

On the basis of fundamental early theoretical work [ref] , lip service is frequently paid to a necessary universal set of operations containing the two-qubit controlled-$σ_x$ (cnot) gate, and a necessary “threshold” error rate in the $10^-5-10^-4$ range.

Fault-Tolerant Computing With Biased-Noise Superconducting Qubits · Introduction · 0.97
While we cannot expect to reduce qubit noise arbitrarily with laboratory engineering alone, the theory of quantum error correction [ref] has shown that we can produce logical qubits that experience next-to-no noise by using a redundancy of high-quality physical qubits, provided the noise strength on the physical qubits as they perform computational operations is below some threshold value [ref] .

Practical quantum error correction with the XZZX code and Kerr-cat qubits · Introduction · 0.81
Quantum error-correcting codes [ref] used fault-tolerantly can perform arbitrarily accurate computations with noisy components, provided the noise stays below a threshold as the system size is scaled up [ref] .

Lower overhead fault-tolerant building blocks for noisy quantum computers · Local measurements on a 1-D chain · 0.99

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.

[1] [21]

R. Solovay and A.C. Yao. in preperation

View on Pith

[2] [1]

D. Aharonov and M. Ben-Or. Polynomial simulations of dec ohered quantum computers. 37th Annual Symposium on Foundations of Computer Science , pages 46–55, 1996

View on Pith 1996

[3] [2]

D. Aharonov, M. Ben-Or, R. Impagliazzo, and N. Nisan. Lim itations of noisy reversible computation. In Submitted to STOC 97 , 1996

View on Pith 1996

[4] [3]

D. Aharonov and N. Nisan. Quantum circuits with mixed sta tes. in preparation

View on Pith

[5] [4]

A.R.Calderbank and P.W.Shor. Good quantum error correc ting codes exist. In phys.Rev.A, to appear , pages quant–ph/9512032, 1995

View on Pith 1995

[6] [5]

M. Ben-Or, S. Goldwasser, and A. Wigderson. Completenes s theorems for fault-tolerant distributed computing. In Proc. 20th ACM Symp. on Theory of Computing , pages 1–10, Chicago, 1988. ACM

View on Pith 1988

[7] [6]

I. L. Chuang, R. Laﬂamme, P. W. Shor, and W. H. Zurek. Quant um computers, factoring and decoherence. Science, 270:1633–1635, 1995

View on Pith 1995

[8] [7]

I. Cirac and P. Zoller. Phys.Rev.Lett, 74:4091, 1995. 11

View on Pith 1995

[9] [8]

D. Deutch. Quantum networks. In Proc. Roy. Soc. Lond, Vol. A400 , 1989

View on Pith 1989

[10] [9]

DiVincenzo. Quantum computation. Science, 270, 1995

View on Pith 1995

[11] [10]

P. Ga’cs. Self correcting two dimentional arrays. In S. Micali, editor, Randomness and Computation , volume 5 of Advances in Computing Research, pages 240–241,246–248. 1989. series editor: F.P.Prepara ta

View on Pith 1989

[12] [11]

I.Chuang, W.C.D. Leung, and Y. Yamamoto. Bosonic quant um codes for amplitude damping. 1996

View on Pith 1996

[13] [12]

J.J.Saqurai. Modern Quantum Mechanics, revised edition. Addison Wesley, 1994

View on Pith 1994

[14] [13]

E. Knill. Non-binary unitary error bases and quantum co des. quant-ph/9608048, 1996

View on Pith Pith review arXiv 1996

[15] [14]

E. Knill, R. Laﬂamme, and W.H. Zurek. Threshold accurac y for quantum computation. quant- ph/9610011, 1996

View on Pith 1996

[16] [15]

R. Laﬂamme, C. Miquel, J.P. Paz, and W.H Zurek. Perfect q uantum error correcting codes. quant- ph/9602019, 1996

View on Pith 1996

[17] [16]

S. Lloyd. A potentially realizable computer. In Science, Vol 261 , pages 1569–1571, 1993

View on Pith 1993

[18] [17]

G. M. Palma, K.A. Suominen, and A. Ekert. Quantum comput ation and dissipation. Proc. Roy. Soc. Lond., 1995

View on Pith 1995

[19] [18]

P. Shor. Scheme for reducing decoherence in quantum com puter memory. Phys.Rev.A, 52(4), 1995

View on Pith 1995

[20] [19]

P. W. Shor. Fault-tolerant quantum computation. In 37th Annual Symposium on Foundations of Com- puter Science, 1996

View on Pith 1996

[21] [20]

P.W. Shor. Algorithms for quantum computation: Discre te logarithms and factoring. In 35th Annual Symposium on Foundations of Computer Science , pages 124–134, 1994

View on Pith 1994

[22] [22]

A.M. Steane. Multiple particle interference and quant um error. In Proc.Roy.Soc.London.Ser, to appear. Also quant-ph/9601029

View on Pith Pith review arXiv

[23] [23]

W. G. Unruh. Maintaining coherence in quantum computer s. Technical report, University of Vancouver,

View on Pith

[24] [24]

W.H.Zurek. Decoherence and the transition from quantu m to classical. In Physics today 44(10) , pages 36–44, 1991

View on Pith 1991

[25] [25]

A. Yao. Quantum circuit complexity. In 34th Annual Symposium on Foundations of Computer Science , pages 352–361, 1993. 8 Appendix A Here we give the proof that the if the ﬁnal density matrix is d−deviated from the correct one, than measuring the qubits and taking majority gives the correct a nswer. Lemma 3 : Let ρ0 be the density matrix of the mixed state...

View on Pith 1993