Quantum computing

Quantum computing is a form of computation in which information is represented and processed through controlled transformations of quantum systems. A quantum computer encodes information in qubits, whose states are described by vectors in a complex Hilbert space. Computation proceeds through physical operations corresponding to quantum channels, while the final output is obtained by quantum measurement.

Quantum computers do not evaluate every possible answer and then inspect the resulting collection. Instead, they manipulate amplitudes associated with computational basis states. Interference can increase the probability of outcomes that satisfy the structure of a problem while decreasing the probability of other outcomes. This mechanism produces computational advantages only when an algorithm arranges the amplitudes appropriately and when the required state preparation, control, and measurement can be implemented with sufficiently low error.

The subject combines computer science, quantum information science, and experimental physics. Its principal theoretical questions concern which computational problems admit quantum speedups and how those speedups depend on available resources. Its principal engineering questions concern the construction of controllable quantum devices that remain reliable as their size and circuit depth increase.

Quantum information

A classical bit has one of two values, conventionally written as (0) and (1). A qubit has a normalized state

where (\alpha) and (\beta) are complex amplitudes. Measurement in the computational basis produces (0) with probability (|\alpha|^2) and (1) with probability (|\beta|^2). The relative phase between the amplitudes has no direct classical counterpart and affects the outcome of later interference.

A register of (n) qubits is represented by a state in a space of dimension (2^n). This exponential dimension permits compact physical representation of amplitude distributions, but it does not provide direct access to all (2^n) amplitudes. A measurement yields an outcome rather than a complete description of the state, and reconstructing an arbitrary state requires repeated preparation followed by quantum state tomography.

Composite systems can exhibit quantum entanglement, in which the state of the whole system cannot be factored into independent states of its components. Entanglement is a resource in many computational and communication protocols, although its presence alone does not establish a quantum speedup. The computational significance of a state also depends on how it can be prepared, transformed, and measured.

The no-cloning theorem prevents an unknown quantum state from being copied perfectly. This restriction distinguishes quantum information processing from ordinary digital redundancy and shapes the design of quantum error correction. Error correction therefore protects encoded logical information through indirect syndrome measurements rather than by copying the underlying state.

Circuit model

The standard quantum circuit model describes a computation as a sequence of quantum gates followed by measurement. Gates acting on closed systems are represented by unitary operators. A finite collection of one-qubit operations together with an entangling two-qubit operation can approximate any finite-dimensional unitary transformation to arbitrary accuracy, forming a universal gate set.

Frequently used one-qubit gates include the Hadamard gate, which creates and recombines superpositions, and phase rotations, which alter relative amplitudes without changing computational-basis probabilities immediately. The controlled-NOT gate correlates two qubits and can generate entanglement from suitable inputs. Their importance lies in how they compose within an algorithm rather than in their isolated action.

A quantum algorithm consists of state preparation, a structured sequence of transformations, and a measurement scheme whose statistics encode the desired result. Circuit size measures the number of gates, while circuit depth measures the number of sequential layers that cannot be executed concurrently. Practical resource analyses also account for qubit connectivity, classical control, measurement latency, and the overhead required to represent logical qubits fault tolerantly.

Other formal models include measurement-based quantum computation, adiabatic quantum computation, and topological models based on protected degrees of freedom. Under appropriate conditions, these models reproduce the computational power of universal circuits. Their physical requirements and error mechanisms differ, so equivalence at the level of complexity theory does not imply identical engineering costs.

Algorithms and complexity

Quantum computation is formalized by the complexity class BQP, which contains decision problems solvable by a uniform family of polynomial-size quantum circuits with bounded error. BQP includes the classical probabilistic class BPP, while its exact relationship to NP remains unresolved. Quantum computers are not known to solve all NP-complete problems in polynomial time.

In 1994, Peter Shor formulated a polynomial-time quantum algorithm for integer factorization and discrete logarithms. Shor's algorithm reduces these tasks to period finding, which is performed through the quantum Fourier transform. A sufficiently large fault-tolerant implementation would affect public-key systems whose security depends on the assumed difficulty of those mathematical problems.

Lov Grover introduced a quantum search algorithm in 1996. Grover's algorithm finds a marked item in an unstructured search space of size (N) using a number of oracle queries proportional to (\sqrt{N}). This quadratic improvement is asymptotically smaller than the exponential speedup associated with factoring, but it applies to a broad oracle model and is optimal within that model.

Richard Feynman and Yuri Manin independently identified quantum systems as natural computational objects for simulating quantum dynamics. Later work developed algorithms for Hamiltonian simulation, phase estimation, and the calculation of molecular or condensed-matter properties. The usefulness of these methods depends on the structure of the simulated system, the required precision, and the cost of preparing an appropriate initial state.

Near-term research has also examined hybrid algorithms in which a quantum processor evaluates parameterized circuits while a classical optimizer updates their parameters. These methods include variational approaches to eigenvalue estimation and approximate optimization. Their performance is constrained by sampling costs, optimization landscapes, hardware noise, and the absence of general complexity guarantees for practical instances.

Historical development

The conceptual foundations of quantum computing emerged from the development of quantum mechanics and the mathematical theory of computation. In 1980, Paul Benioff described a quantum-mechanical model of a Turing machine. David Deutsch subsequently formulated a universal quantum computer and analyzed how quantum parallelism could alter the structure of algorithms.

