Verification of quantum computation: An overview of existing approaches

Alexandru Gheorghiu; Theodoros Kapourniotis; Elham Kashefi

Source-linked AI summary

Verification of quantum computation: An overview of existing approaches

Alexandru Gheorghiu, Theodoros Kapourniotis, Elham Kashefi

arXiv:1709.06984v2Sep 20, 2017quant-phcs.CR

TL;DR

Quantum verification asks how to check quantum computations when general experiments likely lack efficiently checkable witnesses. This paper reviews and compares existing protocols, finding distinct approaches with varied requirements, while none yet lets a classical client verify one quantum server.

Problem
Quantum verification seeks ways to check quantum-computation correctness despite the likely absence of witnesses certifying general quantum-experiment outcomes.
Method
The paper surveys quantum-verification protocols and compares their structure, complexity, resources, cryptographic techniques, fault tolerance, and experimental implementations.
Results
Reviewed protocols provide distinct verification approaches with different advantages, disadvantages, quantum requirements, communication costs, and robustness, but none achieves classical verification of one quantum server.
Takeaways & Limitations
Quantum verification combines cryptography, complexity theory, error correction, and quantum-correlation theory, with proof-of-concept experiments realized for some protocols.
Takeaways & Limitations
Post hoc protocols are not blind because they reveal the computation and input to the provers.

Abstract

from arXiv · show

Quantum computers promise to efficiently solve not only problems believed to be intractable for classical computers, but also problems for which verifying the solution is also considered intractable. This raises the question of how one can check whether quantum computers are indeed producing correct results. This task, known as quantum verification, has been highlighted as a significant challenge on the road to scalable quantum computing technology. We review the most significant approaches to quantum verification and compare them in terms of structure, complexity and required resources. We also comment on the use of cryptographic techniques which, for many of the presented protocols, has proven extremely useful in performing verification. Finally, we discuss issues related to fault tolerance, experimental implementations and the outlook for future protocols.

1 Introduction

Quantum verification asks whether quantum computations can be efficiently checked when their solutions may be classically intractable. The paper reviews verification models and techniques, emphasizing interactive proofs, blindness, and practical concerns such as fault tolerance.

Motivation: Quantum advantage motivates verification because quantum computers may solve problems believed intractable for classical computers, making their outcomes difficult to check.The central question is how to verify an experiment that solves a classically intractable problem.
Complexity-theoretic formulation: The complexity-theoretic challenge is whether every BQP problem has an interactive proof whose prover is restricted to BQP computations.Although BQP ⊆ IP, the unrestricted computational power of the IP prover makes this insufficient for the desired verification setting.
Interactive proofs: General quantum experiments are believed not to have efficiently computable classical witnesses, motivating interactive-proof systems with a BPP verifier and an interacting prover.The verifier and prover exchange messages for polynomially many rounds, while the prover is not restricted to efficient computation.
Verification models: Efficient verification becomes possible with multiple noncommunicating BQP provers or a single prover assisted by a constant-size quantum verifier able to exchange quantum states.These models alter the basic single-prover, classical-verifier formulation to obtain verification of arbitrary BQP computations.
Protocol techniques and scope: Blindness is the primary technique in most reviewed protocols: delegated computations are hidden from provers, while tests or traps detect deviations.The paper also reviews sub-universal protocols, fault tolerance, experimental implementations, and future outlook after classifying the main approaches.

2 Prepare-and-send protocols

Prepare-and-send protocols let a verifier certify delegated quantum computations using only constant-size quantum state preparation and sending, without measurement. The reviewed approaches comprise authentication-based, trap-based, and test-or-compute protocols, with correctness and verifiability guarantees alongside differing verifier resources.

Overview: The section covers three approaches: quantum-authentication protocols, a trap-based protocol, and a scheme repeating indistinguishable test and computation runs.These correspond to the subsections on QAS-based VQC, VUBQC, and Test-or-Compute.
Authentication-based protocols: For fixed m > 0, Clifford-QAS VQC achieves correctness δ = 1 and verifiability ϵ = 2−m.Its security reduces to the Clifford quantum authentication scheme, and honest execution returns the correct output state exactly.
Authentication-based protocols: For fixed d > 0, Poly-QAS VQC achieves correctness δ = 1 and verifiability ϵ = 2−d while reducing quantum communication to one initial message round.Both QAS protocols require a verifier quantum computer of size O(log(1/ϵ)); their total communication is bounded by O(|C| · log(1/ϵ)).
Trap-based protocol: For fixed d > 0, VUBQC achieves correctness δ = 1 and verifiability ϵ = (8/9)d using only single-qubit state preparation by the verifier.This reduces the verifier’s quantum capability relative to QAS-based protocols requiring a constant-size quantum computer.
Test-or-Compute: Test-or-Compute has completeness 8/9 and soundness 7/9, with X- and Z-tests detecting non-benign Pauli errors and bounding incorrect acceptance by ϵ = 2/3.Each test occurs with probability 1/3, yielding the stated incorrect-acceptance bound.
Common features and resources: All five protocols use or can be made blind, while only Clifford-QAS VQC requires two-way quantum communication and the others require one quantum message.Poly-QAS VQC and Test-or-Compute reveal the computation unless blindness is added by encoding the circuit into the one-time-padded input.

