Quantum Computation

Computation is about transforming input information to output information [1]. Information comprises symbols as an alphabet, usually represented by finite strings of binary digits (bits) $\bm{b}=(b_{k})_{k=0}^{n-1}\in\{0,1\}^{n}$, but could be distributions thereof [2], although radically different informational foundations such as real numbers $\mathbb{R}$ [3] are possible. Informational transformations are governed by a well defined logical process, founded on the basic logical steps inherent in the physical realisation of the information-processing machine such as a Turing machine, which serves as a model for deterministic computation based on recursive functions [4]. These logical processes could be about solving equations [5], or executing an algorithm according to basic arithmetic or logical operations on a computer, which is a programmable machine capable of executing sequences of such operations, or instructions. The framework of computer science separates computational problems into types that include decision, function, search, optimisation, and feasibility problems. Problems can be computable or not [6] and have different complexity [7], which are studied in theoretical computer science.

As information is physical [8, 9], treating the Turing machine as a physical device is consequently convenient, and then quantum computation enters by quantizing the classical physics describing that machine [10]. Superpositions of information states are thus possible, and ideal processing of such quantum information states can be described by unitary transformations, followed by quantum measurements with their probabilistic nature. The logical foundation differs for quantum computation compared to classical (i.e., using non-quantum physics) computation—Boolean logic is replaced by quantum logic.

This chapter focuses on quantum computation, with computational problems, and therefore input and output, being classical, but the computational processing of this information being in the quantum domain, hence involving quantum logic operations.

Computation is conveniently understood in terms of Boolean algebra, which formalises processing logical propositions mathematically. A $k$-ary Boolean function $f:\{0,1\}^{k}\to\{0,1\}:\bm{b}\mapsto f(\bm{b})$ represents a decision problem, also known as a (formal) language, with $k=1$ for unary and $k=2$ for binary functions. The unary functions are identity $\mathds{1}$, which leaves the bit unchanged, and NOT, or ‘negation’, which flips: $\neg b\leftarrow b\oplus 1$ for $\oplus$ summation modulo 2, $\lnot$ for negation and $\leftarrow$ for ‘gets’.

In Boolean logic, a literal comprises both a logical variable $b\in\{0,1\}$ and its negation $\neg b$. Binary functions include $\oplus$ for ‘exclusive or’ and $\land$ (conjunction) and $\lor$ (disjunction) for logical ‘and’ and ‘or’ operations, respectively. A Boolean function $f$ is decidable if the output is true ($0$) conditioned on the proposition itself is true, and false ($1$) conditioned on the proposition itself is false. Ideally, a program accepts input and delivers an output representing the solution to the problem in a finite number of steps and then halts. However, some problems, such as the halting problem [11] are undecidable (not every problem corresponds to a program that halts after a finite number of steps), hence uncomputable, because either of these conditions fails.

Consider any $n$-bit Boolean function $f$. Remarkably, a $k$-ary value $K\geq 2$ can be fixed such that $f$ can be solved via a composition of $k$-ary Boolean functions with $k\leq K$ functions independent of the choice of $n$. This universal set of $k\leq K$ generating operations is the ‘instruction set’, and the composition of these $k$-ary functions is the ‘circuit’ to solve $f$. Moreover, certain $k$-ary functions, such as NAND ($\neg\circ\land$ with $\circ$ signifying composition of functions), are universal in the sense that compositions of this binary function alone generates any circuit.

From Boolean functions, we can build the notion of Boolean circuits. A Boolean circuit is a finite directed acyclic graph [12], whose vertices comprise $n$ input bits and a universal set of Boolean gates (with the number of such gates being the circuit size) and has output bits. The Boolean circuit can be designed to compute Boolean function $f$, which implies just one output bit, and the length of the circuit is the maximum number of edges to go from an input to an output gate. Circuit-depth complexity for $f$ is the minimum of these maximum lengths over all Boolean circuits designed to compute $f$.

Time in computation is related to circuit depth. Measuring time in this way is valuable for studying computational complexity as this time depends on the logical operations and not on how fast the physical hardware, such as the speed of a particular implementation of NAND, is. If a Turing machine computes $f$ in time $T(n)$, then a Boolean circuit can solve $f$ in depth $\tilde{O}(T(n))$ [13], meaning the same time scaling up to logarithmic factors with $\tilde{O}$ as explained in Eq. (2).

The space resource of a circuit refers to the number of bits required for the logical circuit. Time-space trade-offs exist such that more or less space could be used to decrease or increase, respectively, the computational time as circuit depth. Resource consumption is quantified by the computational cost, which need not be unique.

