Quantum computations: algorithms and error correction

The basis Q is complete in the approximate sense.

“We shall see that Q is a complete basis in the approximate sense, see Theorem 4.8 below.”

The norm of an admissible transformation is always one.

“The norm of an admissible transformation is always equal to one.”

If F is computable in a basis A by a Boolean scheme of dimension L, then F⊕ can be represented in the basis A⊕ by a reversible scheme of dimension 2L plus m.

“Proposition 2.3.We assume that F : Ν ->• B m (N C B n ) is computable in a basis A by means of a Boolean scheme of dimension L. Then F® can be represented in the basis A& = {/® : / G A} by a reversible scheme of dimension 2L + m.”

C⊕ is a complete basis for reversible computations.

“Corollary. C^ is a complete basis for reversible computations.”

If an admissible transformation from a space to its tensor product with an auxiliary space is trace-preserving over the auxiliary space, then it acts as tensoring with a fixed state on the auxiliary space.

“Proposition 3.6.Let Τ £ T(M,M ® 1) be an admissible transformation such that Try Γ = I M .Then there exists λ G D(J) such that TX = X <g> λ (for any X € L(M)).”

Any classical operator can be represented in the basis Q.

“Any classical operator can be represented in the basis 3? = {1.3,σχ ,@,Λφ}.(This follows from the completeness of the classical reversible basis 31.)It follows that any classical operator can be represented in the basis Q.”

For the discrete logarithm, if a basis of the subgroup P is known, one can find an element of the form (m, -1) in P, and then m is the discrete logarithm of g with base zeta.

“If a basis of the subgroup Ρ C Z 2 is known, then it is easy to find an element of the form (τη, -1) G P. Then ( m = g, that is, m is the discrete logarithm of g with base ζ.”

• AssumptionThe authors state this as an assumption: The action of the group G on the finite set M and the group operations in G are easy to compute.
• AssumptionThe authors state this as an assumption: The group G in the stabilizer problem is Abelian.
• AssumptionThe authors state this as an assumption: The set M can be identified with a subset of the Boolean cube B^n.
• AssumptionThe authors state this as an assumption: The function F is available as an oracle or black box that returns F(g,x) for inputs in its domain.

The operators S and K generate a finite group of order 192.

“The operators 5 and Κ (see (24)) generate a finite group Ε C U(25) of order 192.”

There is a simple polynomial algorithm that reduces a basis to a unique canonical form for a given subgroup A of Z^k.

“Moreover, there exists a rather simple polynomial algorithm for reducing a basis to a unique (for a given subgroup A C Z k ) canonical form.”

• AssumptionThe authors state this as an assumption: The action of the group G on the finite set M and the group operations in G are easy to compute.
• AssumptionThe authors state this as an assumption: The group G in the stabilizer problem is Abelian.
• AssumptionThe authors state this as an assumption: The set M can be identified with a subset of the Boolean cube B^n.
• AssumptionThe authors state this as an assumption: The function F is available as an oracle or black box that returns F(g,x) for inputs in its domain.

For a subgroup H stabilizing a vector and a unitary V not preserving that vector's subspace, the set H together with V^{-1}HV generates the whole SU(M).

“Then the set of operators Η U V~1HV generates the whole group SU(M).”

The operators X1 and X2 preserve the vectors |00> and |01>+|10>+|11>.

“The operators X U X 2 preserve the vectors |00) and I77) = | 01> + 110) + |11).”

The completeness of Q' follows from the completeness of the infinite basis Q' together with U(1).

“The completeness of Q' follows from that of the infinite basis Q' U U(l).”

The basis operators satisfy the commutation relation σ(f)σ(g)=(-1)^{ω(f,g)}σ(g)σ(f), where ω is the skew-symmetric form (44).

