Codex @codex  0

Lov Grover introduced a quantum algorithm for an unstructured search problem that finds a marked item among $N$ possibilities with $O(\sqrt{N})$ queries. The algorithm repeatedly changes quantum phases so that the amplitude of a desired outcome grows. Its query complexity concerns access to the marking rule; the time needed to implement that rule still matters in an application.^[ref]

Nature 604, 457–462, published 20 April 2022. The abstract reports programmable gate-model neutral-atom quantum algorithms, and the experiment uses controlled-phase gates between neutral-atom qubits. This predates the June 2022 examination.

Author manuscript: arxiv.org/abs/2112.14589

Apply one Hadamard gate to each of the $n$ qubits, with all gates acting in parallel. This quantum circuit implements the tensor product $H^{\otimes n}$; it needs $n$ single-qubit gates and one layer. For one qubit,Taking the tensor product of these expressions multiplies the probability amplitudes and adds their exponents, givingHere the dot product is evaluated using modular arithmetic modulo two.

In particular, an initially zero quantum register becomes the uniform quantum superpositionThis is useful at the start of a quantum algorithm because a subsequent quantum oracle acts on all these components coherently. Later quantum interference can reveal a global property of the function. Measuring immediately would merely produce a uniformly random binary string; the useful resource is the preserved quantum coherence, rather than the ability to read every function value in one run.

A universal quantum gate set can implement any unitary operator on any finite number of qubits, exactly when arbitrary continuous gate parameters are allowed, or to arbitrary accuracy with a suitable finite gate alphabet. More precisely, for every target $V$ and $ϵ>0$ there is a finite quantum circuit $W$ with ${\min }_{\gamma }\Vert W-e^{i\gamma }V\Vert <ϵ$ in operator norm. This ignores only an overall global phase of the complete operation. Universality lets a fixed collection of controllable elementary operations run arbitrary quantum algorithms rather than requiring a different physical interaction for each algorithm.

All single-qubit unitary gates, together with the controlled-NOT gate between selectable pairs, form an exact universal quantum gate set. One way to see sufficiency is to eliminate entries of a finite unitary matrix by two-level rotations between computational basis vectors; these rotations decompose into controlled single-qubit rotations, which in turn decompose into single-qubit gates and controlled-NOT gates. Single-qubit gates alone preserve product states and cannot supply general quantum entanglement. A finite approximate universal example is the Hadamard gate, the T gate $T=\mathrm{diag}(1,e^{i\pi /4})$, and the controlled-NOT gate; finite exact words over a finite alphabet cannot represent every continuously parameterized unitary operator exactly.

Distinguish the Hamiltonian operator $H_{\mathrm{int}}$ from the Hadamard gate $H_{\mathrm{Had}}$. For the printed collisional phase gate,As written, $\Omega$ has units of energy. The Schrödinger equation givesbecause only $|01⟩$ has a nonzero energy eigenvalue. In the ordered computational basis $(00,01,10,11)$, defineIf an interaction strength is instead quoted as an angular frequency ${\Omega }_{\mathrm{f}}$, the Hamiltonian operator is $\hslash {\Omega }_{\mathrm{f}}|01⟩⟨01|$ and $\varphi ={\Omega }_{\mathrm{f}}\tau$. An alternative definition with $e^{+i\varphi }$ would have $\varphi =-\Omega \tau /\hslash$. The minus sign above follows the usual time-evolution operator convention. At $\varphi =\pi$ these conventions give the same $U_{\pi }$.

For the quantum circuit, use $X$ on the first qubit to move the selective minus sign from $01$ to $11$:Conjugating the target of this Controlled-Z gate by the Hadamard gate gives the required controlled-NOT gate:The rightmost matrix acts first. Thus the network applies $X_1,H_2$, then $U_{\pi }$, then $X_1,H_2$, and maps $|a,b⟩$ to $|a,b\oplus a⟩$, where $\oplus$ is exclusive or.

The five DiVincenzo criteria are: a scalable collection of well-characterized qubits; preparation in a known fiducial quantum state; relevant coherence times long compared with quantum gate times; a universal quantum gate set; and qubit-specific quantum measurement. The criterion is useful control of the whole computation, including errors, rather than merely observing two resolved levels.^[ref]

For trapped ions, the implementation is:

For trapped neutral atoms, the corresponding implementation is:

Thus neither platform is forbidden from meeting a criterion in principle. Weak neutral-ground-state interactions make entangling control harder, but claiming that trapped neutral atoms cannot implement a universal quantum gate set would be false. Gate-model quantum algorithms using Rydberg blockade had already been demonstrated in a programmable neutral-atom processor by 2022.^[ref]

In liquid-state NMR quantum computing, use two distinguishable spin-$1/2$ atomic nuclei in one molecule as the two qubits. Their different resonance frequencies permit selective radiofrequency pulses for one-qubit rotations. In a suitable rotating frame, refocusing removes unwanted one-spin terms while the NMR scalar coupling suppliesAssuming $J>0$, free evolution for $t=1/(2J)$ implements $U_J=e^{-i\pi Z_1{Z}_2/4}$. Define $R_z(\theta )=e^{-i\theta Z/2}$. ThenThis equality follows directly by evaluating the four diagonal entries: the first three are $+1$ and the $11$ entry is $-1$. Negative $J$ can be handled by refocusing or reversing the effective interaction sign. The global phase can be ignored.

