Evans and Pippenger showed in 1998 that e-noisy gates with 2 inputs are universal for arbitrary computation (i.e. can compute any function with bounded error), if all gates fail independently with probability isin and isin0= (3 - radic7)/4 ap8.856%. We show that formulas built from gates with 2 inputs, in which each gate fails with probability at least isin0cannot be universal. Hence, there is a threshold on the tolerable noise for formulas with 2-input gates and it is isin0. We conjecture that the same threshold also holds for circuits.
Evans and Pippenger showed in 1998 that e-noisy gates with 2 inputs are universal for arbitrary computation (i.e. can compute any function with bounded error), if all gates fail independently with probability isin and isin0= (3 - radic7)/4 ap8.856%. We show that formulas built from gates with 2 inputs, in which each gate fails with probability at least isin0cannot be universal. Hence, there is a threshold on the tolerable noise for formulas with 2-input gates and it is isin0. We conjecture that the same threshold also holds for circuits.
It is known that epsi-noisy gates with two inputs are universal for arbitrary computation (i.e., can compute any function with bounded error), if all gates fail independently with probability epsi and epsi2= (3 - radic7)/4 ap 8.856%. In this paper, it is shown that this bound is tight for formulas, by proving that gates with two inputs, in which each gate fails with probability at least beta2cannot be universal. Hence, there is a threshold on the tolerable noise for formulas with two-input gates and it is beta2. It is conjectured that the same threshold also holds for circuits.
We consider fault-tolerant computation with formulas composed of noisy Boolean gates with two input wires. In our model all gates fail independently of each other and of the input. When a gate fails, it outputs the opposite of the correct output. It is known that if all gates fail with probability at least β2 = (3− √ 7)/4 ≈ 8.856%, faulttolerant computation is not possible. On the other hand, if all gates fail with probability < β2 and is the same for all gates, then fault-tolerant computation is possible. The assumption that all gates fail with exactly the same probability is pretty strong and unrealistic in real-world scenarios. Furthermore, one might be tempted to think that it can be removed easily, since making gates “better” should not hurt. Surprisingly, this is not the case, as we show in this work: there is a constant α2 < β2 such that almost all functions cannot be computed by formulas, if the noise rate of each individual gate is selected adversarially in the range [0, α2]. Hence, while a hardware manufacturer who consistently produces bad gates with noise rate α2 can always achieve reliable computation, a manufacturer who can only ensure that all gates have noise rates at most α2 cannot.
We prove new upper bounds on the tolerable level of noise in a quantum circuit. We consider circuits consisting of unitary k-qubit gates each of whose input wires is subject to depolarizing noise of strength p, as well as arbitrary one-qubit gates that are essentially noise-free. We assume that the output of the circuit is the result of measuring some designated qubit in the final state. Our main result is that for p>1-Θ(1/\sqrt{k}), the output of any such circuit of large enough depth is essentially independent of its input, thereby making the circuit useless. For the important special case of k=2, our bound is p>35.7%. Moreover, if the only allowed gate on more than one qubit is the two-qubit CNOT gate, then our bound becomes 29.3%. These bounds on p are notably better than previous bounds, yet are incomparable because of the somewhat different circuit model that we are using. Our main technique is the use of a Pauli basis decomposition, which we believe should lead to further progress in deriving such bounds.
We prove new upper bounds on the tolerable level of noise in a quantum circuit. We consider circuits consisting of unitary k-qubit gates each of whose input wires is subject to depolarizing noise of strength p, as well as arbitrary one-qubit gates that are essentially noise-free. We assume that the output of the circuit is the result of measuring some designated qubit in the final state. Our main result is that for p>1−Θ(1/k), the output of any such circuit of large enough depth is essentially independent of its input, thereby making the circuit useless. For the important special case of k=2, our bound is p>35.7%. Moreover, if the only allowed gate on more than one qubit is the two-qubit CNOT gate, then our bound becomes 29.3%. These bounds on p are numerically better than previous bounds, yet are incomparable because of the somewhat different circuit model that we are using. Our main technique is the use of a Pauli basis decomposition, in which the effects of depolarizing noise are very easy to describe.
Determining the highest amount of noise that quantum circuits can handle is an interesting and crucial task in the development of fault-tolerant quantum computation. Previous work has constrained this upper limit for local depolarizing noise to ≈45% for circuits constructed using the universal Clifford with T gate set by finding the noise threshold where the gate set loses universality. In this work, we use a similar method with the matchgate with non-Gaussian resource universal gate set to find a limit of p=(8−26)/5 or ≈62% for fermionic quantum computing that is independent of circuit depth. To do this, we use Uhlmann-Wootters concurrences for a 4-mode fermionic Choi state representing a resourceful gate combined with local depolarizing noise to determine when the combined channel is convex Gaussian. These bounds are not directly comparable due to differences in noise model making the bound of ≈62% the best known for fermions.
We present two new positive results for reliable computation using formulas over physical alphabets of sizeq>2. First, we show that for logical alphabets of sizeℓ=qthe threshold for denoising using gates subject to q-ary symmetric noise with error probability$\varepsilon isstrictlylargerthanthatforBooleancomputation,andweshowthatreliablecomputationispossibleaslongassignalsremaindistinguishable,i.e.\epsilon \lt (q - 1) / q,inthelimitoflargefan−ink \rightarrow \infty .Wealsodeterminethepointatwhichgeneralizedmajoritygateswithboundedfan−infail,andshowinparticularthatreliablecomputationispossiblefor\epsilon \lt (q - 1) / (q (q + 1))inthecaseofqprimeandfan−ink = 3.Secondly,weprovideanexamplewhere\ell \lt q,showingthatreliableBooleancomputation,\ell = 2,canbeperformedusing2−inputternary,q = 3,logicgatessubjecttosymmetricternarynoiseofstrength\varepsilon \lt 1/6$by using the additional alphabet element for error signaling.