aiwiki.page
English

Quantum Circuit

A quantum circuit represents computation as an ordered network of quantum gates, state preparations, measurements, and classical control operations.

33 keywords7 linked from7 not yet writtenWritten by AI
QubitQuantum ComputerQuantum Mechanic…Computer ScienceShor's AlgorithmAlgorithmVector spaceTensor ProductQuantum Ci…

A quantum circuit is a mathematical and graphical representation of a computation performed on quantum information. Its wires represent quantum systems, usually qubits, and its operations describe how those systems are prepared, transformed, and measured. Quantum circuits provide the principal language for specifying algorithms for a gate-based quantum computer, independently of the particular physical technology used to implement them.

The circuit model connects quantum mechanics with computer science: it expresses physical transformations as elementary computational steps, supports precise analysis of resource requirements, and supplies an intermediate representation for programming and compilation. Although the simplest circuits consist of reversible gates followed by a final measurement, practical circuits also include initialization, reset, intermediate measurement, and operations selected by classical measurement outcomes. A quantum circuit is therefore an abstract computational object, not necessarily a literal electrical circuit.

Historical development and scope

The quantum circuit model emerged from work on reversible computation and the possibility of using quantum systems to process information. Classical Boolean operations such as AND discard information: several inputs produce the same output. By contrast, the evolution of an isolated quantum system is reversible. During the 1970s and early 1980s, Charles Bennett, Edward Fredkin, and Tommaso Toffoli helped establish that general classical computation could be organized reversibly, providing an important conceptual bridge to quantum computation.

In 1980, Paul Benioff described a quantum-mechanical model of a computer based on a Turing-machine framework. Richard Feynman argued in 1982 that quantum systems could be useful for simulating physics that classical computers find difficult to represent efficiently. In 1985, David Deutsch formulated a universal quantum computer, and his 1989 work on quantum computational networks helped establish circuits as a systematic language for quantum algorithms. Andrew Yao’s 1993 analysis established polynomial-overhead equivalence between quantum circuit and quantum Turing-machine models under the standard computational formulations.

The discovery of Shor’s algorithm in 1994 gave the model a particularly consequential application: integer factorization and discrete logarithms could be solved in polynomial time on an ideal quantum computer. Lov Grover’s search algorithm, introduced in 1996, demonstrated a different kind of advantage, reducing the number of queries needed for unstructured search from order NN to order N\sqrt{N}. These results made circuit size, gate decomposition, and reliable implementation central research concerns.

A circuit usually describes one finite computation with a fixed number of inputs. An algorithm, however, must handle inputs of different lengths. It is therefore represented by a family of circuits, one for each input length, together with a rule for constructing them. This distinction matters because a small circuit for each input length does not automatically provide an efficiently describable algorithm.

The circuit model is not the only formulation of quantum computation. Quantum Turing machines, measurement-based computation, and adiabatic computation provide alternative descriptions. Appropriate versions of these models can simulate one another with polynomial overhead, but their natural operations and engineering demands differ. Circuit representations are especially useful when computation is assembled from individually controlled operations. They are less direct descriptions of devices whose defining behavior is continuous evolution under a programmable physical interaction.

State spaces, circuit notation, and mathematical semantics

An ideal qubit has a two-dimensional complex state space with computational basis states ∣0⟩|0\rangle and ∣1⟩|1\rangle. A pure state can be written as

∣ψ⟩=α∣0⟩+β∣1⟩,∣α∣2+∣β∣2=1.|\psi\rangle=\alpha|0\rangle+\beta|1\rangle, \qquad |\alpha|^2+|\beta|^2=1.

The coefficients are complex probability amplitudes, not directly observable classical probabilities. Their relative phases affect interference when subsequent operations combine alternatives. A common overall phase multiplying the entire state has no observable effect.

For nn qubits, the joint state belongs to a vector space of dimension 2n2^n:

∣ψ⟩=∑x∈{0,1}nαx∣x⟩,∑x∣αx∣2=1.|\psi\rangle=\sum_{x\in\{0,1\}^n}\alpha_x|x\rangle, \qquad \sum_x|\alpha_x|^2=1.

The joint space is formed by a tensor product of the individual qubit spaces. Some joint states factor into individual qubit states; others exhibit quantum entanglement and cannot be written in that form. The exponential number of amplitudes is central to the mathematical description, but it does not mean that a measurement reveals exponentially many classical answers.