A computational problem is defined over instances; for example the problem of factoring semiprime numbers (numbers expressible as $pq$ with $p,q\in\mathbb{P}$ for $\mathbb{P}$ the set of prime numbers) accepts different semiprime instances such as $3763=53\times 71$ and $5141=53\times 97$. Computational complexity studies how the (usually worst-case) cost of solving the problem increases as the size of the instance, measured as the minimum number $n$ of bits to specify the instance, grows.

For studies of asymptototic computational complexity, resource scaling in the large-instance limit is important. Bachmann-Landau notation [14] is used, with $O(g(x))$ defined by

$$\left\{f(x)|\exists M>0,x_{0}\in\mathbb{R}:|f(x)|\leq Mg(x)\forall x\geq x_{0}\right\}.$$

(1)

We define

$$\text{poly}x:=\bigcup_{c\in\mathbb{R}^{+}}O(x^{c}),\,\tilde{O}(f(x)):=O\left(f(x)\text{polylog}x\right)$$

(2)

with the latter known as soft-O notation that incorporates polynomial-of-logarithm factors with polylog being ‘poly’ over ‘log’.

Complementary to big-O (1), $o(g(x))$ is defined by

$$\left\{f(x)|\forall M>0\exists a\in\mathbb{R}:0\leq f(x)<Mg(x)\forall x>a\right\}$$

(3)

meaning that $f(x)$ is smaller than $g(x)$ for large $x$. For lower bounds [15], the relation

$$g(x)\in\Omega(f(x))\Leftrightarrow f(x)\in O(g(x)),$$

(4)

which defines $\Omega$, is useful, and

$$\Theta(f(x)):=O(f(x))\cap\Omega(f(x))$$

(5)

expresses tight bounds. With respect to computational complexity, the number of bits $n$ replaces $x\in\mathbb{R}$ in these expressions, and we use Bachmann-Landau notation [14] in discussing complexity of classical and quantum algorithms and classical here.

A decision problem, or language $L$, is deemed to be tractable if both space and time costs scale as poly$n$ by Cobham’s Thesis [16]; i.e., $L$ is in complexity class P meaning polynomial (henceforth ‘poly’ for short) time on a Turning machine; P$\subseteq$PSPACE, which means poly space (memory), and PSPACE contains all complexity classes within what is known as the polynomial-time hierarchy [17]. Conversely, $L$ is ‘hard’ if all known algorithms are superpoly$n$, i.e., cannot be bounded in poly time so ‘superpolynomial’ in the worst-case scenario.

As a special case of hard problems, the complexity class NP refers to nondeterministic poly-time, meaning $L$ is solved in poly time on a nondeterministic Turing machine. A nondeterministic Turing machine conducts a brute-force search by allowing a multitude of actions in parallel in contrast to the deterministic case with fixed action, and accepting the input if any branch of actions halts with an accept condition. The probabilistic Turing machine is a special case of a non-deterministic Turing machine wherein a probability distribution is provided to make weighted stochastic choices of computational transitions at each state.

Tractable computation on a nondeterministic Turing machine is equivalent to being computationally hard to solve but easy to verify on a (deterministic) Turing machine. Obviously, P$\subseteq$NP, but whether P$=$NP is a famous open problem [18]. With respect to any complexity class C, $L_{0}$ is C-Hard if every $L\in$C can be reduced in poly time to $L_{0}$, and $L$ is C-complete if $L_{0}$ is both C-hard and a member of C. NP-complete is an important example relevant to combinatorial optimisation [19] and to approximate optimisation [20].

The probabilistic Turing machine model deliberately leads to erroneous results: sometimes accepting strings that should be rejected and vice versal. Formally, $L$ is recognised by the probabilistic Turing machine if, given probability $\varepsilon$, a string in $L$ and a string not in $L$ are accepted or rejected with probability $1-\varepsilon$, respectively. The complexity class BPP corresponds to languages for $\varepsilon=\nicefrac{{2}}{{3}}$ (and PP, or probabilistic polynomial-time, for any $\varepsilon>\nicefrac{{1}}{{2}}$ [21], which contains NP). Obviously, P$\subseteq$BPP, but whether the widely believed equality P$=$BPP is true is an open problem.

The Boolean satisfiability problem (SAT)—deciding the existence of an assignment of values to a Boolean expression of literals such that the output is true—is an important type of computation [22] with special significance for quantum computation [23]. Expressed in conjunctive normal form, $k$-SAT is expressed as a conjunction ($\land$) of fixed-length clauses with each clause a disjunction ($\lor$) of $k$ literals. Not only is 2-SAT$\in$P [24], but 2-SAT$\in$NL-complete [25] as well, with NL meaning use of a logarithmic amount of space on a nondeterministic Turing Machine. In contrast, 3-SAT$\in$NP-complete and is pertinent for combinatorial optimization as finding the exact optimal solution is typically NP-complete.