3 Receive-and-measure protocols

Receive-and-measure protocols give the verifier a trusted measurement device: the prover prepares and sends quantum states, which the verifier tests or measures. The section covers measurement-only and post hoc protocols, including a non-blind protocol that achieves an inverse-polynomial completeness–soundness gap.

3.1 Measurement-only protocol: The verifier randomly assigns received copies of a 2D cluster state to MBQC computation or stabilizer testing.Testing checks whether the prover prepared the correct cluster state.
3.1 Measurement-only protocol: Accepted testing makes the computation state close in trace distance to the ideal graph state, so their measurement-outcome distributions are almost indistinguishable.The testing confidence level α bounds the probability that the computation state fails the required condition.
3.1 Measurement-only protocol: Measurement-only protocols are receive-and-measure QPIP protocols with an inverse polynomial gap between completeness and soundness.One variant requires O(|C|^2) total communication according to the cited communication comparison.
3.2 Post hoc verification: The 1S-Post-hoc protocol reduces verification to measuring the energy of an XZ-Hamiltonian whose promise gap satisfies b − a ≥ 1/poly(|x|).For accepted computations, the ground state has energy below a; otherwise every state has energy above b.
3.2 Post hoc verification: 1S-Post-hoc is a receive-and-measure QPIP protocol with an inverse polynomial gap between completeness and soundness.It is optimal in measurement capability because the verifier only needs X and Z observables.
3.2 Post hoc verification: The 1S-Post-hoc protocol is the only receive-and-measure protocol in this comparison that is not blind.Unlike the other protocols, it does not hide the computation and input from the prover.

4 Entanglement-based protocols · 4.1 Verification based on CHSH rigidity · RUV protocol.

Entanglement-based verification uses multiple non-communicating entangled provers and a fully classical verifier, with CHSH rigidity enabling the RUV protocol to certify delegated quantum computation. RUV alternates CHSH testing, tomography, and computation subprotocols, and achieves an inverse polynomial completeness–soundness gap.

4 Entanglement-based protocols: Entanglement-based approaches use multiple non-communicating entangled provers with a fully classical verifier to check delegated quantum computations.They are broadly based on rigid self-testing or post hoc testing of local Hamiltonians.
RUV protocol.: The RUV protocol uses two non-communicating quantum provers, who may share unbounded entanglement, while the verifier interacts with them only classically.It can be generalized to any number of provers greater than two and delegates an arbitrary circuit C.
RUV protocol.: RUV alternates CHSH games, state tomography, process tomography, and computation to test resource preparation, measurements, and gate teleportation.The computation subprotocol combines resource preparation by Bob with Bell-basis measurements by Alice.
RUV protocol.: Local similarity between paired subprotocols prevents a prover from distinguishing tests from computation, supporting correctness when all but the computation subprotocol are tested.Alice receives the same operations in the CHSH/state-tomography pair, while Bob receives the same operations in the process-tomography/computation pair.
RUV protocol.: The protocol imposes only non-communication and near-optimal CHSH win-rate constraints, while rigidity forces accepted provers to follow the ideal strategy up to local isometry.The provers’ quantum systems may be arbitrarily large, and characterizing their shared state and observables enables verification.
RUV protocol.: RUV requires both provers to be universal quantum computers capable of storing multiple quantum states and performing quantum circuits.Communication complexity has a large exponent partly because the rigidity bounds are not tight and because ϵ decreases with n.
RUV protocol.: RUV is an MIP∗ protocol achieving an inverse polynomial gap between completeness and soundness.This provides the protocol’s formal verification guarantee.

GKW protocol. · HPDF protocol. · 4.2 Verification based on self-testing graph states

