1.5: Quantum Computation - A Short Course
- Page ID
- 135493
The reason I was keen to include at least some mathematical descriptions was simply that in my own study of quantum computation the only time I really felt that I understood what was happening in a quantum program was when I examined some typical quantum circuits and followed through the equations. Julian Brown, The Quest for the Quantum Computer, page 6.
My reason for beginning with Julian Brown’s statement is that I accept it wholeheartedly. I learn the same way. So in what follows I will present mathematical analyses of some relatively simple and representative quantum circuits that are designed to carry out important contemporary processes such as parallel computation, teleportation, data-base searches, prime factorization, quantum encryption and quantum simulation. I will conclude with a foray into the related area of Bell’s theorem and the battle between local realism and quantum mechanics.
Quantum computers use superpositions, entanglement and interference to carry out calculations that are impossible with a classical computer. Click here for insightful descriptions of the non-classical character of superpositions and entangled superpositions.
To illuminate the difference between classical and quantum computation we begin with a review of the fundamental principles of quantum theory using the computational methods of matrix mechanics.
A quon (an entity that exhibits both wave and particle aspects in the peculiar quantum manner - Nick Herbert, Quantum Reality, page 64) has a variety of properties each of which can take on two values. For example, it has the property of hardness and can be either hard or soft. It also has the property of color and can be either black or white, and the property of taste and be sweet or sour. The treatment that follows draws on material from Chapter 3 of David Z Albert's book, Quantum Mechanics and Experience.
The basic principles of matrix and vector math are provided in Appendix A. An examination of this material will demonstrate that most of the calculations presented in this tutorial can easily be performed without the aid of Mathcad or any other computer algebra program. In other words, they can be done by hand.
In the matrix formulation of quantum mechanics the hardness and color states are represented by the following vectors.
\[Hard : = \begin{pmatrix} 1 \\ 0 \end{pmatrix} \quad Soft : = \begin{pmatrix} 0 \\ 1 \end{pmatrix} \quad Black : = \begin{pmatrix} \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \end{pmatrix} \quad White : = \begin{pmatrix} \frac{1}{\sqrt{2}} \\ \frac{-1}{\sqrt{2}}\end{pmatrix} \nonumber \]
Hard and Soft represent an orthonormal basis in the two-dimensional Hardness vector space.
\[\begin{array} hHard^{T} \cdot Hard = 1 \qquad & Soft^{T} \cdot Soft = 1 \qquad & Hard^{T} \cdot Soft = 0 \\ \begin{pmatrix} 1 & 0 \end{pmatrix} \begin{pmatrix} 1 \\ 0 \end{pmatrix} = 1 & \begin{pmatrix} 0 & 1 \end{pmatrix} \begin{pmatrix} 0 \\ 1 \end{pmatrix} = 1 & \begin{pmatrix} 1 & 0 \end{pmatrix} \begin{pmatrix} 0 \\ 1 \end{pmatrix} = 0 \end{array} \nonumber \]
Likewise Black and White are an orthonormal basis in the two-dimensional Color vector space.
\[\begin{array} bBlack^{T} \cdot Black= 1 & White^{T} \cdot White= 1 \quad & Black^{T} \cdot White= 0 \\ \begin{pmatrix} \frac{1}{\sqrt{2}} \quad & \frac{1}{\sqrt{2}} \end{pmatrix} \begin{pmatrix} \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \end{pmatrix} = 1 & \begin{pmatrix} \frac{1}{\sqrt{2}} & \frac{-1}{\sqrt{2}} \end{pmatrix} \begin{pmatrix} \frac{1}{\sqrt{2}} \\ \frac{-1}{\sqrt{2}} \end{pmatrix} = 1 & \begin{pmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \end{pmatrix} \begin{pmatrix} \frac{1}{\sqrt{2}} \\ \frac{-1}{\sqrt{2}} \end{pmatrix} = 0 \end{array} \nonumber \]
The relationship between the two bases is reflected in the following projection calculations. Note: \(\frac{1}{\sqrt{2}} = 0.707\)
\[\begin{array} hHard^{T} \cdot Black= 0.707 \qquad & Hard^{T} \cdot White= 0.707 \qquad & Soft^{T} \cdot Black = 0.707 \qquad & Soft^{T} \cdot White = -0.707 \\ \begin{pmatrix} 1 & 0 \end{pmatrix} \begin{pmatrix} \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \end{pmatrix} = 0.707 & \begin{pmatrix} 1 & 0 \end{pmatrix} \begin{pmatrix} \frac{1}{\sqrt{2}} \\ \frac{-1}{\sqrt{2}} \end{pmatrix} = 0.707 & \begin{pmatrix} 0 & 1 \end{pmatrix} \begin{pmatrix} \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \end{pmatrix} = 0.707 & \begin{pmatrix} 0 & 1 \end{pmatrix} \begin{pmatrix} \frac{1}{\sqrt{2}} \\ \frac{-1}{\sqrt{2}} \end{pmatrix} = -0.707 \end{array} \nonumber \]
The values calculated above are probability amplitudes. The absolute square of those values is the probability. In other words, the probability that a black quon will be found to be hard is 0.5. The probability that a white quon will be found to be soft is also 0.5.
\[\begin{array} a(|Hard^{T} \cdot Black|)^{2} = 0.5 \qquad & (|Hard^{T} \cdot White|)^{2} = 0.5 \qquad & (|Soft^{T} \cdot Black|)^{2} = 0.5 \qquad & (|Soft^{T} \cdot White|)^{2} = 0.5 \\ \Bigg[ \Bigg| \begin{pmatrix} 1 & 0 \end{pmatrix} \begin{pmatrix} \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \end{pmatrix} \Bigg| \Bigg]^{2} = 0.5 & \Bigg[ \Bigg| \begin{pmatrix} 1 & 0 \end{pmatrix} \begin{pmatrix} \frac{1}{\sqrt{2}} \\ \frac{-1}{\sqrt{2}} \end{pmatrix} \Bigg| \Bigg]^{2} = 0.5 & \Bigg[ \Bigg| \begin{pmatrix} 0 & 1 \end{pmatrix} \begin{pmatrix} \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \end{pmatrix} \Bigg| \Bigg]^{2} = 0.5 & \Bigg[ \Bigg| \begin{pmatrix} 0 & 1 \end{pmatrix} \begin{pmatrix} \frac{1}{\sqrt{2}} \\ \frac{-1}{\sqrt{2}} \end{pmatrix} \Bigg| \Bigg]^{2} = 0.5 \end{array} \nonumber \]
Clearly Black and White can be written as superpositions of Hard and Soft, and vice versa.
\[\begin{array} a \dfrac{1}{\sqrt{2}} (Hard + Soft) = \begin{pmatrix} 0.707 \\ 0.707 \end{pmatrix} & \dfrac{1}{\sqrt{2}} \Bigg[ \begin{pmatrix} 1 \\ 0 \end{pmatrix} + \begin{pmatrix} 0 \\ 1 \end{pmatrix} \Bigg] = \begin{pmatrix} 0.707 \\ 0.707 \end{pmatrix} \\ \dfrac{1}{\sqrt{2}} (Hard - Soft) = \begin{pmatrix} 0.707 \\ -0.707 \end{pmatrix} & \dfrac{1}{\sqrt{2}} \Bigg[ \begin{pmatrix} 1 \\ 0 \end{pmatrix} - \begin{pmatrix} 0 \\ 1 \end{pmatrix} \Bigg] = \begin{pmatrix} 0.707 \\ -0.707 \end{pmatrix} \\ \dfrac{1}{\sqrt{2}} (Black+ White) = \begin{pmatrix} 1 \\ 0 \end{pmatrix} & \dfrac{1}{\sqrt{2}} \Bigg[ \begin{pmatrix} \frac{1}{\sqrt{2}} \\ \dfrac{1}{\sqrt{2}} \end{pmatrix} + \begin{pmatrix} \frac{1}{\sqrt{2}} \\ \dfrac{-1}{\sqrt{2}} \end{pmatrix} \Bigg] = \begin{pmatrix} 1 \\ 0 \end{pmatrix} \\ \dfrac{1}{\sqrt{2}} (Black - White) = \begin{pmatrix} 0 \\ 1 \end{pmatrix} & \dfrac{1}{\sqrt{2}} \Bigg[ \begin{pmatrix} \frac{1}{\sqrt{2}} \\ \dfrac{1}{\sqrt{2}} \end{pmatrix} - \begin{pmatrix} \dfrac{1}{\sqrt{2}} \\ \dfrac{-1}{\sqrt{2}} \end{pmatrix} \Bigg] = \begin{pmatrix} 0 \\ 1 \end{pmatrix} \end{array} \nonumber \]
Hard, Soft, Black and White are measurable properties and the vectors representing them are eigenstates of the Hardness and Color operators with eigenvalues \(\pm\)1. The Identity operator is also given and will be discussed later. Of course, the Hardness and Color operators are just the Pauli spin operators in the z- and x-directions. Later the Taste operator will be introduced; it is the y-direction Pauli spin operator.
Operators
\[Hardness : = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix} \qquad Color : = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \qquad I : = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \nonumber \]
| Eigenvalue +1 | Eigenvalue -1 |
|---|---|
| $$Hardness \cdot Hard = \begin{pmatrix} 1 \\ 0 \end{pmatrix} \qquad \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix} \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \end{pmatrix}$$ | $$Hardness \cdot Soft = \begin{pmatrix} 0 \\ -1 \end{pmatrix} \qquad \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix} \begin{pmatrix} 0 \\ 1 \end{pmatrix} = \begin{pmatrix} 0 \\ -1 \end{pmatrix}$$ |
| $$Color \cdot Black= \begin{pmatrix} 0.707 \\ 0.707 \end{pmatrix} \qquad \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \end{pmatrix} = \begin{pmatrix} 0.707 \\ 0.707 \end{pmatrix}$$ | $$Color \cdot White = \begin{pmatrix} -0.707 \\ 0.707 \end{pmatrix} \qquad \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} \frac{1}{\sqrt{2}} \\ \frac{-1}{\sqrt{2}} \end{pmatrix} = \begin{pmatrix} -0.707 \\ 0.707 \end{pmatrix}$$ |
Another way of showing this is by calculating the expectation (or average) value. Every time the hardness of a hard quon is measured the result is +1. Every time the hardness of a soft quon is measured the result is -1.
The characteristic feature of a quantum computer is its ability to calculate in parallel. How this is accomplished is illustrated in the following one-page tutorial.
A quantum computer exploits quantum mechanical effects such as superpositions, entanglement and interference to perform new types of calculations that are impossible on a classical computer. Quantum computation is therefore nothing less than a distinctly new way of harnessing nature. (Adapted from David Deutsch, The Fabric of Reality, page 195.)
Whereas classical computers perform operations on classical bits, which can be in one of two discrete states, 0 or 1, quantum computers perform operations on quantum bits, or qubits, which can be put into any superposition of two quantum states, |0> and |1>. Peter Pfeifer, McGraw-Hill Encyclopedia of Science and Industry.
The following example demonstrates how a quantum circuit can function as an algorithm for the evaluation of a mathematical function f(x), and how the same algorithm is capable of parallel evaluations of that function.
\[ \left( \begin{array}{ll}{x} & {f(x)} \\ {0} & {1} \\ {1} & {0}\end{array}\right) \quad \begin{array} | x \rangle & \cdots & \bullet & \ldots & \ldots & | x \rangle \\ \; & \; & | & \; & \; & \; \\ | 0 \rangle & \cdots & \oplus & \text{NOT} & \cdots & | f(x) \rangle \end{array} \quad \hat{U}_{f} | x \rangle | 0 \rangle=| x \rangle | f(x) \rangle \nonumber \]
As shown below, when |x> is |0> or |1> the circuit behaves like a classical computer yielding the value of f(x). When |x> is a superposition of |0> and |1> the circuit is a quantum computer, operating on both input values simultaneously in a single pass through the circuit, yielding both values of f(x). Note that in the latter case, the intermediate and final states are entangled Bell superpositions. The Bell states are an essential resource in many quantum information applications.
\[\begin{array} a \text { Input } & \text{Operation} & \text{Intermediate} & \text{Operation} & \text{Output} \\ |0 \rangle | 0 \rangle & \; & |0 \rangle | 0 \rangle & \; & |0 \rangle | 1 \rangle \\ |1 \rangle | 0 \rangle & \xrightarrow{CNOT} & |1 \rangle | 1 \rangle & \xrightarrow{I \otimes NOT} & |1 \rangle | 0 \rangle \\ \frac{1}{\sqrt{2}}[ |0 \rangle+| 1 \rangle ] | 0 \rangle=\frac{1}{\sqrt{2}}[ |0 \rangle | 0 \rangle+| 1 \rangle | 0 \rangle] & \; & \frac{1}{\sqrt{2}}[ |0 \rangle+| 0 \rangle ] | 1 \rangle | 1 \rangle] & \; & \frac{1}{\sqrt{2}}[ |0\rangle+| 1 \rangle ] | 1 \rangle | 0 \rangle] \end{array} \nonumber \]
Haroche and Raimond (pages 94-95 of Exploring the Quantum) describe the latter process as follows: "By superposing the inputs of a computation, one operates the machine 'in parallel', making it compute simultaneously all the values of a function and keeping its state, before any final bit detection is performed, suspended in a coherent superposition of all the possible outcomes." However, as Haroche and Raimond note, on a practical level only one result can be realized for each operation of the circuit because on measurement the superposition created by the circuit collapses to one of the states forming the superposition. Therefore, the exploitation of quantum parallelism for practical purposes such as searches and factorization requires more elaborate quantum circuits than the one presented here.
Truth tables for the quantum circuit:
\[ \mathrm{NOT} \left( \begin{array}{lll}{0} & {\text { to }} & {1} \\ {1} & {\text { to }} & {0}\end{array}\right) \qquad \mathrm{CNOT} \left( \begin{array} a \text{Decimal} & \text{Binary} & \text{to} & \text{Binary} & \text{Decimal} \\ 0 & 00 & \text{to}& 00 & 0 \\ 1 & 01 & \text{to}& 01 & 1 \\ 2 & 10 & \text{to}& 11 & 3 \\ 3 & 11 & \text{to}& 10 & 2 \end{array} \right) \nonumber \]
The following tutorial adds a matrix analysis to the previous example of parallel calculation.
This tutorial deals with quantum function evaluation and parallel computation. The example is taken from pages 94-95 of Exploring the Quantum by Haroche and Raimond. A certain function of x yields the following table of results.
\[ \left( \begin{array}{ccc}{x} & {0} & {1} \\ {f(x)} & {1} & {0}\end{array}\right) \nonumber \]
First we establish that the circuit shown below yields the results given in the table, and then demonstrate that it also carries out a parallel calculation in one step using both input values of x.
\[\begin{array} | x \rangle & \cdots & \bullet & \ldots & \ldots & | x \rangle \\ \; & \; & | & \; & \; & \; \\ | 0 \rangle & \cdots & \oplus & \text{NOT} & \cdots & | f(x) \rangle \end{array} \qquad \text{where, for example}\; | 0 \rangle=\left( \begin{array}{l}{1} \\ {0}\end{array}\right) \quad | 1 \rangle=\left( \begin{array}{l}{0} \\ {1}\end{array}\right) \nonumber \]
The top wire carries the value of x and the bottom wire is initially set to |0 >. After operation of the controlled-NOT and NOT gates, x remains on the top wire while the bottom wire carries the value of the function, f(x). In other words,
\[ \hat{U}_{f} | x \rangle | 0 \rangle=| x \rangle | f(x) \rangle \nonumber \]
The quantum gates in matrix form are:
\[
\mathrm{I} :=\left( \begin{array}{cc}{1} & {0} \\ {0} & {1}\end{array}\right) \quad \mathrm{NOT} :=\left( \begin{array}{cc}{0} & {1} \\ {1} & {0}\end{array}\right) \quad \mathrm{CNOT} :=\left( \begin{array}{cccc}{1} & {0} & {0} & {0} \\ {0} & {1} & {0} & {0} \\ {0} & {0} & {0} & {1} \\ {0} & {0} & {1} & {0}\end{array}\right)
\nonumber \]
Uf (controlled-NOT, followed by a NOT operation on the lower wire) is a reversible operator. Doing it twice in succession on the initial two-qubit state is equivalent to the identity operation.
Kronecker is Mathcad's command for carrying out matrix tensor multiplication. Note that the identity operator is required when a wire is not involved in an operation. In what follows the quantum circuit is constructed, displayed and its reversibility demonstrated. In other words, repeating the circuit is equivalent to the identity operation. Reversibility is a crucial property in quantum computer circuitry.
\[\text{QuantumCircuit} : = \text{kronecker (I, NOT)} \cdot \text{CNOT} \nonumber \]
\[\text{QuantumCircuit} = \left( \begin{array}{cccc}{0} & {1} & {0} & {0} \\ {1} & {0} & {0} & {0} \\ {0} & {0} & {1} & {0} \\ {0} & {0} & {0} & {1}\end{array}\right) \qquad \text{QuantumCircuit}^{2} = \left( \begin{array}{llll}{1} & {0} & {0} & {0} \\ {0} & {1} & {0} & {0} \\ {0} & {0} & {1} & {0} \\ {0} & {0} & {0} & {1}\end{array}\right) \nonumber \]
Given the simplicity of the matrix representing the circuit, the following calculations can easily be done by hand.
| Input | Calculation | Output | |
|---|---|---|---|
| f(0) = 1 | $$ \left( \begin{array}{l}{1} \\ {0}\end{array}\right) \otimes \left( \begin{array}{l}{1} \\ {0}\end{array}\right)=\left( \begin{array}{l}{1} \\ {0} \\ {0} \\ {0}\end{array}\right) $$ | $$\text{QuantumCircuit} \cdot \left( \begin{array}{l}{1} \\ {0} \\ {0} \\ {0}\end{array}\right)=\left( \begin{array}{l}{0} \\ {1} \\ {0} \\ {0}\end{array}\right)$$ | $$ \left( \begin{array}{l}{0} \\ {1} \\ {0} \\ {0}\end{array}\right)=\left( \begin{array}{l}{1} \\ {0}\end{array}\right) \otimes \left( \begin{array}{l}{0} \\ {1}\end{array}\right) $$ |
| f(1) = 0 | $$ \left( \begin{array}{l}{0} \\ {1}\end{array}\right) \otimes \left( \begin{array}{l}{1} \\ {0}\end{array}\right)=\left( \begin{array}{l}{0} \\ {0} \\ {1} \\ {0}\end{array}\right) $$ |
$$\text{QuantumCircuit} \cdot \left( \begin{array}{l}{0} \\ {0} \\ {1} \\ {0}\end{array}\right)=\left( \begin{array}{l}{0} \\ {0} \\ {1} \\ {0}\end{array}\right)$$ | $$ \left( \begin{array}{l}{0} \\ {0} \\ {1} \\ {0}\end{array}\right)=\left( \begin{array}{l}{0} \\ {1}\end{array}\right) \otimes \left( \begin{array}{l}{1} \\ {0}\end{array}\right) $$ |
These calculations demonstrate that the quantum circuit is a valid algoritm for the calculation of f(x). We now demonstrate parallel computation by putting |x> in a balanced superposition of |0> and |1>. As shown below, the operation of the circuit yields a superposition of the previous results. The function has been evaluated for both values of x in a single pass through the circuit.
\[
\frac{1}{\sqrt{2}} \left( \begin{array}{l}{1} \\ {1}\end{array}\right) \otimes \left( \begin{array}{l}{1} \\ {0}\end{array}\right)=\frac{1}{\sqrt{2}} \left( \begin{array}{l}{1} \\ {0} \\ {1} \\ {0}\end{array}\right)
\nonumber \]
\[
\text{QuantumCircuit} \cdot \frac{1}{\sqrt{2}} \cdot \left( \begin{array}{l}{1} \\ {0} \\ {1} \\ {0}\end{array}\right)=\left( \begin{array}{c}{0} \\ {0.707} \\ {0.707} \\ {0}\end{array}\right)
\nonumber \]
\[
\frac{1}{\sqrt{2}} \cdot \left( \begin{array}{l}{0} \\ {1} \\ {1} \\ {0}\end{array}\right)=\frac{1}{\sqrt{2}} \cdot\left[\left( \begin{array}{l}{0} \\ {1} \\ {0} \\ {0}\end{array}\right)+\left( \begin{array}{l}{0} \\ {0} \\ {1} \\ {0}\end{array}\right)=\frac{1}{\sqrt{2}} \cdot\left[\left( \begin{array}{l}{1} \\ {0}\end{array}\right) \cdot \left( \begin{array}{l}{0} \\ {1}\end{array}\right)+\left( \begin{array}{l}{0} \\ {1}\end{array}\right) \cdot \left( \begin{array}{l}{1} \\ {0}\end{array}\right)\right]\right.
\nonumber \]
Haroche and Raimond describe this process as follows: "By superposing the inputs of a computation, one operates the machine 'in parallel', making it compute simultaneously all the values of a function and keeping its state, before any final bit detection is performed, suspended in a coherent superposition of all the possible outcomes."
In summary, simple calculations have demonstrated how a quantum circuit can function as an algorithm for the evaluation of a mathematical function, and how the same circuit is capable of parallel evaluations of that function.
\[\begin{array} a \text { Input } & \text{Operation} & \text{Intermediate} & \text{Operation} & \text{Output} \\ |00 \rangle & \; & |00 \rangle & \; & |01 \rangle \\ |10 \rangle & \xrightarrow{CNOT} & |11 \rangle & \xrightarrow{I \otimes NOT} & |10 \rangle \\ \frac{1}{\sqrt{2}}[ |0 \rangle+| 1 \rangle ] | 0 \rangle=\frac{1}{\sqrt{2}}[ |0 0 \rangle+| 1 0 \rangle] & \; & \frac{1}{\sqrt{2}}[ |0 0 \rangle ]+ | 1 1 \rangle] & \; & \frac{1}{\sqrt{2}}[ |01 \rangle ]+ | 1 0 \rangle] \end{array} \nonumber \]
However, as Haroche and Raimond note, on a practical level only one result can be realized for each operation of the circuit because on measurement the superposition created by the circuit collapses to one of the states forming the superposition. This is simulated with projection operators (|0><0| and |1><1|) on both registers for the four possible measurement outcomes for each value of x.
\[f(0) = 0 \qquad \Bigg[ \Bigg| \text{kronecker} \left[\left( \begin{array}{l}{1} \\ {0}\end{array}\right) \cdot \left( \begin{array}{l}{1} \\ {0}\end{array}\right)^{\mathrm{T}}, \left( \begin{array}{l}{1} \\ {0}\end{array}\right) \cdot \left( \begin{array}{l}{1} \\ {0}\end{array}\right)^{\mathrm{T}}\right] \cdot \text{QuantumCircuit} \cdot \frac{1}{\sqrt{2}} \begin{pmatrix} 1 \\ 0 \\ 1 \\ 0 \end{pmatrix} \Bigg| \Bigg]^{2} = 0 \nonumber \]
\[f(0) = 1 \qquad \Bigg[ \Bigg| \text{kronecker} \left[\left( \begin{array}{l}{1} \\ {0}\end{array}\right) \cdot \left( \begin{array}{l}{1} \\ {0}\end{array}\right)^{\mathrm{T}}, \left( \begin{array}{l}{0} \\ {1}\end{array}\right) \cdot \left( \begin{array}{l}{0} \\ {1}\end{array}\right)^{\mathrm{T}}\right] \cdot \text{QuantumCircuit} \cdot \frac{1}{\sqrt{2}} \begin{pmatrix} 1 \\ 0 \\ 1 \\ 0 \end{pmatrix} \Bigg| \Bigg]^{2} = 0.5 \nonumber \]
\[f(1) = 0 \qquad \Bigg[ \Bigg| \text{kronecker} \left[\left( \begin{array}{l}{0} \\ {1}\end{array}\right) \cdot \left( \begin{array}{l}{0} \\ {1}\end{array}\right)^{\mathrm{T}}, \left( \begin{array}{l}{1} \\ {0}\end{array}\right) \cdot \left( \begin{array}{l}{1} \\ {0}\end{array}\right)^{\mathrm{T}}\right] \cdot \text{QuantumCircuit} \cdot \frac{1}{\sqrt{2}} \begin{pmatrix} 1 \\ 0 \\ 1 \\ 0 \end{pmatrix} \Bigg| \Bigg]^{2} = 0.5 \nonumber \]
\[f(1) = 1 \qquad \Bigg[ \Bigg| \text{kronecker} \left[\left( \begin{array}{l}{0} \\ {1}\end{array}\right) \cdot \left( \begin{array}{l}{0} \\ {1}\end{array}\right)^{\mathrm{T}}, \left( \begin{array}{l}{0} \\ {1}\end{array}\right) \cdot \left( \begin{array}{l}{0} \\ {1}\end{array}\right)^{\mathrm{T}}\right] \cdot \text{QuantumCircuit} \cdot \frac{1}{\sqrt{2}} \begin{pmatrix} 1 \\ 0 \\ 1 \\ 0 \end{pmatrix} \Bigg| \Bigg]^{2} = 0 \nonumber \]
As Haroche and Raimond write, "It is, however, one thing to compute potentially at once all the values of f(x) and quite another to be able to exploit this quantum parallelism and extract from it more information than from a mundane classical computation. The final stage of information acquisition must always be a measurement." Therefore, the exploitation of quantum parallelism for practical purposes such as searches and factorization requires more elaborate quantum circuits than the one presented here.
Truth tables for quantum circuit elements:
\[ \mathrm{Identity} \left( \begin{array}{lll}{0} & {\text { to }} & {0} \\ {1} & {\text { to }} & {1}\end{array}\right) \qquad \mathrm{NOT} \left( \begin{array}{lll}{0} & {\text { to }} & {1} \\ {1} & {\text { to }} & {0}\end{array}\right) \qquad \mathrm{CNOT} \left( \begin{array} a \text{Decimal} & \text{Binary} & \text{to} & \text{Binary} & \text{Decimal} \\ 0 & 00 & \text{to}& 00 & 0 \\ 1 & 01 & \text{to}& 01 & 1 \\ 2 & 10 & \text{to}& 11 & 3 \\ 3 & 11 & \text{to}& 10 & 2 \end{array} \right) \nonumber \]
Solving systems of equations is a relatively routine task for a quantum circuit.
This tutorial demonstrates the solution of two linear simultaneous equation using a quantum circuit. The circuit is taken from arXiv:1302.1210. See this reference for details on the experimental implementation of the circuit and also for a discussion of the potential of quantum solutions for systems of equations. Two other sources (arXiv:1302.1946 and 1302.4310) provide alternative quantum circuits and methods of implementation.
First we consider the conventional method of solving systems of linear equation for a particular matrix A and three different |b> vectors.
\[
A | x \rangle=| b \rangle \qquad | x \rangle=A^{-1} | b \rangle
\nonumber \]
\[
A :=\left( \begin{array}{cc}{1.5} & {0.5} \\ {0.5} & {1.5}\end{array}\right) \qquad b_{1} : =\frac{1}{\sqrt{2}} \left( \begin{array}{l}{1} \\ {1}\end{array}\right) \qquad b_{2} : =\frac{1}{\sqrt{2}} \left( \begin{array}{l}{1} \\ {-1}\end{array}\right) \qquad b_{3} :=\left( \begin{array}{l}{1} \\ {0}\end{array}\right)
\nonumber \]
\[
A^{-1} \cdot b_{1}=\left( \begin{array}{c}{0.354} \\ {0.354}\end{array}\right) \quad A^{-1} \cdot b_{2}=\left( \begin{array}{c}{0.707} \\ {-0.707}\end{array}\right) \quad A^{-1} \cdot B_{3}=\left( \begin{array}{c}{0.75} \\ {-0.25}\end{array}\right)
\nonumber \]
The following quantum circuit (see arXiv:1302.1210) generates the same solutions.
\[\begin{array} a |b \rangle & \rhd & R & \bullet & R^{T} & \rhd & |x \rangle \\ \; & \; & \; & | & \; & \; & \; \\ |1 \rangle & \rhd & \cdots & Ry( \theta ) & M_{1} & \rhd & |1 \rangle \end{array} \nonumber \]
In this circuit, R is the matrix of eigenvectors of matrix A and RT its transpose. The last step on the bottom wire is the measurement of |1>, which is represented by the projection operator M1. The identity operator is required for cases in which a quantum gate operation is occurring on one wire and no operation is occurring on the other wire.
\[R : = \text{eigenvecs(A)} \quad \mathrm{R}=\left( \begin{array}{ll}{0.707} & {-0.707} \\ {0.707} & {0.707}\end{array}\right) \quad \mathrm{R}^{\mathrm{T}}=\left( \begin{array}{cc}{0.707} & {0.707} \\ {-0.707} & {0.707}\end{array}\right) \quad \mathrm{M}_{1} :=\left( \begin{array}{ll}{0} & {0} \\ {0} & {1}\end{array}\right) \longleftarrow \left( \begin{array}{l}{0} \\ {1}\end{array}\right) \cdot \left( \begin{array}{ll}{0} & {1}\end{array}\right) \quad \mathrm{I}=\left( \begin{array}{ll}{1} & {0} \\ {0} & {1}\end{array}\right) \nonumber \]
The controlled rotation, CR(\(\theta\)), is the only two-qubit gate in the circuit. The rotation angle required is determined by the ratio of the eigenvalues of A as shown below.
\[
\mathrm{CR}(\theta) :=\left( \begin{array}{cccc}{1} & {0} & {0} & {0} \\ {0} & {1} & {0} & {0} \\ {0} & {0} & {\cos \left(\frac{\theta}{2}\right)} & {-\sin \left(\frac{\theta}{2}\right)} \\ {0} & {0} & {\sin \left(\frac{\theta}{2}\right)} & {\cos \left(\frac{\theta}{2}\right)}\end{array}\right) \qquad \text{eigenvals(A)} = \begin{pmatrix} 2 \\ 1 \end{pmatrix} \qquad \theta : = -2 \cdot \text{acos} \left(\dfrac{1}{2}\right)
\nonumber \]
The input (|b>|1>) and output (|x>|1>) states are expressed in tensor format. Kronecker is Mathcad's command for the tensor product of matrices.
| Input |b>|1> | Quantum Circuit | Output |x>|1> |
|---|---|---|
| |1>" class="lt-chem-135493">$$\begin{array} a \dfrac{1}{\sqrt{2}} \left( \begin{array}{l}{1} \\ {1}\end{array}\right) \cdot \left( \begin{array}{l}{0} \\ {1}\end{array}\right)=\dfrac{1}{\sqrt{2}} \left( \begin{array}{l}{0} \\ {1} \\ {0} \\ {1}\end{array}\right) \quad & \text{kronecker} \left( R^{T}, M_{1} \right) \cdot \mathrm{CR} (\theta) \cdot \text{kronecker} (R,I) \cdot \dfrac{1}{\sqrt{2}} \cdot \left(\begin{array}{l}{0} \\ {1} \\ {0} \\ {1}\end{array}\right)= \left( \begin{array}{c}{0} \\ {0.354} \\ {0} \\ {0.354}\end{array}\right) \quad & \left( \begin{array}{c}{0.354} \\ {0.354}\end{array}\right) \cdot \left( \begin{array}{l}{0} \\ {1}\end{array}\right) \\ \dfrac{1}{\sqrt{2}} \cdot \left( \begin{array}{c}{1} \\ {-1}\end{array}\right) \cdot \left( \begin{array}{l}{0} \\ {1}\end{array}\right)=\dfrac{1}{\sqrt{2}} \left( \begin{array}{c}{0} \\ {1} \\ {0} \\ {-1}\end{array}\right) \quad & \text{kronecker} \left( R^{T}, M_{1} \right) \cdot \mathrm{CR} (\theta) \cdot \text{kronecker} (R,I) \cdot \dfrac{1}{\sqrt{2}} \cdot \left(\begin{array}{l}{0} \\ {1} \\ {0} \\ {-1}\end{array}\right)= \left( \begin{array}{c}{0} \\ {0.707} \\ {0} \\ {-0.707}\end{array}\right) \quad & \left( \begin{array}{c}{0.707} \\ {-0.707}\end{array}\right) \cdot \left( \begin{array}{l}{0} \\ {1}\end{array}\right) \\ \left( \begin{array}{l}{1} \\ {0}\end{array}\right) \cdot \left( \begin{array}{l}{0} \\ {1}\end{array}\right)=\left( \begin{array}{l}{0} \\ {1} \\ {0} \\ {0}\end{array}\right) \quad & \text{kronecker} \left( R^{T}, M_{1} \right) \cdot \mathrm{CR} (\theta) \cdot \text{kronecker} (R,I) \cdot \left(\begin{array}{l}{0} \\ {1} \\ {0} \\ {0}\end{array}\right)= \left( \begin{array}{c}{0} \\ {0.75} \\ {0} \\ {-0.25}\end{array}\right) \quad & \left( \begin{array}{c}{0.75} \\ {-0.25}\end{array}\right) \cdot \left( \begin{array}{l}{0} \\ {1}\end{array}\right) \end{array}$$ | ||