Reversible computation [26] provides a valuable bridge from concepts of computation based on Boolean logic to concepts of quantum computation [27, 28]. One impetus for reversible computation arises from Maxwell’s demon, which enables studying entropy and the second law of thermodynamics [29]. From Szilard’s information engine incorporating Maxwell’s demon [30], Landauer connected information to thermodynamics by showing that erasure is physical [8].

Reversible computation shows that bit erasure can be postponed so the full computation can be achieved in a logically reversible way with the solution plus the ‘garbage’ bits at the output potentially serving as the input with the reversed version of the computation mapping this solution to the original input. For a finite machine undergoing a large number of computations, erasures are eventually needed to recoup space from garbage for useful information. However, energy consumption requirements per computational step can approach zero in a reversible computer.

Reversible computation is achieved by embedding the Boolean function $f$ into a reversible function as

$\displaystyle F:\{0,1\}^{n+1}\to\{0,1\}^{n+1}:(\bm{b},b^{\prime})\mapsto(\bm{b},b^{\prime}\oplus f(\bm{b}))$

(6)

for $\{0,1\}^{n+1}:=\{0,1\}^{n}\times\{0,1\}$, making reversible computation equivalent to permutation [31]. Analogous to Boolean logic, $F$ can be decomposed into a sequence of reversible $k$-ary logic gates, with $k$ independent of the choice of $n$. Whereas the binary NAND gate suffices as a universal gate for Boolean logic, a ternary gate, mapping three bits to three bits, is the smallest value for $k$ in reversible logic.

The Toffoli, or controlled-controlled-not gate (CCNOT) is one such universal gate [27] with C^ιNOT mapping $\iota$ control bits and one target bit to the same state unless all control bits are $1$ in which case the target bit flips. Another universal gate is the Fredkin [32], or controlled-SWAP, gate [33]. Thus, following the language established for Boolean logic, each of CCNOT and CSWAP is a cardinality-one universal instruction set for reversible computation. As for Boolean logic, decomposing logical circuits into the same kind of circuit allows careful comparison on relative complexity between different reversible functions $F$.

We begin with a brief mathematical description of nonrelativistic quantum mechanics [34]. A state is a normalised positive linear functional on a unital C^∗ algebra (comprising linear operators on a Hilbert space with the ^∗ operation representing adjoint, typically ^† in physics). Representing linear operators on Hilbert space is achieved by the Gel’fand-Naimark-Segal construction [35, 36], and each state can be uniquely identified with a positive semi-definite trace-class (‘density’) operator of unit trace by requiring equivalence between expectation values for representations of operators and the functional acting on the operator.

In the case of quantum bits (‘qubits’ [37]), states are density operators on a tensor product of two-dimensional Hilbert spaces: $\mathscr{H}_{2}^{n}$. Pure states are idempotent operators and thus can represented by vectors in $\mathscr{H}_{2}^{n}$, which is isomorphic to projective complex space of dimension $2n-1$, i.e., $P_{2n-1}(\mathbb{C})$, with $2n$ the overall Hilbert-space dimension and subtraction of one for the constraint on norm. Each multiqubit state is thus representable as a complex unit-length vector of length $2n$.

In Dirac notation, a qubit string is

$$\ket{\psi}^{n}=\sum_{\bm{b}\in\{0,1\}^{n}}\psi_{\bm{b}}\ket{\bm{b}},\,\left(\psi_{\bm{b}}\right)\in P_{2*-1}(\mathbb{C}),$$

(7)

with $\{\ket{\bm{b}}\}$ the ‘computational basis states’ of $\mathscr{H}_{2}^{n}$, i.e., basis vectors labelled by bit strings. Henceforth, we do not explicitly normalise the states if norm-$1$ is implied. Two useful examples of non-product states are ‘ebits’ (maximally entangled pair of qubits) $\ket{0\;b_{1}}+(-1)^{b_{0}}\ket{1\;1-b_{1}}$. The Hadamard gate maps $H\ket{b}\mapsto\ket{0}+(-1)^{b}\ket{1}$, and normalisation is implicit in both cases. Each multi-qubit gate is representable in $\mathcal{M}_{d}(\mathbb{C})$, meaning a $d\times d$ complex matrix, where $d=2^{n}$ for $n$ qubits. The distance between two normalised multiqubit states (7) is the ‘quantum angle’ $\arccos\left|\braket{\psi^{\prime}}{\psi}\right|$ corresponding to the Fubini-Study metric for $\mathscr{H}$ [38].