The GKW and HPDF protocols combine self-testing with VUBQC through verified preparation and computation stages, while McKague’s approach self-tests triangular graph states using multiple non-communicating provers. These protocols achieve inverse polynomial completeness-soundness gaps, with resource requirements determined by their self-testing constructions.

GKW protocol.: GKW reduces the RUV requirement to one universal quantum prover, while the other prover performs only single-qubit measurements as an untrusted measurement device.The protocol uses verified preparation of resource states followed by VUBQC-based verified computation.
GKW protocol.: The GKW protocol remains valid when resource-state imperfections satisfy δ > 1/poly(|C|), with acceptance probabilities changing by at most O(δ).This robustness applies both to states that are uncorrelated with the prover’s private system and, under sufficiently small correlations, to the joint resource-memory system.
GKW protocol.: O(|C|c), c > 2048 is the GKW communication complexity, although the protocol achieves an inverse polynomial completeness-soundness gap as an MIP∗ protocol.The large overhead follows from the need for sufficient verified-preparation tests to make the resource states close to ideal.
HPDF protocol.: The HPDF protocol has the same verified-preparation and verified-computation structure as GKW but uses O(poly(|C|)) non-communicating provers.One prover acts as the verifier’s untrusted measurement device, while the remaining provers receive resource states and perform the computation collectively.
HPDF protocol.: O(|C|4log(|C|)) non-communicating provers provide the tensor-product structure that lets HPDF self-test individual Bell pairs while retaining an inverse polynomial completeness-soundness gap.The computation stage then applies VUBQC, accepting when all trap measurements succeed.
4.2 Verification based on self-testing graph states: McKague’s protocol uses multiple groups of O(|C|) provers, with each group jointly sharing a triangular graph state whose qubits are distributed one per prover.The verifier randomly assigns one group to compute and uses the remaining groups to test the graph state through vertex, triangle, and R(θ) tests.
4.2 Verification based on self-testing graph states: The vertex, triangle, and R(θ) tests jointly self-test the triangular graph state and the provers’ observables, with robustness ϵ = poly(δ, 1/n).The same measurement types are used during testing and computation, making each prover unable to distinguish the two phases and yielding blindness.
4.2 Verification based on self-testing graph states: O(|C|22) is the total number of required provers and communication complexity in McKague’s protocol, which has an inverse polynomial completeness-soundness gap.Each prover must only perform a single-qubit measurement.

4.3 Post hoc verification · FH protocol.

The FH protocol extends post hoc verification to multiple quantum provers and a classical verifier by combining encoded-witness energy testing with non-local-game checks. It is an MIP∗ protocol with an inverse-polynomial completeness–soundness gap, requiring repetition to distinguish acceptance from rejection reliably.

4.3 Post hoc verification: The section introduces two post hoc protocols for the multi-prover setting with a classical verifier, beginning with Fitzsimons and Hajdušek’s FH protocol.This contrasts with the earlier protocol using a single quantum prover and a verifier equipped with a measurement device.
FH protocol: The FH protocol reduces verification to the local Hamiltonian problem, which is QMA-complete and has a witness state polynomial in the input size.The verifier distinguishes whether some state has energy at most a or every state has energy at least b, with b − a ≥ 1/poly(n).
FH protocol: The verifier alternates energy measurements with encoding measurements to test both the witness energy and whether the shared state lies in the code space.Energy tests sample Hamiltonian terms, while encoding tests use code-space checks or a 5-player non-local game.
FH protocol: Ji’s non-local-game techniques make the verifier classical while self-testing the encoded state and enabling delegated measurements of Hamiltonian terms.The Hamiltonian terms can be expressed as linear combinations of k-local XZ-terms, whose constituent Pauli observables the provers measure.
FH protocol: The FH protocol instructs provers to share an encoded Feynman–Kitaev state, prevents communication, and accepts based on either sampled energy or non-local-game outcomes.For a circuit C, the threshold gap is specified as b − a > 1/poly(|C|).
FH protocol: The FH protocol is an MIP∗ protocol achieving an inverse polynomial gap between completeness and soundness.The protocol checks the computation indirectly through the ground-state energy rather than self-testing the operations implementing C.
FH protocol: 2 rounds of interaction are sufficient as described, but inverse-polynomial robustness requires repetition on the order of O(N^16) times.Here N is the number of qubits on which the Hamiltonian acts, and repetition boosts the completeness–soundness distinction.

NV protocol. · 4.4 Summary of entanglement-based protocols

