8.65: A Brief Introduction to the Quantum Computer

Last updated
Save as PDF

Page ID: 148435

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

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.

\[ \begin{matrix} \begin{pmatrix} \text{x} & \text{f(x)} \\ 0 & 1 \\ 1 & 0 \end{pmatrix} & \begin{matrix} |x \rangle & \cdots & \cdot & \cdots & \cdots & | x \rangle \\ ~ & ~ & | \\ |0 \rangle & \cdots & \oplus & \fbox{NOT} & \cdots & | f(x) \rangle \end{matrix} & \hat{U}_f | x \rangle |0 \rangle = |x \rangle f(x) \rangle \end{matrix} \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{matrix} \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{ \text{CNOT}} & |1 \rangle |1 \rangle & \xrightarrow{ \text{I} \otimes \text{NOT}} & |1 \rangle |0 \rangle \\ \frac{1}{ \sqrt{2}} \left[ |0 \rangle + |1 \rangle \right] = \frac{1}{ \sqrt{2}} \left[ |0 \rangle |0 \rangle + |1 \rangle |0 \rangle \right] & ~ & \frac{1}{ \sqrt{2}} \left[ |0 \rangle |0 \rangle + |1 \rangle |1 \rangle \right] & ~ & \frac{1}{ \sqrt{2}} \left[ |0 \rangle |1 \rangle + |1 \rangle |0 \rangle \right] \end{matrix} \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:

\[ \begin{matrix} \text{NOT} & \begin{pmatrix} 0 \text{ to } 1 \\ 1 \text{ to } 0 \end{pmatrix} & \text{CNOT} \begin{pmatrix} \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{pmatrix} \end{matrix} \nonumber \]