On an ideal quantum computer, $n$ qubits are transformed by unitary maps, i.e., isometries on Hilbert space: $U\ket{\psi}^{n}$ with $U\in\mathcal{M}_{2^{n}}(\mathbb{C})$ a representation of a group element in SU$(2^{n})$. The unitary map $U$ is generated by a self-adjoint Hamiltonian operator $H$ that describes the dynamical physical system yielding this gate, and $U$ forms a strongly continuous one-parameter unitary group over time $t$. The distance between two operators, say $A$ and $A^{\prime}$ (need not be unitary), is $\text{dis}(A,A^{\prime}):=\|A-A^{\prime}\|$ for $\|A\|:=\sup_{\left\|\ket{\psi}\right\|=1}\left\|A\ket{\psi}\right\|$ the spectral norm [39].

Whereas Boolean and reversible-logic functions are exactly decomposable to a sequence of instruction gates, with the universal instruction set having just one universal gate, a related decomposition theorem for quantum computation [40] yields a sequence that only approximately realizes $U$ and requires at least two instruction gates. The Solovay-Kitaev theorem, as formulated by Dawson and Nielsen [40], conveys that, given a universal instruction set for SU$(d)$ and accuracy $\epsilon>0$, $\exists c>0$ such that, $\forall U\in$SU$(d)$, a sequence of instruction gates of depth $O\left(\log^{c}\left(\nicefrac{{1}}{{\epsilon}}\right)\right)$ exists such that the unitary map so generated has a distance, based on operator norm, not greater than $\epsilon$. We write $\log$ for logarithm in base 2 as the default. Succinctly, any universal instruction set generates a polylog$\left(\nicefrac{{1}}{{\epsilon}}\right)$-depth quantum circuit approximating $U$, and, furthermore, the classical algorithm to generate this sequence is also polylog$\left(\nicefrac{{1}}{{\epsilon}}\right)$, with an even smaller constant $c$ than for the circuit depth [40].

A choice is made regarding which quantum instruction gates to include, with one common choice being [41]

$$\left\{\text{H}=\begin{pmatrix}1&1\\ 1&-1\end{pmatrix}/\sqrt{2},\text{T}:=\text{diag}(1,\omega_{8}),\text{CNOT}\right\}$$

(8)

for $\omega_{d}$ the $d^{\text{th}}$ principal root of unity. Alternatively, combining H with CCNOT whose representation is in $\mathcal{M}_{8}\mathbb{C})$, which is universal by itself for reversible computation, provides a universal instruction set for quantum computation. Physically, the universal instruction set $\{\text{H},\text{T},\text{CNOT}\}$ is convenient as only single- and two-body interactions are involved, whereas CCNOT involves more challenging three-body interactions.

In this section we consider quantum algorithms [42], quantum state generation and quantum heuristics, which tend to be grouped together under the term ‘quantum algorithms’. An algorithm is the means by which a computer solves a well posed computational problem and comprises (a perhaps empty) input, an output and a procedure. A procedure is expressed as a finite sequence of instructions based on a formal language and incurs finite cost.

On the other hand, heuristics are techniques for solving hard problems exactly or approximately, such as for search or optimisation types of problems, but are not guaranteed to succeed for finite cost. Heuristics are valuable for solving NP-hard problems. A metaheuristic is technique for devising or choosing or tuning a heuristic for attempting to solve optimisation or machine learning problems approximately [43], with simulated annealing for approximate global optimisation one important example of a metaheuristic.

As discussed in §II, reversible computation is permutation; extending reversible computation to quantum computation leads to permutations being replaced by unitary transformations. The algorithmic procedure acting on a $n$ qubits is then described by a unitary mapping $U$ on $\mathscr{H}_{2}^{n}$. Approximate quantum computation is achieved by realising approximate $U^{\prime}$ such that dis$(U,U^{\prime})<\epsilon$. The approximation $U^{\prime}$ must be achievable as a quantum circuit with computational cost that grows as polylog$n$, i.e., efficient and known as ‘speedup’. We shall next discuss important cases of quantum algorithms [44, 45].

Shor’s quantum factoring algorithm, the most celebrated of all quantum algorithms, was inspired by Simon’s algorithm [46]. Simon’s algorithm solves the following oracle problem, with an oracle black box being a system (e.g., a subroutine) that accepts inputs and yields outputs with an unspecified procedure. Cost is typically quantified by queries rather than in terms of time-space resources [42]. Given oracle $f:\{0,1\}^{n}\to\{0,1\}^{n}$, subject to the promise that $\exists s\in\{0,1\}^{n}$ such that