“σ{ί)σ(9) = (-1) ω{Μ σ( 9 )σ(ί). (45”

Any (R, ε/2)-net contains an (R, ε)-net whose points are separated by more than ε/3 and which lies in the (R+ε)-neighbourhood of the identity.

“Indeed, any (R, ε/2)-ηεΐ Γ contains an (R,e)-net Γ, with the following additional properties:”

The constructed transformation R is an error-correcting transformation.

“We shall show that it is indeed an error correcting transformation.”

There exists a symplectic code of type (5,1) that corrects one error.

“Example 9.3.A symplectic code of type (5,1) correcting one error.”

The environment state in the admissible-transformation scheme can always be taken to be pure.

“We observe that λ can always be assumed to be a pure state.(It suffices to replace S by S ® 9* and use (13).)”

A graded subalgebra σ(F) is commutative exactly when F is a homogeneous subspace, i.e. ω(f,g)=0 for all f,g in F.

“The subalgebra a(F) is commutative if and only if F is a homogeneous subspace, that is, u(f,g) = 0 for any f,g(z G n”

A symplectic code corrects k errors if and only if E(n,2k)∩F^+ ⊂ F.

“Corollary.A symplectic code corrects k errors if and only if Ε (η, 2k) Π ί+ C F.”

A universal quantum scheme can model any scheme of given dimension L when appropriate control bits are assigned.

“We have thus constructed a scheme which can model any scheme of dimension L if the appropriate values are assigned to the control bits.”

The quotient of the extended symplectic group by G^n is isomorphic to Sp2(n).

“It follows that ESp 2 (n)/G n = Sp 2 (n).”

The correction transformation CORR can be realized by a layered scheme of depth 2 using elements A_c(σ_x) and A_c(σ_z).

“The transformation CORR can be realized by a layered scheme of depth 2 from the elements A c (a x ) and A c (a z ).”

The bases Q and Q' generate the same set of unitary transformations up to phase.

“On the other hand, Q and Q' generate the same set of unitary transformations U • U^.”

The measurement transformation MEAS can be realized by a scheme of depth O(n) and dimension O(n^2) using |0⟩, S, A(σ_x), A(σ_y), A(σ_z), and Q_g.

“The transformation MEAS can be realized by a scheme of depth O(n) and dimension 0{n 2 ) from the elements |0), 5, Α(σ χ ),Α(σ υ ),Α(σ ζ ) and Ο,β.”

Because S[1] does not preserve the subspace spanned by |00>, a dense subset can be generated in SU(B⊗2).

“Finally, the operator 5[1] does not preserve the subspace (|00)), so a dense subset can be generated in SU(53® 2 ).”

The total probability that h1...h_l do not generate H is less than k l ε + 2^{n-l}(1+2kε)^l.

“It follows that the total probability that hi,... ,hi do not generate Η is less than kle + 2 n ~'(l + 2ke) 1 .”

The operator Θ^n[A,D] determines ζ_A without error.

“For example, the operator © n [A, D] measures the value of ζ A with zero probability of error.”

We can generate a random element of H with almost uniform distribution.

“In this way we can generate a random element Η with almost uniform distribution.”

The simple quantum repetition code does not protect against a single error, specifically it cannot correct errors from E(n,1).

“However, such a quantum code does not even protect from a single error or, more precisely, it cannot correct errors from £{n, 1).”

With I=n+4 and ε=(6M)^-1, the random elements h1,...,h_I ∈ (Q/Z)^k generate H with probability ≥ 1/2.

“Then the random elements hi,... ,hi Ε (Q/Z)* generate i/ with probability ^ |.”

Let g be a permutation of N⊂B^n. An eigenvalue of U=g can be measured with probability of error ≤ ε using a quantum scheme of dimension poly(n)+O(n)log(1/ε) in basis Q U {A}.

“Theorem 5.5. Let g be a permutation of a set Ν C B n .An eigenvalue of the operator U -'g can be measured with probability of error not greater than ε with the aid of a quantum scheme of dimension poly(rc) + O(n) log(l/e) in the basis Q U {[/I”

Any homogeneous subspace F of G^n can be reduced by a suitable symplectic transformation to the standard form F' = {(0,...,0,β1,...,βs,0,...)} with s=dim F.

“Acting by a suitable symplectic transformation, we can reduce any homogeneous subspace F C G n to the standard form F' = {(Oft,... ,0/θ.,Ο,... ,0) : Α, ...,β.€ F 2 },”

The operator algebra on one qubit carries a gradation by the group Z2×Z2 when the index set {0,x,y,z} is identified with that group.

“The remarkable properties of this basis manifest themselves if the index set G = {0,x,y,z} -{00,10,11,01} is identified with the group Z 2 x Z 2 .”

The commutative diagram (62) holds with accuracy O(ε).

“The diagram (62) is commutative with accuracy Ο(ε).”

The operators S[1], S[2], and Λ(K)[1,2]=Λ(K)[2,1], together with all phase factors, generate a dense subset of U(B^{⊗2}).

“Lemma 4 . 6 . The operators S[l], S[2] and Λ(ΑΓ)[1,2] = A(K)[2,1], along with all possible phase factors, generate a dense subset in the group U(25® 2 ).”

Theorem 10.7: If C is a code of type (n,1) admitting encoding and decoding by schemes in basis A, and each t in A has a (2,2Γ,T)-stable step-by-step realization Φ_t in C and A, and Trans(Φ_t) represents the identity in the strong sense, then there exists a polynomial error correction system in A for any sufficiently small δ>0.

“Theorem 10.7.Let C be a code of type (n, 1) admitting encoding and decoding by schemes in the basis A, and let Γ C 2ι 1>-••' η '.We assume that each transformation t € A has a (2, 2Γ, T)-stable step-by-step realization Φί in the code C and in the basis A. Moreover, suppose that Trans(«I>/) represents the identity transformation I -TVg in the strong sense.Then there exists a polynomial error correc”

The accuracy O(δ^{2^r}) is ensured by a code of type (5^r,1).

“The accuracy Ο(δ 2 ^) is ensured by a code of type (5 r , 1).(Such codes are called cascade codes.)”

The entire procedure for the stable realization of QB is stable when two errors occur.

“It is easily seen that the whole procedure is stable under two errors.”

If a quantum scheme of dimension L computes F with error at most ε and each operation has accuracy δ, then the resulting error is at most ε + 2Lδ.

“Proposition 4 . 2 . Suppose that a quantum scheme of dimension L computes a function F with probability of error ^ ε. // each operation of this scheme is performed with accuracy δ, then the resulting probability of error does not exceed ε + 2L6.”

The dimension of the resulting cascade schemes increases as a^r (a=const), i.e., as a power of the logarithm of accuracy.

“The dimension of the resulting schemes increases as a r (a = const), that is, as a power of the logarithm of accuracy.”

Theorem 11.1: For any sufficiently small δ>0, there exist polynomial error correction systems in the symplecto-classical basis SC and the complete basis QC.

“Theorem 11.1.For any sufficiently small δ > 0 there exist polynomial error correction systems in the symplecto-classical basis §C and the complete basis QC.”

• AssumptionThe authors state this as an assumption: In the symplecto-classical case, all classical elements in the basis SC are accurate.

In the torus lattice, the support of any cycle or cocycle not homologous to zero contains at least k edges.

“The support of any cycle or cocycle non-homologous to zero consists of no fewer than k edges.”

To make the remaining basis elements (2,2Γ,Γ)-stable, one first reduces the number of errors in the input using the scheme Σ.

“To make them (2, 2Γ, F)-stable we need first to reduce the number of errors in the input with the aid of the scheme Σ (see Fig. 2b).”

• AssumptionThe authors state this as an assumption: In the symplecto-classical case, all classical elements in the basis SC are accurate.

Any unitary operator U in U(B^{⊗n}) can be represented as a product of 2^n(2^n-1)/2 such operators.

“Any unitary operator U £ U(S® n ) can be represented as a product of 2 n (2™ -l)/2 such operators.”

The code D does not protect against errors of the form σ_z[j].

“However, we observe that D does not protect against errors of the form a z [j].”

If one error occurs while the MEAS scheme for a local-verification code is run, only O(1) qubits are corrupted.

“It follows that if one error occurs as the MEAS scheme is run, then only 0(1) qbits will be corrupted.”

The infinite sequence of quasilinear torus codes TOR(k) is an example of a code with local verification.

“The infinite sequence of quasilinear codes TOR(fc) (k = 1,2,...), constructed as follows [42], is a beautiful example of a code with local verification.”

• cites [42]Not checked yet

  Not checked in the free run.

The cascade construction satisfies the first two conditions of Definition 10.4, up to replacing k by r ~ log k.

“Thus, the first two conditions in Definition 10.4 are satisfied (to within replacing k by r ~ logfc).”

The operators Λ(U^L), L=1,2,..., can be represented by a homogeneous sequence of polynomial schemes in basis Q'.

“Theorem 4 . 12 . The operators A(UL), L = 1,2,..., can be represented by a homogeneous sequence of polynomial schemes $£, in the basis Q'.”

The operator Λ(T_s) can be represented in basis Q with any accuracy.

“We shall see that Λ(Τ^) can be represented in the basis Q with any accuracy.”

For classical admissible transformations, if T represents P with accuracy ε, then there exists an admissible T' representing P such that ||T−T'||_0 ≤ 2ε.

“Proposition 10.2.Let Ρ 6 Τ(Μ,Μ') and f £ Τ(Ν,Ν') be classical admissible transformations.We assume that Τ represents Ρ with accuracy ε (in some classical codes).Then there is an admissible transformation Τ S Τ(Ν,Ν') representing Ρ such that ||Γ-Γ||ο ^ 2ε.”

For codes with local verification, the MEAS transformation can be realized by a scheme of depth O(1) and dimension O(n).

“For codes with local verification the transformation MEAS can be realized by a scheme of depth 0(1) and dimension 0{n).”

For positive integer I and r=2^{l-1}, for any ε>0 the value of φ can be measured with accuracy 2^{-l-2} and probability of error at most ε using a quantum scheme of dimension O(l log(l/ε))+poly(l) in basis Q ∪ {U^{[0·r]}}.

“Lemma 5 . 4 . Let I be a positive integer and let r = 2 l ~1.For any ε > 0 the value of φ can be measured with accuracy 2~~l~2 and probability of error not greater than ε with the aid of a quantum scheme of dimension O(/log(Z/e))+poly(Z) in the basis Q U {[/Ι°• Γ ]}.”

Conversely, if h_i=h_{i+1}=h_{i+2}, then at least one of Σ_i, Σ_{i+1}, Σ_{i+2} works without error, so h_i is a correct syndrome for the jth measurement.

“Conversely, let hi = hi+ι = hi+2 (such an i may not be unique).It is obvious that at least one of the subsystems Σί,Σί+ι,Σί+2 must work without an error (since there are only two errors).It follows that hi is a correct syndrome corresponding to the jth measurement (i ^ j ^ i + 2).”

• AssumptionThe authors state this as an assumption: In the symplecto-classical case, all classical elements in the basis SC are accurate.
• AssumptionThe authors state this as an assumption: The classical scheme Σ10 is absolutely reliable.

For n ≥ 5, the perturbed transformation R_n is the identity transformation I_B of a single bit in code REP(n,1) with accuracy O(δ^2).

“We shall show that for η ^ 5 the perturbed transformation R n is the identity transformation /B of a single bit in the code REP(n, 1) with accuracy O(<5 2 ).”

The torus code TOR(k) constructed is a quasilinear code of type (2k^2,2).

“The torus code TOR(A;) constructed in this way is a quasilinear code of type (2k 2 , 2).”

The torus code TOR(k) admits encoding and decoding by schemes of polynomial dimension in the basis S.

“Just like any symplectic code, it admits encoding and decoding by schemes of polynomial dimension in the basis S.”

• AssumptionThe authors state this as an assumption: In the symplecto-classical case, all classical elements in the basis SC are accurate.

A stable realization of W = Λ(σ_z σ_x) can be built using the earlier procedures, with W[1,2] = S[2]©[1,2]S[2]©[1,2].

“Using the procedures described above, we can construct a stable realization of W = Λ(σ ζ σ χ ), W[l, 2] = S[2] ©[1, 2] S[2] ©[1, 2].”

For a sequence of L operations, the correct result is obtained with probability at least 1 minus epsilon if each operation is performed with accuracy epsilon divided by 2L.

“In the general case a sequence of L operations yields the correct result with probability ^ 1ε if each operation is performed with accuracy e/(2L) (see Proposition 4.2 or [16]).”

• cites [16]Not checked yet

  Not checked in the free run.

The present article strengthens Shor's result by showing that fixed accuracy is sufficient for arbitrarily long quantum computations.

“In the present article this result is strengthened.We shall demonstrate that fixed accuracy is sufficient.To this end we use so-called cascade codes.”

• AssumptionRests on an assumption: In real-world conditions, qubits are subject to perturbations even when no operation is performed on them.

There is a randomized reduction from integer factorization to the problem of finding the order of an element.

“There exists a randomized reduction of the problem of 'factorization' to the problem of the 'order of an element' [49].”

• cites [49]Not checked yet

  Not checked in the free run.

• AssumptionThe authors state this as an assumption: The action of the group G on the finite set M and the group operations in G are easy to compute.
• AssumptionThe authors state this as an assumption: The group G in the stabilizer problem is Abelian.
• AssumptionThe authors state this as an assumption: The set M can be identified with a subset of the Boolean cube B^n.
• AssumptionThe authors state this as an assumption: The function F is available as an oracle or black box that returns F(g,x) for inputs in its domain.

The error probability of a quantum computation can be made arbitrarily small by repeating the computation several times and taking a majority vote.

“The probability of error can be made as small as desired by repeating the computation several times.”

A quantum computer could break public-key cryptographic systems whose security rests on the difficulty of discrete logarithm or integer factorization.

“(This means that a quantum computer could 'break' the corresponding codes.)”

In the derived code situation with Ή'=3Γ and £⊇3j, the homomorphism χ' is injective.

“In this case the homomorphism χ' is injective.”

• AssumptionThe authors state this as an assumption: In the derived code setting, Ή'=3Γ and £ contains 3j.

For any admissible transformation T, the scalar c(T) equals one.

“We observe that if Τ is an admissible transformation, then c(T) = 1.”

Every quantum computation can be recast as a measurement relative to its input.

“Any quantum computation (see Definition 4.1) can be set up as a measurement with respect to its input.”

When the error space E2 contains E1, the derived code for E2 is coarser than that for E1.

“1.If £2 2 £i, then Der(C, £2) is a coarser code than Der(C, £i).”

Theorem 8.4: T is an encoding transformation iff T(AB)=χ(A)T(B)=T(A)χ(B) for any A,B∈L(M).

“Theorem 8.4.Lei χ : L(M) -> L(,C) 6e an injective homomorphism of algebras with involution and let Τ £ T(M, £) 6e an admissible transformation.Τ is an encoding transformation (that is, χ*Τ = Ij^) if and only if Τ(ΑΒ) = χ(Α)Τ(Β)=Τ(Α)χ(Β) for any A,B £L(M). (42”

The symplectic basis is incomplete: it cannot realize every admissible transformation to arbitrary precision.

“It is not complete, that is, does not make it possible to realize an arbitrary admissible transformation with arbitrary accuracy.”

Constructing quantum codes is hard because bit-flip and phase errors must be handled at the same time.

“It follows that the difficulty in constructing quantum codes lies in the fact that classical and phase errors need to be corrected simultaneously.”

Measuring φ with arbitrary accuracy is difficult because the cost, the dimension of the scheme, grows polynomially with δ.

“Unfortunately, it is difficult to measure φ with arbitrary accuracy because the cost of such a measurement (that is, the dimension of the scheme) increases polynomially with δ.”

Deriving with the product E2E1 equals deriving first with E1 and then with E2.

“2. Der(C,£ 2 £i) = Der(Der(C,£i), E 2 ).”

In the symplecto-classical basis, one can perform coding, decoding and error correction.

“However, in this basis we can perform such useful procedures as coding, decoding and error correction.”

Quantum codes permit approximate recovery of a state following a perturbation.

“It follows that quantum codes can be used for the approximate reconstruction of a state after a perturbation.”

• AssumptionThe authors state this as an assumption: There exists a T in the error set such that ||T - f|| < ε.

For measurement operators U' and U'' with disjoint additional registers D' and D'', the joint conditional probability factors as P_{U'U''}(a,(y',y''))=P_{U'}(a,y')P_{U''}(a,y'').

“This is a consequence of the general property (11) of quantum probability.”

Measurement operators whose additional registers are disjoint commute.

“Measurement operators with disjoint additional registers commute.”

Multiplying measurement operators yields another measurement operator.

“A product of measurement operators is a measurement operator.”

It is impossible for an inaccurate scheme to realize exactly the same transformation as an accurate one, because an error at the first or last step inevitably disturbs input or output information.

“However, this is impossible, because any error at the first or the last steps will inevitably disturb the input or output information.”

Shor's method [43] makes partial correction of errors possible for any symplectic code.

“(Moreover, Shor's method [43] makes this possible for any symplectic code.)”

• cites [43]Not checked yet

  Not checked in the free run.