Editing Quantum computing (section)

== Quantum information processing ==
{{See also|Introduction to quantum mechanics}}

[[Computer engineer]]s typically describe a [[modern computer]]'s operation in terms of [[classical electrodynamics]].
Within these "classical" computers, some components (such as [[semiconductors]] and [[random number generators]]) may rely on quantum behavior, but these components are not [[isolated system|isolated]] from their environment, so any [[quantum information]] quickly [[quantum decoherence|decoheres]].
While [[programmers]] may depend on [[probability theory]] when designing a [[randomized algorithm]], quantum mechanical notions like superposition and [[quantum interference|interference]] are largely irrelevant for [[program analysis]].

[[Quantum program]]s, in contrast, rely on precise control of [[quantum coherence|coherent]] quantum systems. Physicists [[mathematical formulation of quantum mechanics|describe these systems mathematically]] using [[linear algebra]]. [[Complex number]]s model [[probability amplitude]]s, [[vector (mathematics and physics)|vectors]] model [[quantum state]]s, and [[matrix (mathematics)|matrices]] model the operations that can be performed on these states. Programming a quantum computer is then a matter of [[function composition (computer science)|composing]] operations in such a way that the resulting program computes a useful result in theory and is implementable in practice.

As physicist [[Charles H. Bennett (physicist)|Charlie Bennett]] describes the relationship between quantum and classical computers,<ref>{{Cite AV media |url=https://www.youtube.com/live/rslt-LwtDK4&t=4102 |title=Information Is Quantum: How Physics Helped Explain the Nature of Information and What Can Be Done With It |date=2020-07-31 |last=Bennett |first=Charlie |type=Videotape |author-link=Charles H. Bennett (physicist) |time=1:08:22 |via=YouTube}}</ref>
{{Blockquote|text=A classical computer is a quantum computer&nbsp;... so we shouldn't be asking about "where do quantum speedups come from?" We should say, "well, all computers are quantum.&nbsp;... Where do classical slowdowns come from?"}}

=== Quantum information ===
Just as the bit is the basic concept of classical information theory, the ''[[qubit]]'' is the fundamental unit of [[quantum information]]. The same term ''qubit'' is used to refer to an abstract mathematical model and to any physical system that is represented by that model. A classical bit, by definition, exists in either of two physical states, which can be denoted 0 and 1. A qubit is also described by a state, and two states often written <math>|0\rangle</math> and <math>|1\rangle</math> serve as the quantum counterparts of the classical states 0 and 1. However, the quantum states <math>|0\rangle</math> and <math>|1\rangle</math> belong to a [[vector space]], meaning that they can be multiplied by constants and added together, and the result is again a valid quantum state. Such a combination is known as a ''superposition'' of <math>|0\rangle</math> and <math>|1\rangle</math>.{{sfn|Nielsen|Chuang|2010|page=13}}{{sfn|Mermin|2007|p=17}}

A two-dimensional [[vector (mathematics and physics)|vector]] mathematically represents a qubit state. Physicists typically use [[Dirac notation]] for quantum mechanical [[linear algebra]], writing <math>|\psi\rangle</math> {{gloss|ket [[psi (Greek)|psi]]}} for a vector labeled <math>\psi</math> . Because a qubit is a two-state system, any qubit state takes the form <math>\alpha|0\rangle+\beta|1\rangle</math> , where <math>|0\rangle</math> and <math>|1\rangle</math> are the standard ''basis states'',{{efn|The [[standard basis]] is also the ''computational basis''.{{sfn|Mermin|2007|p=18}}}} and <math>\alpha</math> and <math>\beta</math> are the ''[[probability amplitude]]s,'' which are in general [[complex numbers]].{{sfn|Mermin|2007|p=17}} If either <math>\alpha</math> or <math>\beta</math> is zero, the qubit is effectively a classical bit; when both are nonzero, the qubit is in superposition. Such a [[quantum state vector]] acts similarly to a (classical) [[probability vector]], with one key difference: unlike probabilities, probability {{em|amplitudes}} are not necessarily positive numbers.{{sfn|Aaronson|2013|page=110}} Negative amplitudes allow for destructive wave interference.

When a qubit is [[quantum measurement|measured]] in the [[standard basis]], the result is a classical bit. The [[Born rule]] describes the [[norm-squared]] correspondence between amplitudes and probabilities{{mdash}}when measuring a qubit <math>\alpha|0\rangle+\beta|1\rangle</math>, the state [[wave function collapse|collapses]] to <math>|0\rangle</math> with probability <math>|\alpha|^2</math>, or to <math>|1\rangle</math> with probability <math>|\beta|^2</math>.
Any valid qubit state has coefficients <math>\alpha</math> and <math>\beta</math> such that <math>|\alpha|^2+|\beta|^2 = 1</math>.
As an example, measuring the qubit <math>1/\sqrt {2}|0\rangle+1/\sqrt{2}|1\rangle</math> would produce either <math>|0\rangle</math> or <math>|1\rangle</math> with equal probability.

Each additional qubit doubles the [[dimension (vector space)|dimension]] of the [[state space (physics)|state space]].{{sfn|Mermin|2007|p=18}}
As an example, the vector {{nowrap|{{sfrac|1|√2}}{{ket|00}} + {{sfrac|1|√2}}{{ket|01}}}} represents a two-qubit state, a [[tensor product]] of the qubit {{ket|0}} with the qubit {{nowrap|{{sfrac|1|√2}}{{ket|0}} + {{sfrac|1|√2}}{{ket|1}}}}.
This vector inhabits a four-dimensional [[vector space]] spanned by the basis vectors {{ket|00}}, {{ket|01}}, {{ket|10}}, and {{ket|11}}.
The [[Bell state]] {{nowrap|{{sfrac|1|√2}}{{ket|00}} + {{sfrac|1|√2}}{{ket|11}}}} is impossible to decompose into the tensor product of two individual qubits{{mdash}}the two qubits are ''[[quantum entanglement|entangled]]'' because neither qubit has a state vector of its own.
In general, the vector space for an ''n''-qubit system is 2<sup>''n''</sup>-dimensional, and this makes it challenging for a classical computer to simulate a quantum one: representing a 100-qubit system requires storing 2<sup>100</sup> classical values.

=== Unitary operators<span class="anchor" id="gate-application"></span> ===
{{See also|Unitarity (physics)}}

The state of this one-qubit [[quantum memory]] can be manipulated by applying [[quantum logic gate]]s, analogous to how classical memory can be manipulated with [[Logic gate|classical logic gates]]. One important gate for both classical and quantum computation is the NOT gate, which can be represented by a [[Matrix (mathematics)|matrix]]
<math display="block">X := \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}.</math>
Mathematically, the application of such a logic gate to a quantum state vector is modelled with [[matrix multiplication]]. Thus
: <math>X|0\rangle = |1\rangle</math> and <math>X|1\rangle = |0\rangle</math>.
The mathematics of single qubit gates can be extended to operate on multi-qubit quantum memories in two important ways. One way is simply to select a qubit and apply that gate to the target qubit while leaving the remainder of the memory unaffected. Another way is to apply the gate to its target only if another part of the memory is in a desired state. These two choices can be illustrated using another example. The possible states of a two-qubit quantum memory are
<math display="block">
 |00\rangle := \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix};\quad
 |01\rangle := \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \end{pmatrix};\quad
 |10\rangle := \begin{pmatrix} 0 \\ 0 \\ 1 \\ 0 \end{pmatrix};\quad
 |11\rangle := \begin{pmatrix} 0 \\ 0 \\ 0 \\ 1 \end{pmatrix}.
</math>
The [[Controlled NOT gate|controlled NOT (CNOT)]] gate can then be represented using the following matrix:
<math display="block">
 \operatorname{CNOT} :=
 \begin{pmatrix}
  1 & 0 & 0 & 0 \\
   0 & 1 & 0 & 0 \\
   0 & 0 & 0 & 1 \\
   0 & 0 & 1 & 0
 \end{pmatrix}.
</math>
As a mathematical consequence of this definition, <math display="inline">\operatorname{CNOT}|00\rangle = |00\rangle</math>, <math display="inline">\operatorname{CNOT}|01\rangle = |01\rangle</math>, <math display="inline">\operatorname{CNOT}|10\rangle = |11\rangle</math>, and <math display="inline">\operatorname{CNOT}|11\rangle = |10\rangle</math>. In other words, the CNOT applies a NOT gate (<math display="inline">X</math> from before) to the second qubit if and only if the first qubit is in the state <math display="inline">|1\rangle</math>. If the first qubit is <math display="inline">|0\rangle</math>, nothing is done to either qubit.

In summary, quantum computation can be described as a network of quantum logic gates and measurements. However, any [[deferred measurement principle|measurement can be deferred]] to the end of quantum computation, though this deferment may come at a computational cost, so most [[quantum circuit]]s depict a network consisting only of quantum logic gates and no measurements.

=== Quantum parallelism ===

''Quantum parallelism'' is the heuristic that quantum computers can be thought of as evaluating a function for multiple input values simultaneously. This can be achieved by preparing a quantum system in a superposition of input states and applying a unitary transformation that encodes the function to be evaluated. The resulting state encodes the function's output values for all input values in the superposition, allowing for the computation of multiple outputs simultaneously. This property is key to the speedup of many quantum algorithms. However, "parallelism" in this sense is insufficient to speed up a computation, because the measurement at the end of the computation gives only one value. To be useful, a quantum algorithm must also incorporate some other conceptual ingredient.{{sfn|Nielsen|Chuang|2010|p=30–32}}{{sfn|Mermin|2007|pp=38–39}}

=== Quantum programming<span class="anchor" id="Models of computation for quantum computing"></span> ===
{{Further|Quantum programming}}

There are a number of [[model of computation|models of computation]] for quantum computing, distinguished by the basic elements in which the computation is decomposed.

==== Gate array {{anchor|Quantum circuit|Definition}} ====
[[File:Quantum Toffoli Gate Implementation.svg|thumb|A quantum circuit diagram implementing a [[Toffoli gate]] from [[Quantum logic gate|more primitive gates]]|upright=1.15]]

A [[quantum circuit|quantum gate array]] decomposes computation into a sequence of few-qubit [[quantum gate]]s. A quantum computation can be described as a network of quantum logic gates and measurements. However, any measurement can be deferred to the end of quantum computation, though this deferment may come at a computational cost, so most quantum circuits depict a network consisting only of quantum logic gates and no measurements.

Any quantum computation (which is, in the above formalism, any [[unitary matrix]] of size <math>2^n \times 2^n</math> over <math>n</math> qubits) can be represented as a network of quantum logic gates from a fairly small family of gates. A choice of gate family that enables this construction is known as a [[Quantum logic gate#Universal quantum gates|universal gate set]], since a computer that can run such circuits is a [[universal quantum computer]]. One common such set includes all single-qubit gates as well as the CNOT gate from above. This means any quantum computation can be performed by executing a sequence of single-qubit gates together with CNOT gates. Though this gate set is infinite, it can be replaced with a finite gate set by appealing to the [[Solovay–Kitaev theorem|Solovay-Kitaev theorem]]. Implementation of Boolean functions using the few-qubit quantum gates is presented here.<ref>{{Cite book |last1=Kurgalin |first1=Sergei |title=Concise guide to quantum computing: algorithms, exercises, and implementations |last2=Borzunov |first2=Sergei |date=2021 |publisher=Springer |isbn=978-3-030-65054-4 |series=Texts in computer science |location=Cham}}</ref>

==== Measurement-based quantum computing ====

A [[measurement-based quantum computer]] decomposes computation into a sequence of [[Bell state#Bell state measurement|Bell state measurements]] and single-qubit [[quantum gate]]s applied to a highly entangled initial state (a [[cluster state]]), using a technique called [[quantum gate teleportation]].

==== Adiabatic quantum computing ====

An [[Adiabatic quantum computation|adiabatic quantum computer]], based on [[quantum annealing]], decomposes computation into a slow continuous transformation of an initial [[Hamiltonian (quantum mechanics)|Hamiltonian]] into a final Hamiltonian, whose ground states contain the solution.<ref name="Das 2008 1061–1081">{{cite journal|last1=Das|first1=A.|last2=Chakrabarti|first2=B. K.|year=2008|title=Quantum Annealing and Analog Quantum Computation|journal=[[Reviews of Modern Physics|Rev. Mod. Phys.]]|volume=80|issue=3|pages=1061–1081|arxiv=0801.2193|bibcode=2008RvMP...80.1061D|citeseerx=10.1.1.563.9990|doi=10.1103/RevModPhys.80.1061|s2cid=14255125}}</ref>

==== Neuromorphic quantum computing ====
Neuromorphic quantum computing (abbreviated as 'n.quantum computing') is an unconventional type of computing that uses [[Neuromorphic engineering|neuromorphic computing]] to perform quantum operations. It was suggested that quantum algorithms, which are algorithms that run on a realistic model of quantum computation, can be computed equally efficiently with neuromorphic quantum computing. Both traditional quantum computing and neuromorphic quantum computing are physics-based unconventional computing approaches to computations and do not follow the [[von Neumann architecture]]. They both construct a system (a circuit) that represents the physical problem at hand and then leverage their respective physics properties of the system to seek the "minimum". Neuromorphic quantum computing and quantum computing share similar physical properties during computation.

==== Topological quantum computing ====

A [[topological quantum computer]] decomposes computation into the braiding of [[anyon]]s in a 2D lattice.<ref name="Nayaketal2008">{{cite journal |last1=Nayak |first1=Chetan |last2=Simon |first2=Steven |last3=Stern |first3=Ady |last4=Das Sarma |first4=Sankar |year=2008 |title=Nonabelian Anyons and Quantum Computation |journal=Reviews of Modern Physics |volume=80 |issue=3 |pages=1083–1159 |arxiv=0707.1889 |bibcode=2008RvMP...80.1083N |doi=10.1103/RevModPhys.80.1083 |s2cid=119628297}}</ref>

==== Quantum Turing machine ====

A [[quantum Turing machine]] is the quantum analog of a [[Turing machine]].<ref name="The computer as a physical system"/> All of these models of computation—quantum circuits,<ref>{{Cite book|last=Chi-Chih Yao|first=A.|title=Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science |chapter=Quantum circuit complexity |year=1993|chapter-url=https://ieeexplore.ieee.org/document/366852|pages=352–361|doi=10.1109/SFCS.1993.366852|isbn=0-8186-4370-6|s2cid=195866146}}</ref> [[One-way quantum computer|one-way quantum computation]],<ref>{{Cite journal |last1=Raussendorf |first1=Robert |last2=Browne |first2=Daniel E. |last3=Briegel |first3=Hans J. |date=2003-08-25 |title=Measurement-based quantum computation on cluster states |journal=Physical Review A |volume=68 |issue=2 |pages=022312 |doi=10.1103/PhysRevA.68.022312 |arxiv=quant-ph/0301052 |bibcode=2003PhRvA..68b2312R |s2cid=6197709}}</ref> adiabatic quantum computation,<ref>{{Cite journal |last1=Aharonov |first1=Dorit |last2=van Dam |first2=Wim |last3=Kempe |first3=Julia |last4=Landau |first4=Zeph |last5=Lloyd |first5=Seth |last6=Regev |first6=Oded |date=2008-01-01 |title=Adiabatic Quantum Computation Is Equivalent to Standard Quantum Computation |journal=SIAM Review |volume=50 |issue=4 |pages=755–787 |doi=10.1137/080734479 |arxiv=quant-ph/0405098 |bibcode=2008SIAMR..50..755A |s2cid=1503123 |issn=0036-1445}}</ref> and topological quantum computation<ref name="FLW02">{{Cite journal |last1=Freedman |first1=Michael H. |last2=Larsen |first2=Michael |last3=Wang |first3=Zhenghan |date=2002-06-01 |title=A Modular Functor Which is Universal for Quantum Computation |journal=Communications in Mathematical Physics |volume=227 |issue=3 |pages=605–622 |doi=10.1007/s002200200645 |issn=0010-3616 |arxiv=quant-ph/0001108 |bibcode=2002CMaPh.227..605F |s2cid=8990600}}</ref>—have been shown to be equivalent to the quantum Turing machine; given a perfect implementation of one such quantum computer, it can simulate all the others with no more than polynomial overhead. This equivalence need not hold for practical quantum computers, since the overhead of simulation may be too large to be practical.

====Noisy intermediate-scale quantum computing====
The [[threshold theorem]] shows how increasing the number of qubits can mitigate errors,{{sfn|Nielsen|Chuang|2010 |p=481}} yet fully fault-tolerant quantum computing remains "a rather distant dream".<ref name="preskill2018"/> According to some researchers, ''noisy intermediate-scale quantum'' ([[NISQ]]) machines may have specialized uses in the near future, but [[noise (signal processing)|noise]] in quantum gates limits their reliability.<ref name="preskill2018">{{Cite journal |last=Preskill |first=John |date=6 August 2018 |title=Quantum Computing in the NISQ era and beyond |journal=Quantum |volume=2 |page=79 |arxiv=1801.00862 |doi=10.22331/q-2018-08-06-79 |doi-access=free |bibcode=2018Quant...2...79P |s2cid=44098998}}</ref>
Scientists at [[Harvard University|Harvard]] University successfully created "quantum circuits" that correct errors more efficiently than alternative methods, which may potentially remove a major obstacle to practical quantum computers.<ref>{{Cite journal |last1=Bluvstein |first1=Dolev |last2=Evered |first2=Simon J. |last3=Geim |first3=Alexandra A. |last4=Li |first4=Sophie H. |last5=Zhou |first5=Hengyun |last6=Manovitz |first6=Tom |last7=Ebadi |first7=Sepehr |last8=Cain |first8=Madelyn |last9=Kalinowski |first9=Marcin |last10=Hangleiter |first10=Dominik |last11=Ataides |first11=J. Pablo Bonilla |last12=Maskara |first12=Nishad |last13=Cong |first13=Iris |last14=Gao |first14=Xun |last15=Rodriguez |first15=Pedro Sales |date=2023-12-06 |title=Logical quantum processor based on reconfigurable atom arrays |journal=Nature |volume=626 |issue=7997 |language=en |pages=58–65 |doi=10.1038/s41586-023-06927-3 |pmid=38056497 |pmc=10830422 |issn=1476-4687|arxiv=2312.03982 |s2cid=266052773 }}</ref><ref>{{Cite web |last=Freedberg Jr. |first=Sydney J. |date=2023-12-07 |title='Off to the races': DARPA, Harvard breakthrough brings quantum computing years closer |url=https://breakingdefense.sites.breakingmedia.com/2023/12/off-to-the-races-darpa-harvard-breakthrough-brings-quantum-computing-years-closer/ |access-date=2023-12-09 |website=Breaking Defense |language=en-US}}</ref> The Harvard research team was supported by [[Massachusetts Institute of Technology|MIT]], [[QuEra Computing]], [[California Institute of Technology|Caltech]], and [[Princeton University|Princeton]] University and funded by [[DARPA]]'s Optimization with Noisy Intermediate-Scale Quantum devices (ONISQ) program.<ref>{{Cite web |date=December 6, 2023 |title=DARPA-Funded Research Leads to Quantum Computing Breakthrough |url=https://www.darpa.mil/news-events/2023-12-06 |access-date=January 5, 2024 |website=darpa.mil}}</ref><ref>{{Cite web |last=Choudhury |first=Rizwan |date=2023-12-30 |title=Top 7 innovation stories of 2023 – Interesting Engineering |url=https://interestingengineering.com/lists/top-7-innovation-stories-of-2023-interesting-engineering |access-date=2024-01-06 |website=interestingengineering.com |language=en-US}}</ref>

==== Quantum cryptography and cybersecurity ====
Quantum computing has significant potential applications in the fields of cryptography and cybersecurity. Quantum cryptography, which leverages the principles of quantum mechanics, offers the possibility of secure communication channels that are fundamentally resistant to eavesdropping. Quantum key distribution (QKD) protocols, such as BB84, enable the secure exchange of cryptographic keys between parties, ensuring the confidentiality and integrity of communication. Additionally, quantum random number generators (QRNGs) can produce high-quality randomness, which is essential for secure encryption.

At the same time, quantum computing poses substantial challenges to traditional cryptographic systems. Shor's algorithm, a quantum algorithm for integer factorization, could potentially break widely used public-key encryption schemes like RSA, which rely on the intractability of factoring large numbers. This has prompted a global effort to develop post-quantum cryptography—algorithms designed to resist both classical and quantum attacks. This field remains an active area of research and standardization, aiming to future-proof critical infrastructure against quantum-enabled threats.

Ongoing research in quantum and post-quantum cryptography will be critical for maintaining the integrity of digital infrastructure. Advances such as new QKD protocols, improved QRNGs, and the international standardization of quantum-resistant algorithms will play a key role in ensuring the security of communication and data in the emerging quantum era.<ref>{{cite journal |last1=Pirandola |first1=S. |last2=Andersen |first2=U. L. |last3=Banchi |first3=L. |last4=Berta |first4=M. |last5=Bunandar |first5=D. |last6=Colbeck |first6=R. |last7=Englund |first7=D. |last8=Gehring |first8=T. |last9=Lupo |first9=C. |last10=Ottaviani |first10=C. |last11=Pereira |first11=J. |last12=Razavi |first12=M. |last13=Shamsul Shaari |first13=J. |last14=Tomamichel |first14=M. |last15=Usenko |first15=V. C. |last16=Vallone |first16=G. |last17=Villoresi |first17=P. |last18=Wallden |first18=P. |year=2020 |title=Advances in quantum cryptography |journal=Advances in Optics and Photonics |volume=12 |issue=4 |pages=1012–1236 |doi=10.1364/AOP.361502 |arxiv=1906.01645 |bibcode=2020AdOP...12.1012P}}</ref>

Quantum computing also presents broader systemic and geopolitical risks. These include the potential to break current encryption protocols, disrupt financial systems, and accelerate the development of dual-use technologies such as advanced military systems or engineered pathogens. As a result, nations and corporations are actively investing in post-quantum safeguards, and the race for quantum supremacy is increasingly shaping global power dynamics.<ref>{{cite web |last=Inderwildi |first=Oliver |title=The Quantum Computing Revolution: From Technological Opportunity to Geopolitical Power Shift |url=https://medium.com/the-geopolitical-economist/the-quantum-computing-revolution-geopolitics-economics-c2380e0167ee |website=The Geopolitical Economist |date=April 14, 2025 |access-date=April 14, 2025}}</ref>