$$f(x)=f(y)\iff x\oplus y\in\left\{0^{n},s\right\}\forall x,y\in\{0,1\}^{n},$$

(9)

Simon’s problem is to compute $s$ with the fewest oracle queries possible and can be converted to a decision problem by rewriting the task as distinguishing whether $s=0^{n}$ or not. Importantly, Simon’s problem yields an exponential oracle separation between the two complexity classes, namely BPP and BQP, which is the quantum version of BPP.

Simon’s algorithm can be contrasted with the Bernstein-Vazirani algorithm [47], which also proves a separation between BPP and BQP but not exponentially. The Bernstein-Vazirani algorithm accepts an oracle with input $x\in\{0,1\}^{n}$ and yields a single-bit output $x\odot h$ (with Hadamard multiplication notation, which is element-wise vector or matrix multiplication) with the task being to find the hidden string $h\in\{0,1\}^{n}$. Quantumly, a single query suffices [47]; classically, $O(n)$ queries to the oracle are required.

The Bernstein-Vazirani algorithm is itself a specialisation of the Deutsch-Jozsa algorithm [48]. The Deutsch-Jozsa algorithm employs an oracle that accepts an $n$-bit input and yields a single-bit output subject to the promise that all $2^{n}$ possible outputs are either the same (constant case) or half yield output $1$ and the other half yield $0$ (balanced case). The task is to decide whether the oracle is constant or balanced, which can be solved quantumly with just one query in contrast to two queries for the $n=1$ deterministic classical algorithm [10] and exp$n$ queries for general $n$ [48]; However, the task can be achieved with $O(1)$ queries with a probabilistic algorithm so the Deutsch-Jozsa algorithm yields an exponential speedup over P but not over BPP.

Shor’s algorithm delivers superpoly$n$ speedup for factoring any $n$-bit number $N$ ($n=\lceil\log N\rceil$) compared to the best-known classical algorithms [49, 50], which shows that the computationally hard problem of integer factoring is tractable using quantum computation. Specifically, Shor’s algorithm for factoring an $n$-bit integer $N$ executes in $O(n^{3})$ time [49, 50], subsequently reduced to $\tilde{O}(n^{2})$ [51], which subexponentially outperforms the best known classical algorithm based on the general number sieve, whose complexity is [52]

$$O\left(\exp\left[c\left(\log n\right)^{\nicefrac{{1}}{{3}}}\left(\log\log n\right)^{\nicefrac{{2}}{{3}}}\right]\right)\sim 2^{\tilde{O}\left(n^{\nicefrac{{1}}{{3}}}\right)}$$

(10)

for $c\in\mathbb{R}^{+}$, and the soft-O notation in the exponent on the right-hand side captures the log and log log terms in the exponent on the left-hand side of Eq. (10).

Shor’s algorithm comprises the following steps. Given $N\in\mathbb{Z}^{+}$, choose random $a\in[N]$and compute $\gcd(a,N)$; terminate if $\gcd(a,N)\neq 1$ or else solve the order-finding problem, namely compute the smallest period $r$ such that

$$f_{N}(x+r)=f_{N}(x)\stackrel{{\scriptstyle\scriptscriptstyle N}}{{=}}a^{x}.$$

(11)

This order-finding problem is solved by Shor’s quantum algorithm, with $\stackrel{{\scriptstyle\scriptscriptstyle N}}{{=}}$ meaning equal modulo $N$. Start over if the resultant minimum $r$ is odd; else proceed. If $a^{r/2}\stackrel{{\scriptstyle\scriptscriptstyle N}}{{=}}-1$, start over; else return $\gcd\left(a^{r/2}\pm 1,N\right)$ and halt. Shor’s integer factoring algorithm dramatically affects cybersecurity, particularly on breaking the Rivest-Shamir-Adleman (RSA) public-key encryption [53]. Minimising $r$ is the classical computational bottleneck that leads to superpoly$n$ scaling for classical computation.

Shor’s quantum period-finding algorithm works as follows. Two input qubit strings with $k$ source qubits and $n$ target qubits satisfy

$$N^{2}\leq 2^{k}\leq 2N^{2},\,n=\lceil N\rceil$$

(12)

with $k$ chosen to ensure more than $N^{2}$ terms in the sum. Only $r$ distinct values of $a^{q}\bmod N$ are possible.

The first step is