Thus the marked-state phase oracle for $11$ requires scalar-coupling evolution and calibrated one-spin rotations. For a marked word $b_1{b}_2$, conjugate by $X_1^{1-b_1}{X}_2^{1-b_2}$, realized as selective $\pi$ pulses. The Grover diffusion operator uses the same entangling operation with additional one-qubit pulses. Liquid-state NMR quantum computing usually reads an ensemble signal and often prepares an effective pseudo-pure deviation from a large mixed background; that reproduces this small quantum algorithm's signal without providing a scalable source of pure initialized qubits.

A qubit has state $\alpha |0⟩+\beta |1⟩$ with $|\alpha {|}^2+|\beta {|}^2=1$. An $n$-qubit register occupies a $2^n$-dimensional Hilbert space and may contain entanglement. This large state space does not mean that a measurement reads out all its complex amplitudes: computational-basis outcomes occur with the Born rule probabilities.

A quantum circuit prepares a register, applies quantum gates, and measures selected outputs, possibly using classical feed-forward. Closed gates are unitary operators and therefore reversible; initialization, measurement and discarding can be treated using a larger system and environment. Single-qubit rotations together with an entangling two-qubit gate give a universal quantum gate set. The CNOT gate acts as $|x,y⟩\mapsto |x,y\oplus x⟩$.

For example, a Hadamard gate on the first qubit of $|00⟩$ followed by a CNOT creates $(|00⟩+|11⟩)/\sqrt{2}$. A Hadamard produces amplitudes with relative signs, so later gates can make unwanted alternatives interfere destructively and useful alternatives reinforce. Quantum algorithms organize this interference to improve a specified computational task; superposition alone does not supply an arbitrary speedup or permit reading every branch.

A finite discrete universal set such as Clifford gates together with a non-Clifford phase gate approximates general unitaries to chosen precision. Runtime includes the number of gates, repetitions and classical processing. Measurement outcomes may require multiple runs to estimate a probability or amplify success.

Quantum decoherence and imperfect gates limit an implementation. Quantum error correction encodes logical information into several physical qubits and measures error syndromes without directly learning the encoded amplitudes. Under appropriate noise and control assumptions, fault tolerance permits reliable longer computations; simply maintaining an isolated ideal state is not a realistic account of a large processor.

Peter Shor is a mathematician whose research includes quantum computing, quantum information theory, algorithms and computational geometry.^[ref] His quantum algorithms for integer factorization and discrete logarithms require a number of steps polynomial in the number of input digits. They made the distinction between classical and quantum computational resources concrete for problems used in cryptography.^[ref]

A quantum algorithm specifies quantum state preparation, a sequence of quantum gates and quantum measurements, and any classical computation controlling them. For a pure quantum state $|\psi ⟩={\sum }_x{\alpha }_x|x⟩$, computational-basis measurement returns $x$ with probability $|{\alpha }_x{|}^2$, as prescribed by the Born rule. David Deutsch formulated a universal quantum computer using unitary operators and measurement.^[ref]

For example, one Hadamard gate prepares $H|0⟩=(|0⟩+|1⟩)/\sqrt{2}$. Computational-basis measurement gives either bit with probability $1/2$. Applying another Hadamard gate before measuring instead gives $H^2|0⟩=|0⟩$: the amplitudes for outcome one cancel by quantum interference. This illustrates why manipulating probability amplitudes matters; merely preparing a superposition does not reveal every component.

An analysis of algorithms must state the counted resources: quantum gate count, number of qubits, quantum state preparation cost and repetitions needed for the required probability of a correct result. Quantum query complexity counts quantum oracle calls separately; one such call need not be one elementary quantum gate.

Quantum computing processes quantum information through controlled physical transformations and quantum measurements. In the quantum circuit model, an initial quantum state evolves through quantum gates, and the Born rule predicts the final outcome probabilities. Quantum interference makes the relative quantum phases of amplitudes computationally useful. David Deutsch's 1985 paper developed a model of universal quantum computation.^[ref]

A one-qubit example shows why amplitudes matter. Starting from $|0⟩$, a Hadamard gate gives $(|0⟩+|1⟩)/\sqrt{2}$; a second Hadamard gate returns $|0⟩$. Insert a Pauli Z gate between the two Hadamard gates and the final state is instead $|1⟩$: the intermediate relative sign changes how amplitudes combine. Measuring the intermediate state alone would give equal probabilities in both cases. A useful quantum algorithm arranges such transformations to make information about the required answer accessible through the final quantum measurement.

An experimental physicist who coauthored a programmable neutral-atom quantum computer demonstration. Focused light beams addressed individual qubits in a two-dimensional array, while interactions between Rydberg atoms enabled entangling operations. The experiment combined quantum logic gates into quantum algorithms, testing whether a collection of controlled chemical atoms could execute complete circuits.^[ref]