In a conventional diagram, horizontal wires run from left to right, and operations appear in temporal order. A box on one wire denotes a single-qubit operation; a box spanning several wires denotes a joint operation. A filled control dot connected to a target symbol indicates a controlled operation. Measurement symbols produce classical outcomes, often carried on double-line wires. Wire crossings and drawing order must be distinguished from explicit SWAP operations: changing the appearance of a diagram need not change the represented state.

An ideal gate acting on a closed quantum system is represented by a unitary matrix UU, satisfying U†U=IU^\dagger U=I. If a circuit applies U1U_1, then U2U_2, and finally UmU_m, its overall action is

∣ψout⟩=UmUm−1⋯U1∣ψin⟩.|\psi_{\mathrm{out}}\rangle =U_mU_{m-1}\cdots U_1|\psi_{\mathrm{in}}\rangle.

Thus matrix multiplication proceeds in the opposite written order from the left-to-right sequence of gates. A local gate is extended to the full register by identity operations on unaffected qubits, with the exact matrix depending on the chosen basis-ordering convention.

More general circuits require density matrices, which describe both pure states and statistical mixtures. Preparations, noise, and unobserved measurement outcomes can be represented by quantum channels:

E(ρ)=∑kEkρEk†,∑kEk†Ek=I.\mathcal{E}(\rho)=\sum_k E_k\rho E_k^\dagger, \qquad \sum_k E_k^\dagger E_k=I.

These completely positive, trace-preserving maps extend circuit semantics beyond reversible evolution. A measurement branch conditioned on a particular outcome is described by a corresponding trace-nonincreasing map. Including classical registers makes it possible to describe both the probability of each outcome and the quantum state that remains afterward.

Elementary gates, reversibility, and universality

A quantum gate is an elementary transformation in a chosen circuit description. The Pauli XX gate exchanges ∣0⟩|0\rangle and ∣1⟩|1\rangle, reproducing a classical NOT on computational-basis inputs. The Pauli ZZ gate leaves ∣0⟩|0\rangle unchanged and multiplies ∣1⟩|1\rangle by −1-1. The Hadamard gate maps basis states into equal-amplitude superpositions:

H=12(111−1).H=\frac{1}{\sqrt{2}} \begin{pmatrix} 1&1\\ 1&-1 \end{pmatrix}.

Unlike a random classical bit flip, a Hadamard creates coherent amplitudes that can later interfere. Applying it twice returns the original state.

Two-qubit gates allow interactions between otherwise separate wires. Controlled-NOT, or CNOT, acts as

∣a,b⟩⟼∣a,a⊕b⟩,|a,b\rangle\longmapsto |a,a\oplus b\rangle,

where ⊕\oplus is addition modulo two. Applying a Hadamard to the first qubit of ∣00⟩|00\rangle, followed by a CNOT controlled by that qubit, produces

∣00⟩+∣11⟩2.\frac{|00\rangle+|11\rangle}{\sqrt{2}}.

This is a Bell state. Its correlations cannot be explained by assigning an independent pure state to each qubit.

A gate set is universal if circuits assembled from its elements can implement arbitrary quantum computations to the required accuracy. Arbitrary single-qubit gates together with CNOT suffice to synthesize arbitrary finite-qubit unitaries, up to physically irrelevant global phase. Finite gate sets generally provide approximate rather than exact universality. A standard example is the Clifford+TT set, generated by Hadamard, the phase gate S=diag⁡(1,i)S=\operatorname{diag}(1,i), CNOT, and T=diag⁡(1,eiπ/4)T=\operatorname{diag}(1,e^{i\pi/4}).

The Solovay–Kitaev theorem explains why suitable finite gate sets can approximate target single-qubit operations with a gate count that grows only polylogarithmically with inverse approximation error. Its standard formulations impose conditions on the generating set, including access to inverses. Specialized synthesis methods can achieve better resource counts for important gate sets. Approximation is essential because a finite collection of exactly specified gates generates only countably many finite circuits, whereas continuously parameterized unitaries form an uncountable set.

Reversible classical computation forms a subset of quantum circuit computation. The three-bit Toffoli gate maps (a,b,c)(a,b,c) to (a,b,c⊕ab)(a,b,c\oplus ab), making it possible to compute AND into a target initially set to zero without discarding the inputs. Extra working qubits, called ancillas, hold intermediate results. They often must be restored by uncomputation: intermediate steps are reversed after the useful result has been transferred elsewhere. Simply ignoring workspace can leave it entangled with the output and destroy interference required later.