$$H^{\otimes k}\ket{0}^{k+n-1}\ket{1}\mapsto\sum_{q=0}^{2^{k}-1}\ket{q}\ket{0}^{n-1}\ket{1}$$

(13)

with the input state being all qubits in the $\ket{0}$ except that the last target qubit is $\ket{1}$. An interesting fact is that the same transformation of $\ket{0}^{k}$ is achieved by the quantum Fourier transform (QFT)

$$\ket{q}\mapsto\sum_{q^{\prime}=0}^{2^{k}-1}\omega_{Q}^{qq^{\prime}}\ket{q^{\prime}},$$

(14)

following the convention of implicit state normalisation. Note that the inverse QFT, i.e., QFT^-1, is obtained by replacing $\omega_{Q}^{qq^{\prime}}$ with $\omega_{Q}^{-qq^{\prime}}$.

The next step in the quantum circuit is to execute the quantum subcircuit for order-finding, which can conveniently be viewed as an oracle problem. The order-finding oracle yields the order $r$ of a group in a full oracle-free circuit. For some quantum algorithms discussed below, the oracle approach and query cost is vital to showing quantum advantage, but, for Shor’s algorithm and its variants, the oracle is replaced by an explicit quantum subcircuit and costs are expressed in space and time.

For quantum order-finding, the oracle is replaced by a subcircuit that executes a quantum version of classical exponentiation by squaring [54]. This quantum subcircuit [55] performs $\ket{q,0}\mapsto\ket{q,a^{q}\bmod N}$ with $\ket{q,0}$ having $q$ as a label for the source qubit string and the second label $0$ for the target qubit string. Thus, the output quantum state from the order-finding subcircuit is

$$\sum_{q=0}^{2^{k}-1}\ket{q,a^{q}\bmod N}=\sum_{p=0}^{r-1}\sum_{q=0}^{k-1}\ket{rq+p,a^{p}\bmod N},$$

(15)

with this final form convenient to show how terms can be grouped together due to the modular exponent term in the target qubits. Most of the quantum cost for Shor’s algorithm is in executing this quantum subcircuit.

The next step of Shor’s algorithm is to apply QFT^-1 to this output state, which yields

$$\sum_{p=0}^{r-1}\sum_{q=0}^{r-1}\omega_{r}^{-pq}\ket{kq,a^{p}\bmod N}.$$

(16)

Measuring only the source qubit string $s$ suffices to infer $r$: discarding the $s=0$ case, $s$ is highly likely to be a multiple of $k$ with coefficients from $1$ to $r-1$. An efficient number of repeats of this process suffices to estimate $r$ with high confidence [56].

Quantum speedup for order finding also applies to other computational problems. One case is the discrete logarithm problem, posed as accepting $a,b,N\in\{0,1\}^{n}$ with the promise that $\exists s:b\stackrel{{\scriptstyle\scriptscriptstyle N}}{{=}}a^{s}$, and the task is to find $s$, which can be achieved in poly$n$ time [50] compared to superpoly$n$ classically. Quantum computers can solve the discrete logarithm problem on elliptic curves using Shor’s technique [50], thereby breaking elliptic curve cryptography [57, 58, 29].

Another case concerns solving Pell’s Equation

$$x^{2}-dy^{2}=1,\,x,y,d\in\mathbb{Z},$$

(17)

with $d$ not a square. The computational problem is

$$(x_{1},y_{1})=\min\left(x+y\sqrt{d}:d\in\{0,1\}^{n}\right),$$

(18)

which is uniquely identified by $\lfloor R\rceil$ with $R:=\log(x_{1}+y_{1}\sqrt{d})$. Whereas computing $\lfloor R\rceil$ is superpoly$n$, Hallgren’s quantum algorithm finds $\lfloor R\rceil$ in poly$n$ time [59], which breaks the Buchman-Williams cryptosystem [60].

The Abelian Hidden Subgroup Problem [61] is regarded as the heart of Shor’s and related algorithms and yields a superpoly$n$ speedup over the best classical alternative. Formally, the problem is described by considering a finitely generated Abelian group $G$ and a subgroup $H$ with $G/H$ being finite along with a function $f:G\to X$, for some set $X$. Furthermore $G$ ‘hides’ $H$; i.e.,

$$\forall g,g^{\prime}\in G,f(g)=f(g^{\prime})\Leftrightarrow gH=g^{\prime}H.$$

(19)

The task is to find a set of generators for $H$ via queries to $f$; this is solvable on a quantum computer using $O(\log|G|)$ queries, whereas classically $\Omega(|G|)$ are required [57, 62], although solving in one query is possible for some instances [63].