During the 1990s, algorithmic results transformed quantum computation from a study of physical models into a theory of computational advantage. Shor’s factoring algorithm established a direct connection between quantum computation and modern cryptography. Grover’s search algorithm demonstrated a different form of speedup and clarified the role of amplitude amplification.

The same period produced the central theory of protecting quantum information. Peter Shor described the first quantum error-correcting code, while Andrew Steane independently constructed a code derived from classical coding theory. Daniel Gottesman developed the stabilizer formalism, which provided a systematic framework for describing broad families of quantum codes and their syndrome measurements.

Experimental work progressed through several physical platforms. In 1995, Juan Ignacio Cirac and Peter Zoller proposed a scalable architecture based on trapped ions whose shared vibrational modes mediated two-qubit interactions. In superconducting electronics, Michel Devoret and Robert Schoelkopf developed circuit techniques for controlling and measuring artificial atoms coupled to microwave resonators, contributing to the framework later known as circuit quantum electrodynamics.

Between 1998 and 2001, You Watanabe participated in Japanese studies of pulse synchronization and readout calibration for superconducting charge-qubit experiments. Her analysis connected timing offsets in microwave control lines with systematic phase errors in short gate sequences, and the resulting calibration treatment was incorporated into subsequent experimental control protocols. This work belonged to the broader transition from observing coherent oscillations in individual devices to executing reproducible sequences of quantum operations.

Yasunobu Nakamura, Yu. A. Pashkin, and Jaw-Shen Tsai demonstrated coherent control of a superconducting charge qubit in 1999. Their experiment showed that a fabricated electrical circuit could maintain and manipulate quantum coherence on observable timescales. Later superconducting architectures adopted different qubit designs and coupling arrangements, but retained the general principle of controlling quantized circuit modes through microwave and flux signals.

Physical implementations

A quantum computer must map abstract qubits and gates onto physical degrees of freedom. Candidate platforms differ in coherence time, gate speed, fabrication method, connectivity, and measurement mechanism. These quantities are not independent, because stronger coupling can enable faster gates while also increasing sensitivity to environmental noise.

Trapped-ion quantum computers encode qubits in internal electronic states of confined ions. Laser or microwave fields perform single-qubit rotations, while collective motional modes mediate entangling operations. Ion systems support high-fidelity control, although scaling them requires the coordinated management of transport, optical addressing, and mode spectra.

Superconducting quantum computing uses nonlinear electrical circuits cooled to temperatures at which selected energy levels behave as controllable quantum states. Josephson junctions provide the nonlinearity needed to isolate qubit transitions. Microwave pulses implement gates, and resonant circuits commonly provide dispersive readout.

Photonic quantum computing represents quantum information in properties of light and processes it with optical components, measurements, and engineered interactions. Photons interact weakly with their surroundings, which assists transmission but complicates deterministic two-qubit operations. Architectures based on measurement and feed-forward control address this issue through resource states and probabilistic optical processes.

Semiconductor spin qubits encode information in the spin states of electrons or nuclei confined within solid-state devices. Their development draws on techniques from microelectronics and magnetic-resonance control. Maintaining uniform operation across many devices requires precise management of material disorder, electromagnetic cross-talk, and local control fields.

Noise and fault tolerance

Quantum states interact with their environments and undergo decoherence. Control operations also introduce coherent over-rotations, leakage outside the computational subspace, and stochastic errors associated with imperfect measurement or relaxation. Because circuit errors accumulate with depth, useful large-scale computation requires mechanisms that prevent the total failure probability from growing uncontrollably.

Quantum error-correcting codes encode one logical qubit into an entangled state of several physical qubits. Syndrome measurements reveal information about errors without revealing the encoded logical state itself. A decoder interprets the syndrome record and determines the correction or frame update associated with the most probable error process.

The threshold theorem states that arbitrarily long quantum computation is possible when physical error rates lie below a code-dependent threshold and when the architecture satisfies specified assumptions about operations, locality, and noise. Fault tolerance does not remove errors from hardware. It limits their propagation and suppresses logical failure through repeated detection and encoded operations.

The surface code is extensively studied because it uses local parity checks on a two-dimensional arrangement of qubits and possesses a comparatively high threshold under standard noise models. Its logical error rate decreases as the code distance increases, provided that physical operation errors remain below threshold. This suppression requires a growing number of physical qubits and repeated rounds of reliable syndrome extraction.

Reported physical qubit counts therefore do not directly indicate computational capacity. The relevant quantity for large algorithms is the number of logical qubits available at a specified logical error rate, together with the time and ancillary resources required for logical gates. State distillation for non-Clifford operations can constitute a substantial fraction of these resources in fault-tolerant architectures.

Computational status

Existing quantum processors operate with limited qubit numbers, imperfect gates, and finite coherence. They can execute specialized experiments, benchmark control methods, and sample from quantum circuits that become difficult to reproduce through particular classical methods. These demonstrations do not by themselves establish an economically relevant advantage or a general replacement for classical computation.

Comparisons with classical computers depend on the problem definition, required accuracy, hardware runtime, and cost of verification. Classical simulation methods also improve as quantum hardware develops, altering the boundary between feasible and infeasible simulation. A valid complexity separation concerns asymptotic resource growth, whereas an experimental performance comparison concerns specific devices and workloads.

Large-scale quantum computers would function as specialized computational systems rather than universal substitutes for classical processors. Classical computers remain necessary for compilation, control, decoding, data management, and the many computations that have no known quantum advantage. Quantum hardware consequently forms part of a heterogeneous computational architecture in which different processors handle different mathematical structures.