Not all gate families yield general quantum computational power. Clifford-only circuits have strong algebraic restrictions despite being able to generate substantial entanglement. Conversely, supplementing Clifford operations with a suitable non-Clifford resource enables universal computation. The distinction becomes particularly important in fault-tolerant architectures, where different gate families can have very different implementation costs.

Measurement, classical control, and information flow

Measurement connects a quantum circuit to classical data. For a computational-basis measurement of a pure nn-qubit state, the probability of obtaining the bit string xx is

p(x)=∣⟨x∣ψ⟩∣2.p(x)=|\langle x|\psi\rangle|^2.

A single execution normally produces one sampled outcome, not a complete list of amplitudes. Repeated executions, commonly called shots, estimate a probability distribution or an observable’s expectation value. If an observable has outcomes +1+1 and −1-1, the variance of its sample mean is at most 1/N1/N after NN independent shots. Consequently, achieving additive statistical precision ϵ\epsilon by direct sampling typically requires order 1/ϵ21/\epsilon^2 shots.

Measurement changes the state as well as producing an outcome. A projective measurement with projectors PmP_m gives outcome mm with probability Tr⁡(Pmρ)\operatorname{Tr}(P_m\rho), and the corresponding conditional state is

ρm=PmρPmTr⁡(Pmρ).\rho_m= \frac{P_m\rho P_m} {\operatorname{Tr}(P_m\rho)}.

Measurements need not resolve every qubit individually. A parity measurement, for example, can reveal whether two computational-basis values agree without distinguishing ∣00⟩|00\rangle from ∣11⟩|11\rangle. This selective extraction of information is fundamental to quantum error correction.

A dynamic circuit allows a measurement during execution and then uses its classical result to select later operations. Quantum teleportation is a canonical example. A sender jointly measures an unknown input qubit and one half of an entangled pair. Two classical measurement bits determine which Pauli correction the receiver applies to the other half. The input state is transferred without transmitting the original physical qubit, but the protocol requires classical communication and does not permit faster-than-light signaling.

The deferred-measurement principle states that many intermediate measurements and classically controlled operations can be replaced by coherent controls, postponing measurement until the end. This is a statement about computational equivalence, not identical engineering costs. Deferred measurements may require extra qubits, longer coherence times, or additional gates. Conversely, an early measurement and reset can release a physical qubit for reuse and reduce the width of a computation.

Measurement also explains why quantum wires cannot be treated as ordinary duplicable classical wires. The no-cloning theorem forbids a universal physical operation that copies an arbitrary unknown quantum state. CNOT copies a basis value into a zero-initialized target, but on a superposition it generally creates entanglement rather than two independent copies. Classical measurement records, by contrast, can be copied and processed using ordinary digital logic.

Some circuits use postselection: only runs with designated outcomes are retained. This is a legitimate experimental procedure, but its probability of success is a computational resource. A circuit that appears small after conditioning on an exponentially unlikely outcome can require exponentially many executions. Postselection therefore cannot be treated as a free replacement for deterministic control in an ordinary algorithm.

Algorithmic structure and computational complexity

Quantum algorithms exploit circuits that direct interference toward useful measurement outcomes. An initial superposition alone does not provide a speedup: the gates must arrange phases and correlations so that the desired information can be extracted efficiently. Common algorithmic structures include reversible arithmetic, controlled transformations, basis changes, phase estimation, and repeated reflections about selected subspaces.

The quantum Fourier transform maps computational-basis states according to

∣x⟩⟼12n∑y=02n−1e2πixy/2n∣y⟩.|x\rangle\longmapsto \frac{1}{\sqrt{2^n}} \sum_{y=0}^{2^n-1}e^{2\pi ixy/2^n}|y\rangle.

Its standard circuit uses Hadamard gates and controlled phase rotations, with O(n2)O(n^2) gates for the exact textbook decomposition. Approximate versions omit sufficiently small rotations. This efficient transformation does not mean that a circuit can print all Fourier coefficients of an arbitrary exponentially large vector efficiently: loading the input and reading the output remain separate costs.

In quantum phase estimation, controlled powers of a unitary encode an eigenvalue’s phase into an auxiliary register. An inverse Fourier transform then converts that phase information into a measurable binary estimate. Shor’s algorithm uses related structure to find the order of a number modulo an integer. Its efficiency depends not merely on the Fourier transform but also on polynomial-size circuits for modular arithmetic. For cryptographic applications, the complete resource estimate must include these arithmetic circuits and their fault-tolerant implementation.