Significant effort has been dedicated to devising quantum algorithms for speeding up solutions to non-Abelian hidden subgroups, with successful quantum speedup in some cases [64] and important implications for problems such as graph isomorphism in the symmetric-group case [65] or some lattice problems for the dihedral-group (symmetry group of the $n$-sided polygon) case [66] with the computational cost for finding a hidden subgroup of the dihedral group reduced to $2^{O(\log\sqrt{n})}$ in the quantum case compared to the classical cost of $O(\sqrt{n})$ [67]. This algorithm was further extended to be subexponential in time and polynomial in space [68].

Although Shor’s algorithm and the variants discussed above can be posed as oracular algorithms, the analyses above typically consider space and time cost. On the other hand, the quantum search algorithm [69] is naturally posed as an oracle problem. This quantum algorithm for unstructured search finds, with high probability, the unique oracle input whose output is $1$ (all other $N-1$ oracle outputs are $0$ although extendable to multiple $1$ [70]).

First the procedure creates a uniform superposition of states and then applies the quantum oracle $\ket{x}\mapsto(-1)^{f(x)}\ket{x}$, which changes the phase of the marked state. After sufficiently many iterations, the quantum search algorithm halts and resultant quantum states are measured, with measurement of the marked state being highly likely: A high probability of determining the marked state is achieved with just $O(\sqrt{N})$ queries to the quantum oracle [71] compared to the classical requirement of $O(N)$ queries to the classical oracle $f$. The quantum search algorithm is optimal [71, 72].

Importantly, although the search-algorithm improvement is only quadratic with respect to query complexity, the quadratic improvement is provable, whereas Shor’s algorithm is subexponentially better but based on polynomial hierarchy [17] arguments rather than on a formal proof. The quantum search algorithm has amplitude estimation [73, 74, 75] at its core and is at the core of quadratically sped-up quantum algorithms such as for enhancing the classical 3-SAT algorithm [76].

Another type of task for a quantum computer is to simulate Hamiltonian-generated evolution on a system with $n$ degrees of freedom for the Hamiltonian $H$ promised to have certain properties. These properties could include being row-computable, which means that the elements of each row of the Hermitian matrix representing $H$ are computable, perhaps efficiently. Another property could be that the Hamiltonian is $k$-local, which means $H=\sum_{j=1}^{m}H_{j}$ for each $H_{j}$ a Hamiltonian acting on up to $k$ qubits. Yet another would be that every row of $H$ contains at most $d$ nonzero entries, meaning that it would have to be $d$-sparse.

The problem of quantum simulation, or quantum-state generation [77], originates with Feynman’s motivation for quantum computation [78]. One major focus of application is simulating chemical dynamics [79]. Hamiltonian-generated unitary evolution is described by unitary map $U=\exp(-\text{i}Ht)$ (setting $\hbar=1$). This evolution is used to map any input state to its $H$-evolved form after time $t$. The quantum circuit for simulating this evolution can be achieved with a poly$(n,t)$-depth quantum circuit [77, 80, 81, 82], hence efficient with respect to these quantities and not believed to be efficient classically.

Generating the quantum state as a solution is a step towards solving a computational problem but is not the full solution as the end point does not yield an output string as the solution. For example, finding the ground-state energy of a $k$-local Hamiltonian is important for physics and chemistry but this problem is hard to solve. To understand this hardness, we consider the complexity class QMA. Roughly speaking QMA is to BQP what NP is to BPP (or to P itself if BPP$=$P). Solving the ground state of a $k$-local Hamiltonian is QMA-complete for $k\geq 2$ [83] (but in P for $k=1$). Other applications such as simulating chemical dynamics [79] have been explored.

This complexity result for finding the ground state is analogous to the maximum satisfiability problem (MAX-SAT), which is an optimisation extension of SAT. The task for MAX-SAT is to determine the maximum number of clauses of a given Boolean formula expressed in conjunctive normal form that can be made true. For more than one clause, MAX-SAT is NP-complete. For quantum computation, an extension of MAX-SAT to weighted MAX-SAT [84] is important. Given a Boolean formula in conjunctive normal form, with each clause assigned a non-negative weight, the task is to assign values to the variables that maximize the combined weight of the satisfied clauses.