The NV protocol uses a constant-robustness Pauli braiding self-test to estimate the Feynman–Kitaev ground-state energy, achieving a constant completeness-soundness gap. Across entanglement-based protocols, self-testing determines verification structure, prover capabilities, blindness, communication complexity, and overhead.

NV protocol.: The Pauli braiding test self-tests tensor products of Bell pairs and Pauli X and Z observables with constant robustness.For n qubits, it uses O(n)-bit questions and O(1)-bit answers.
NV protocol.: The test combines linearity, anticommutation, and consistency checks to certify observables equivalent to X and Z on a maximally entangled state.The anticommutation test can use games such as CHSH or magic square; with magic square, ω∗(PBT) = 1.
NV protocol.: The NV protocol encodes the Feynman–Kitaev state in Steane’s 7-qubit code and randomly performs Pauli braiding, energy, or energy consistency tests.Steane’s code supports the required X/Z stabilizer structure and symmetry, enabling delegated measurements of X(x) and Z(z).
NV protocol.: Constant precision in the ground-state energy estimate enables the NV protocol to achieve a constant completeness-soundness gap.Parallel repetition O(log(1/ϵ)) times boosts the gap to 1 − ϵ.
4.4 Summary of entanglement-based protocols: Entanglement-based verification protocols either combine non-local games to implement universal computation or self-test a specific resource state.RUV uses the first approach, while other protocols use self-testing to check resource-state preparation.
4.4 Summary of entanglement-based protocols: All protocols require collective BQP computation, but individual provers may not need to be universal quantum computers; post hoc protocols are not blind.Blindness depends on the protocol approach, and some protocols use it while others do not.
4.4 Summary of entanglement-based protocols: Inverse-polynomial self-testing robustness causes an inverse-polynomial completeness-soundness gap, while achieving a constant gap requires polynomial communication complexity.This requirement creates substantial overhead compared with preparing and measuring quantum states directly.

5 Outlook

The outlook extends verification beyond universal quantum computation to sub-universal models, while emphasizing that realistic noise creates major fault-tolerance challenges. Experimental implementations are therefore an important direction for scalable verification.

Sub-universal verification: Verification protocols have been proposed for sub-universal models including one-clean-qubit computation, IQP, Ising spin sampling, and Spekkens’ toy model.These approaches adapt existing verification ideas to restricted computational settings, sometimes using computational assumptions and sometimes requiring limited quantum capabilities from the verifier.
Sub-universal verification: IQP verification includes hypothesis testing, post-hoc certification of Feynman-Kitaev states, and VUBQC adaptations with differing assumptions and verifier requirements.The hypothesis test demonstrates quantum computational advantage but cannot verify sampling from the correct distribution; another scheme removes computational assumptions using a single-qubit preparation device.
Fault tolerance: Noise is a primary obstacle to scalable quantum computers and undermines verification protocols designed for ideal devices.Fault-tolerant techniques use quantum error detection and correction, but realistic devices introduce deviations that honest provers can produce as well.
Fault tolerance: O(p^n) is the probability that n noisy qubits produce the ideal outcomes when each qubit independently matches the ideal result with probability p.Thus, even honest prover behavior can appear incorrect as the number of qubits increases.
Fault tolerance: Fault-tolerant verification protocols have been proposed using topological error-correcting codes and encoded graph states, but they require additional assumptions.Receive-and-measure protocols also face correctness risks when verifier-device errors correlate with the prover’s state preparation.
Experimental outlook: Verification protocols could benchmark quantum-computing experiments, moving beyond non-scalable brute-force classical simulation as devices grow larger.Proof-of-concept experiments have begun demonstrating components of verification protocols on quantum devices.

6 Conclusions

The reviewed protocols offer distinct verification strategies but none yet lets a classical client verify a single quantum server unconditionally. Key open problems concern reducing verifier resources, enforcing physical separation, improving robustness and fault tolerance, and extending protocols to other computation models.