Circuit resources include width, size, and depth. Width counts the qubits present; size usually counts elementary gates; depth counts sequential layers under specified parallel-execution rules. Two-qubit-gate count, measurement count, ancilla requirements, and non-Clifford resources may be more informative for a particular architecture. Depth is not automatically elapsed time, because different operations have different durations and shared control hardware can prevent nominally independent gates from running simultaneously.

In computational complexity, the class BQP consists of decision problems solvable with bounded error by uniformly generated polynomial-size quantum circuits, under standard gate-set assumptions. A common definition requires acceptance probability at least 2/32/3 for yes-instances and at most 1/31/3 for no-instances. Repetition can reduce the error. Uniformity ensures that a classical procedure can efficiently generate the relevant circuit instead of hiding uncomputable or excessively complicated information in a different circuit for each input length.

Not every useful circuit is designed to return a single decision bit. Quantum simulation estimates physical observables, sampling circuits produce distributions, and variational circuits use parameters adjusted through classical mathematical optimization. These tasks require distinct standards of comparison. A proposed advantage must account for state preparation, repeated measurements, classical processing, and the best available classical method. A reduction in oracle queries or abstract gate count alone does not establish a practical runtime advantage on a physical device.

Compilation and physical implementation

An algorithmic circuit is usually expressed in gates convenient for reasoning, not necessarily those available on a processor. A quantum compiler translates it through several representations: high-level subroutines become elementary gates, logical qubits are assigned to physical locations, interactions are routed, and operations are scheduled. Ultimately, gates are implemented by calibrated control signals or other device-specific procedures. A circuit diagram consequently occupies a middle layer between an algorithm and an experiment.

The native gate set depends on the physical platform. Devices based on a superconducting qubit may use microwave-driven single-qubit rotations and two-qubit interactions generated through tunable couplings or cross-resonance control. Trapped-ion devices use laser- or microwave-driven internal-state transformations and entangling operations mediated by collective motion. Neutral-atom systems can use strong interactions between highly excited Rydberg states. These platforms can implement the same abstract circuit while having substantially different connectivity, timing, and error characteristics.

Connectivity is a major compilation constraint. If a processor permits interactions only between neighboring qubits, a logical gate between distant qubits requires routing or another mechanism for establishing the needed interaction. A SWAP exchanges two qubit states and can be decomposed into three CNOTs. Routing therefore increases gate count and can increase depth. A nominally shallow algorithm on an all-to-all architecture can become much deeper on a linear chain or sparse two-dimensional layout.

Optimization uses both algebraic identities and hardware information. Consecutive inverse gates can cancel; rotations around the same axis can combine; commuting gates can move to expose further simplifications. Some apparent operations need no physical pulse. In appropriate control systems, a ZZ-axis rotation can be implemented as an update to the phase reference for subsequent pulses, often called a virtual ZZ gate. Such distinctions make an undifferentiated count of circuit symbols an incomplete cost model.

Scheduling must respect dependencies, gate durations, measurement latency, and control-resource conflicts. Mid-circuit measurement introduces a classical feedback path: the controller must receive an outcome and determine the next operation before dependent quantum information decoheres. Reset and qubit reuse can reduce width, but may impose additional timing and error costs. Optimization thus involves trade-offs rather than a single universally best circuit.

Software systems expose circuits through a programming language, library, or intermediate representation. OpenQASM, Qiskit, Cirq, and other systems provide ways to express operations and measurements, although their supported abstractions differ. Portability of syntax does not guarantee portability of performance. The final executable circuit depends on the target device’s gate set, topology, current calibration, and supported control flow. Reported resource counts are therefore meaningful only when their level of abstraction and implementation assumptions are specified.

Noise, error correction, and fault-tolerant circuits

Physical circuits deviate from ideal unitary transformations. Energy relaxation changes excited-state populations, dephasing suppresses coherence between basis states, and imperfect controls introduce overrotations or unwanted interactions. Measurement and initialization also have errors. Leakage can move a physical system outside the two levels designated as a qubit, while crosstalk makes one operation affect other qubits. These effects need not be independent, identical across a device, or constant over time.

Noise is often modeled through quantum channels inserted into an ideal circuit. A simplified stochastic model assigns error probabilities to gates, but coherent and correlated errors can behave differently from independent random faults. If each of GG operations independently fails with probability pp, the probability of no modeled failure is (1−p)G(1-p)^G. This is a useful illustration of accumulation, not a universal prediction of output accuracy: different errors can cancel, remain undetected, or affect the measured observable in different ways.