One application of quantum-state generation has been as a system-of-linear-equations (SLEP ) solver [85]. This ‘HHL’, or SLEP, problem [86], accepts an oracle description of $A\in\mathcal{M}_{n}(\mathbb{R})$ and an efficient description of a vector $\bm{b}$ (not to be confused with the bit string defined earlier) and an accuracy parameter $\varepsilon$. The task is to compute some property of $f(A)\bm{b}$ for an efficiently computable function $f$. Suppose that $A$ is a polylog$n$-sparse Hermitian matrix. Furthermore, suppose $A$ has condition number $\kappa$ that, generically, quantifies sensitivity of a function’s output to variation of input. Specifically, for $A\bm{x}=\bm{b}$ (noting that $\|A\|$ is $A$’s largest singular value and, if $A$ is square, $\|A^{-1}\|$ is $A$’s smallest singular value), the ratio of the fractional error of $\bm{x}$ to the fractional error of $\bm{b}$ has an upper bound of $\kappa:=\|A\|\cdot\|A^{-1}\|$ [87].

Under these assumptions, some expectation values of operators with respect to $f(A)\bm{b}$ can be approximated by quantum computation in $O(\kappa^{2}\log n)$ time within poly$\left(\nicefrac{{1}}{{\varepsilon}}\right)$ achieving poly$(\nicefrac{{1}}{{\varepsilon}})$ accuracy [86]/ The HHL algorithm can be extended to non-sparse matrices but require pre-computation [88, 89]. Practical applications such as for recommendation systems [88] and principal component analysis [90] were later shown to be solvable in poly time by classical randomised algorithms (known as dequantising quantum algorithms) in 2019 [91] and in 2021 [92], respectively. By similar means, the application of the SLEP method to quantum algorithms for singular-value transformation [93, 94] were also dequantised [95], showing the immense challenge in taking the HHL algorithm all the way to practical applications.

Many more quantum algorithms have been constructed and their complexities analysed, but this discussion conveys some of the key concepts in studies of quantum algorithms and complexity. Another large area of quantum computation research concerns quantum heuristics for optimisation. Especially prominent amongst these heuristics is the ‘Quantum Approximate Optimization Algorithm’, or QAOA for short, applied to approximate solutions of combinatorial optmisiation problems [96, 97]. Early on, this heuristic achieved a better approximation ratio than any known polynomial-time classical algorithm to a to a Bounded Occurrence Constraint Problem [98]. Subsequently, an efficient classical algorithm that achieves the hardness-of-approximation limit for the approximation ratio was achieved [99].

The quantum-circuit, or gate-based, approach to quantum algorithms is not the only way to perform quantum computation. Other approaches include measurement-based, or one-way, quantum computation [100], quantum walks [101], and topological quantum computation [102], but equivalences between these approaches and the quantum circuit model are known. One alternative approach, however, began with a presumption of inequivalence: adiabatic quantum computation [103, 104].

Following the adiabatic theorem (but bearing in mind caveats [105]), which posits that a system in a ground state remains in that state if the evolution is sufficiently slow, adiabatic quantum computation is about commencing with an easy-to-prepare ground state of some Hamiltonian and evolving the system slowly to a new Hamiltonian whose ground state encodes the solution to a problem, generally one pertinent to combinatorial optimisation. Adiabatic quantum computation was tested for small instances of an NP-complete problem with indications that adiabatic quantum computation could be advantageous for NP-complete problems [104].

For the minimum eigenvalue gap $\gamma$ between the ground and first excited states, the run time of an adiabatic process is $O(\nicefrac{{1}}{{\gamma^{3}}})$ [106], which can be improved to $\tilde{O}(\nicefrac{{1}}{{\gamma^{2}}})$ if the evolution is sufficiently smooth [107]. Adiabatic quantum computation is divided into two types: stochastic vs non-stochastic Hamiltonian, with the stochastic Hamiltonian being represented by a matrix whose off-diagonal elements in the standard basis are are real and non-positive [108]. Adiabatic quantum computation with non-stochastic Hamiltonians is at least as efficient as quantum circuits, whereas restricting to stochastic Hamiltonians is likely weaker than using quantum circuits [109] but likely better than classical computation [110].

This chapter reviews essential fundamentals of classical computation and quantum mechanics to be able to convey concisely the essence of quantum computation. The material covered is not exhaustive but rather explains some of the major advances since inception of the field and aims to convey the key concepts. The quantum algorithm zoo [45] is an excellent source of comprehensive information about all quantum algorithms, and this chapter is partially meant to provide a useful primer for being able to read the material in this zoo.

The industrial side of quantum computation must contend with the parlous state of current quantum computer technologies and so runs whatever quantum algorithms and heuristics are promising and feasible on existing devices. Consequently much of the material here is beyond the reach of existing commercial quantum computers. The basics of building a quantum computer are not covered here but can be studied from other sources [111]. Existing quantum computers are said to be following the noisy intermediate-scale quantum paradigm [112, 113], which constitutes a valuable step towards large scalable quantum computers of the future.