Conclusions: None of the reviewed protocols achieves classical verification of a computation performed by a single quantum server, although each combines tools from several fields.The approaches draw on cryptography, complexity theory, error correction and related areas, with different advantages and disadvantages.
Conclusions: All surveyed approaches provide unconditional verification, while newer protocols use computational assumptions to reduce the verifier’s requirements.Quantum fully homomorphic encryption protocols achieve one communication round but still require the client to have minimal quantum capabilities.
Conclusions: Constant-robustness self-testing is a promising direction because self-testing underlies entanglement-based protocols and strongly affects their communication complexity and overhead.The development of constant-robustness results began with work by Natarajan and Vidick, which formed the basis of one surveyed protocol.
Open problems: Major open problems include adapting interactive proofs from PSPACE to BQP, enforcing space-like separation between entangled provers, and developing fault-tolerant verification under realistic noise.Existing fault-tolerant protocols add assumptions such as uncorrelated verifier and prover noise, while entanglement-based protocols assume provers cannot communicate without physically enforcing it.
Open problems: For a fixed completeness-soundness gap, the best achieved communication complexity is linear, leaving open whether prepare-and-send verification needs only a poly-logarithmic number of prepared single qubits.Other open questions include optimal verifier resources and communication overhead across protocol types.
Open problems: The choice of computational model shapes verification protocols, motivating investigation of additional universal models beyond those already connected to MBQC and post hoc approaches.The paper also identifies broader open problems relevant to quantum information theory.

Basics of quantum mechanics.

Quantum states are unit vectors in finite-dimensional complex Hilbert spaces, with qubits occupying two-dimensional spaces. Quantum mechanics changes states through reversible unitary evolution or measurement, whose outcomes are probabilistic and may be described using projective measurements, POVMs, or observables.

States and registers: Quantum states are unit vectors in finite-dimensional complex Hilbert spaces, while qubits are states in two-dimensional Hilbert spaces.States are written as ket vectors |ψ⟩, with dual bra vectors ⟨ψ|.
State evolution and measurement: Unitary evolution maps |ψ⟩ to U|ψ⟩ and is reversible through the Hermitian conjugate U†.The reversibility relation is UU† = U†U = I.
State evolution and measurement: Projective measurement selects a basis vector at random, producing a classical basis-label outcome with probability |⟨v|ψ⟩|2.The post-measurement state is the selected basis vector.
Generalized measurements: General measurements use operators {Mi}i, with outcome probability p(i) = ⟨ψ|M†iMi|ψ⟩ and post-measurement state Mi|ψ⟩/√p(i).When only outcome probabilities matter, Ei = M†iMi defines a positive-operator-valued measure (POVM).
Observables: Observables are Hermitian operators whose measurement outcomes are eigenvalues, equivalent to projective measurement in their diagonal basis.If the state projects to |i⟩, the outcome is the corresponding eigenvalue λi.
Pure states: Kets represent pure states, which completely describe isolated quantum systems but do not uniquely determine all measurement outcomes.This contrasts with classical pure states, which uniquely determine outcomes of all possible measurements.

Density matrices.

Density matrices represent pure states, probabilistic ensembles, and mixed states, with purity distinguished by the trace of the squared matrix. They also describe measurement probabilities and reduced states obtained through partial trace.