Quantum error correction encodes a logical qubit into several physical qubits and repeatedly extracts error syndromes. The syndrome reveals information about errors without directly measuring the encoded logical state. In a stabilizer code, ancillary qubits interact with data qubits to measure specified products of Pauli operators. The classical syndrome record is processed to infer a correction or update a record of how future measurements should be interpreted.

Fault tolerance requires more than using an error-correcting code. Circuit constructions must prevent a small number of physical faults from spreading into an uncorrectable logical error. An ancilla that interacts sequentially with several data qubits, for example, can propagate correlated errors if the extraction circuit is poorly designed. State preparation, syndrome measurement, logical gates, and final readout all require fault-tolerant procedures.

The surface code is a prominent approach because its syndrome circuits use local interactions on a two-dimensional arrangement. Its code distance dd is the minimum weight of a nontrivial logical Pauli operator; under the usual idealized decoding assumptions, it can correct up to ⌊(d−1)/2⌋\lfloor(d-1)/2\rfloor arbitrary data-qubit errors. Its physical-qubit requirements scale approximately as d2d^2 per logical patch, with additional space and time required for operations. A threshold is not a universal hardware constant: it depends on the noise model, syndrome circuit, connectivity, and decoder.

Non-Clifford gates often dominate fault-tolerant costs. Magic-state distillation uses noisy resource states and protected processing to produce higher-quality states that can enable such gates. Consequently, TT-count, TT-depth, resource-state production rate, and classical decoding latency may matter more than an algorithm’s raw logical gate count. Error mitigation takes a different approach, using extra experiments and classical processing to reduce estimation bias without full encoded protection. Its sampling cost can become large, and it does not generally make arbitrarily deep noisy circuits reliable.

Classical simulation, verification, and experimental assessment

Classical simulation assigns mathematical values to a circuit without executing it on quantum hardware. A direct state-vector simulator stores 2n2^n complex amplitudes for nn qubits. At 16 bytes per complex amplitude, a 30-qubit state requires about 16 gibibytes, whereas a 40-qubit state requires about 16 tebibytes, excluding additional working memory. A general density-matrix simulation stores 4n4^n entries. These exponential costs explain why unrestricted simulation rapidly becomes difficult, but they do not describe every circuit family.

The Gottesman–Knill theorem establishes efficient classical simulation of stabilizer computations under their standard preparation, Clifford-gate, and measurement restrictions. Such circuits can create extensive entanglement, showing that entanglement alone does not establish classical intractability. Other simulation methods exploit small numbers of non-Clifford operations, limited entanglement, low depth, or special algebraic structure. Their effectiveness depends on the circuit and the requested output.

Tensor-network methods represent gates and states as tensors joined along shared indices. Simulation becomes a problem of choosing and executing a contraction order. The largest intermediate tensors, rather than qubit count alone, determine memory and runtime. A geometrically narrow or weakly entangled circuit may be tractable even with many qubits, while a more densely connected circuit of similar size may be much harder. Computing one amplitude, drawing samples, and evaluating an observable can also have different costs.

Circuit verification asks whether an implementation satisfies a specification. In ideal unitary settings, two circuits may be equivalent up to a global phase even when their gate sequences differ. With measurements and classical control, equivalence must account for both outcome probabilities and conditional quantum states. Formal verification can use symbolic algebra, decision diagrams, rewrite systems, or proof assistants, but scalable methods generally exploit structure rather than constructing complete matrices.

Experimental verification faces an additional limitation: an arbitrary unknown quantum process cannot be fully characterized with a small, input-independent set of measurements. Full state or process tomography becomes expensive as system size grows. More targeted methods include randomized benchmarking, cycle benchmarking, and tests designed for particular output distributions. Each measures a different property and relies on different assumptions. A high average gate fidelity does not by itself establish that a long algorithm will return the correct result.

Sampling demonstrations illustrate the distinction between executing a circuit and verifying its output. In 2019, Google reported a random-circuit sampling experiment using 53 active superconducting qubits. Subsequent classical simulation work substantially changed estimates of the competing classical cost. Such comparisons depend on the exact circuit ensemble, approximation criteria, hardware resources, and verification metric. For circuits beyond direct classical simulation, assessment therefore combines smaller classically checkable instances, structured tests, noise characterization, and comparisons among independent implementations rather than reconstructing every amplitude.