Density matrices.: A pure state |ψ⟩ has density matrix ρ = |ψ⟩⟨ψ|, while an ensemble is represented by a probability-weighted density matrix.The ensemble probabilities satisfy ∑_i p_i = 1.
Density matrices.: Tr(ρ^2) = 1 for pure states, whereas Tr(ρ^2) < 1 for mixed states.The maximally mixed state has density matrix I/d; for one qubit, it is I/2 and represents maximal uncertainty.
Density matrices.: Every non-degenerate projective measurement of the maximally mixed state produces all outcomes with equal probability.The set of density matrices over a Hilbert space H is denoted D(H).
Density matrices.: For a state ρ measured with operators {M_i}_i, the probability of outcome i is given by a trace expression involving the measurement operator and ρ.The supplied passage truncates the displayed expression after p(i) = Tr(M †.
Density matrices.: The partial trace obtains the density matrix of a subsystem within a larger system and is a linear operation.It is defined for density matrices on Hilbert spaces H_1 and H_2.

Purification.

The purification principle states that every mixed state can be represented as the reduced state of a pure state on an enlarged Hilbert space, with different purifications related by a unitary on the added system.

Purification: The partial trace is defined by tracing out one subsystem while retaining the other, together with linearity.Tracing out system 2 produces the reduced state on system 1, and vice versa.
Purification: Every mixed state ρ on H1 can be purified by a pure state |ψ⟩ in H1 ⊗ H2 with dim(H1) = dim(H2).The original mixed state is recovered by tracing out the added subsystem.
Purification: Purification is not unique: any two purifications of ρ are related by a unitary acting only on the added system H2.This unitary freedom is the key structural property behind the purification principle.
Purification: These results are collectively referred to as the purification principle.The principle combines purification of mixed states with unitary equivalence among purifications.

CPTP maps and isometries.

Quantum operations are modeled as completely positive trace-preserving maps, or quantum channels, while isometries are defined as bounded linear maps between Hilbert spaces that preserve the relevant structure.

CPTP maps: Quantum operations map input density matrices to output density matrices and satisfy linearity, complete positivity, and trace preservation.Complete positivity requires positivity under extensions by arbitrary systems, while trace preservation requires Tr(O(ρ)) = Tr(ρ).
CPTP maps: Maps satisfying these three properties are called completely positive trace-preserving (CPTP) maps or quantum channels.Any CPTP map can be equivalently expressed using a set of linear Kraus operators satisfying the stated condition.
Isometries: An isometry is a bounded linear map Φ : H_in → H_out defined using its adjoint Φ† and the identity map on H_in.The discussion restricts attention to purifications in systems of the same dimensions.

Trace distance.

Trace distance generalizes variation distance to compare quantum states, taking the maximum variation distance obtainable over all measurements. It ranges from identical to perfectly distinguishable states and satisfies the triangle inequality.

Trace distance generalizes variation distance for probability distributions to comparisons between quantum states represented by density matrices.
Trace distance is the maximum variation distance between probability distributions produced by measuring the two states with any possible measurement.The maximization covers infinitely many measurement bases and POVMs.
Trace distance ranges from 0 for identical states to 1 for perfectly distinguishable states and satisfies the triangle inequality.

Quantum computation.

Quantum computation is described through basic gates, controlled operations, Clifford circuits, and geometric visualization of single-qubit states. Measurement converts the resulting quantum state into a classical outcome.

Quantum gates: Quantum circuits use Pauli X and Z, Hadamard, T, and controlled-NOT gates, while controlled-U applies U to the target when the control is |1⟩.The first qubit is the control and the second is the target.
Measurement: Measuring the quantum state resulting from a computation produces a classical outcome.
Quantum gates: A Toffoli gate applies X to its target when both control qubits are in the |1⟩ state.
Clifford operations: Clifford operations normalize the n-qubit Pauli group and can be constructed from Pauli gates, H, CNOT, and S = T^2.T and Toffoli gates are not Clifford operations.
Bloch sphere: The Bloch sphere represents every single-qubit state as a point on its surface, including |0⟩, |1⟩, and the eigenstates of Z.

Bloch sphere.

The Bloch sphere represents single-qubit states geometrically, while common single-qubit gates and equatorial states correspond to rotations about specified axes.

Bloch sphere.: Single-qubit operations can be viewed as rotations on the Bloch sphere.Pauli X, Y, and Z gates rotate by π radians around their corresponding axes; the Hadamard gate rotates by π radians around the X + Z axis, and the T gate by π/4 around Z.
Bloch sphere.: Equatorial states 2(|0⟩−e^iφ |1⟩) lie in the XY-plane and arise by rotating |+⟩, |−⟩ around Z by φ radians.For example, |+π/2⟩ and |−π/2⟩ are obtained by π/2 rotations around Z.
Bloch sphere.: Any two diametrically opposed states in the XY-plane form a one-qubit Hilbert-space basis and define a projective measurement.The passage also notes that measurements can be considered in the XY-plane.

Quantum error correction

Quantum error correction enables fault-tolerant computation by encoding noisy quantum operations into larger logical states and correcting the resulting errors. The section illustrates this framework with Kraus operators, encoded subspaces, and the 3-qubit and 5-qubit codes.

Motivation: Noise from interactions with the external environment makes fault-tolerant quantum computation necessary.Quantum error detection and correction protocols provide the mechanism for fault-tolerant computation.
Noise model: A noisy gate acting on a k-qubit state produces E(G |ψ⟩), where E is a CPTP error map.The quantum memory and gate implementation are both subject to noise.
Error correction framework: Correcting every Kraus operator E_j suffices to correct the complete error map E.The error map is represented through a Kraus decomposition, with {E_j}_j as its Kraus operators.
Encoding: Encoding maps a k-qubit state with n − k ancillas into a logical state on n > k qubits within a 2^k-dimensional code subspace of the 2^n-dimensional Hilbert space.The encoding procedure is Enc(|ψ⟩|anc⟩) → |ψ⟩_L.
Example codes: The 3-qubit flip code encodes one qubit into three and detects and corrects single-qubit Pauli X errors, while the 5-qubit code corrects any single-qubit error.For the flip code, |ψ⟩ = a|0⟩ + b|1⟩ maps to |ψ⟩_L = a|000⟩ + b|111⟩; the 5-qubit code is the smallest code correcting arbitrary single-qubit errors.