Quantum computing is evolving so rapidly that it forces us to revisit, rewrite, and update the foundations of the theory. Basic Quantum Algorithms revisits the earliest quantum algorithms. The journey began in 1985 with Deutsch attempting to evaluate a function at two domain points simultaneously. Then, in 1992, Deutsch and Jozsa created a quantum algorithm that determines whether a Boolean function is constant or balanced. The following year, Bernstein and Vazirani realized that the same algorithm could be used to identify a specific Boolean function within a set of linear Boolean functions. In 1994, Simon introduced a novel quantum algorithm that determined whether a function was one-to-one or two-to-one exponentially faster than any classical algorithm for the same problem. That same year, Shor developed two groundbreaking quantum algorithms for integer factoring and calculating discrete logarithms, posing a threat to the widely used cryptography methods. In 1995, Kitaev proposed an alternative version of Shor's algorithms that proved valuable in numerous other applications. The following year, Grover devised a quantum search algorithm that was quadratically faster than its classical equivalent.  With an emphasis on the circuit model, this work provides a detailed description of all these remarkable algorithms.

CHAPTER: INTRODUCTION

Quantum algorithms are a rapidly evolving subarea of quantum computing, not only in terms of new algorithms, but also in applications and implementations. The basic algorithms serve as the pillars of this new edifice. The construction began with a change in the rules of the game. Instead of storing information in bits, which take either zero or one, we are allowed to store information in qubits, the state of which is a superposition of zeroes and ones. The rules based on classical mechanics were replaced by rules based on quantum mechanics.

The first breakthrough came with Deutsch's 1985 proposal to evaluate a one-bit Boolean function at two points simultaneously using quantum parallelism, which exploits the superposition of zeros and ones. At the time, a framework for creating new algorithms was missing, which Deutsch established in 1989 with the introduction of quantum gates and circuits, taking the place of well-known classical gates like AND, OR, and NOT.

In 1992, Deutsch and Jozsa developed an algorithm to determine if a Boolean function is balanced or constant, giving momentum to the field of quantum algorithms and inspiring the development of oracle-based algorithms. The goal is to find a function's hidden property with as few queries as possible.

Bernstein and Vazirani observed in 1993 that the Deutsch-Jozsa algorithm could be used to identify a specific Boolean function within a set of linear Boolean functions.  The Bernstein-Vazirani algorithm outperforms its classical counterpart without exploiting entanglement, relying solely on quantum parallelism.

The momentum continued to grow as Simon published a quantum algorithm in 1994 that exponentially outperformed classical algorithms in determining if a function is one-to-one or two-to-one. This algorithm leveraged maximum entanglement and had applications in finding hidden subgroups within specific classes of groups.

In 1994, Shor developed two groundbreaking quantum algorithms for factoring composite integers and calculating discrete logarithms, which posed a significant threat to the cryptography methods widely used today. Shor's algorithms brought quantum computing to the spotlight, and since then, the field has been growing at an astonishing rate. Shor's algorithm can also be formulated as an oracle-based algorithm with a function that is periodic. The goal is to find the period by evaluating the function as few as possible. Finding periods is a task suited for the Fourier transform, which, although it has a complexity of $O(N \log N)$, where $N$ represents the data size, proves useful in classical algorithms. In the quantum domain, the Fourier transform is implemented with $O(\log^2 N)$ universal gates, and it is the quantum superposition that works wonders.

In 1995, Kitaev introduced another version of Shor's algorithms after developing a quantum algorithm for phase estimation. Given a unitary operator and one of its eigenvectors, the algorithm efficiently finds the corresponding eigenvalue, which is totally characterized by its phase. Kitaev's algorithm proved useful for other applications, such as quantum counting.

Grover focused on unsorted databases in 1996 and developed a quantum algorithm that could locate an item quadratically faster than classical searching.  Grover's algorithm can also be formulated as an oracle-based algorithm with a Boolean function that is constant except for a single point in the domain. The goal is to find that point by evaluating the function as few as possible. When it is written as a black-box algorithm, it is clear that Grover's algorithm has wide applicability.

Basic Quantum Algorithms details the remarkable contributions mentioned above. There is no hope if we don't use the correct language: Mathematics, more specifically, linear algebra. Concepts like quantum superposition and entanglement have a precise definition when we use linear algebra. Measurements are described by projectors, gates by unitary operators, and qubits by vectors. Projectors, unitary operators, and vectors are words of the linear algebra language. When describing quantum algorithms or anything related to quantum, it is better to use mathematics because without it someone will probably utter nonsense.

Basic Quantum Algorithms follows as much as possible the historical ordering, which is the order of increasing complexity. We feel like climbing steps with increasing heights, strengthening muscles, and preparing for the challenge of understanding complex quantum algorithms. Each chapter is designed to be as independent as possible, allowing readers familiar with some algorithms to skip certain sections.

Lastly, do not hesitate in contacting the author () if there are errors or any problems in terms of imprecision or missing citations. Suggestions are also welcome.

§.§ Acknowledgments

The author thanks P.H.G. Lugão for suggesting improvements.

CHAPTER: QUANTUM CIRCUITS

The goal of this Chapter is to define the concepts of qubit, logic gate, and quantum circuit. Before that, we briefly review key facts of linear algebra [2, 64] using Dirac notation from the beginning. Part of this material was published in the tutorial [50]. References for this Section are [54] and [67]. Additional references for linear algebra for quantum computing are Appendix A of [49] and Section 2.1 of [45].

§ REVIEW OF LINEAR ALGEBRA USING DIRAC NOTATION

There are several notations to show that a variable $v$ is a vector, for example, $\vec{v}$, $\textbf{v}$, and so on. In quantum computing, the most used is Dirac's: $\ket{v}$. A sequence of vectors is denoted by $\ket{v_0}$, $\ket{v_1}$, $\ket{v_2}$ and so forth. It is very common to abuse this notation and denote the same sequence as $\ket{0}$, $\ket{1}$, $\ket{2}$ and so on.

The canonical basis of a two-dimensional vector space has two vectors, denoted by $\{\ket{0},\ket{1}\}$ in Dirac notation, where $\ket{0}$ and $\ket{1}$ have the following representation

\[
\ket{0}=\begin{pmatrix} 1 \\ 0 \end{pmatrix} \,\,\,\text{ and }\,\,\,
\ket{1}=\begin{pmatrix} 0 \\ 1 \end{pmatrix}.
\]

These vectors have two entries or components, unit length, and are orthogonal. Then, this basis is orthonormal. It is called the canonical basis in linear algebra and the computational basis in quantum computing. Note that $\ket{0}$ is not the null vector, but the first vector of the canonical basis. All entries of the null vector are equal to 0. In the two-dimensional case, it is

\[
\begin{pmatrix} 0 \\ 0 \end{pmatrix}
\]

without any special denomination in Dirac notation.

A generic vector in a two-dimensional vector space is obtained via the linear combination of the basis vectors,

\[
\ket{\psi}=\alpha\ket{0}+\beta\ket{1},
\]

where $\alpha$ and $\beta$ are complex numbers. These numbers are the entries of vector $\ket{\psi}$, as can be seen from the notation

\begin{equation*}\label{eq:psi}
\ket{\psi}=\begin{pmatrix} \alpha \\ \beta \end{pmatrix}.
\end{equation*}

The dual vector (with respect to $\ket{\psi}$) is denoted by $\bra{\psi}$ and is obtained by transposing $\ket{\psi}$ and conjugating each entry. Using the previous equation, we obtain

\begin{equation*}\label{eq:brapsi}
\bra{\psi}=\begin{pmatrix} \alpha^* & \beta^* \end{pmatrix},
\end{equation*}

which can be written as

\[
\bra{\psi}=\alpha^*\bra{0}+\beta^*\bra{1},
\]

\[
\bra{0}=\begin{pmatrix} 1& 0 \end{pmatrix} \,\,\,\text{ and }\,\,\,
\bra{1}=\begin{pmatrix} 0 & 1 \end{pmatrix}.
\]

The dual vector $\bra{\psi}$ is a $1\times 2$ matrix and vector $\ket{\psi}$ is a $2\times 1$ matrix. At this point, we introduce the dagger symbol, denoted by $\dagger$, which is the notation for the conjugate transpose vector (transpose the vector and then conjugate each entry or vice versa). Then, we may write $\bra{\psi}=\ket{\psi}^\dagger$ and $\ket{\psi}=\bra{\psi}^\dagger$. Two daggers one after the other work as the identity operation.

Suppose that $\ket{\psi_1}$ and $\ket{\psi_2}$ are two-dimensional vectors given by

\[
\ket{\psi_1}=\begin{pmatrix} \alpha \\ \beta \end{pmatrix} \,\,\,\,\text{ and }\,\,\,\,
\ket{\psi_2}=\begin{pmatrix} \gamma \\ \delta \end{pmatrix}.
\]

The inner product of two vectors $\ket{\psi_1}$ and $\ket{\psi_2}$ is a complex number denoted by $\braket{\psi_1}{\psi_2}$ and defined as the matrix product of the dual vector $\bra{\psi_1}$ by $\ket{\psi_2}$, as follows

\begin{equation*}
\braket{\psi_1}{\psi_2}=\begin{pmatrix} \alpha^* & \beta^* \end{pmatrix}\begin{pmatrix} \gamma \\ \delta \end{pmatrix}=\alpha^*\gamma+\beta^*\delta.
\end{equation*}

In Dirac notation, the calculation of the inner product is performed by distributing the matrix product over the sum of vectors, as follows

\begin{equation*}
\braket{\psi_1}{\psi_2}=\big(\alpha^*\bra{0}+\beta^*\bra{1}\big)\cdot \big(\gamma\ket{0}+\delta\ket{1}\big) =\alpha^*\gamma\,\braket{0}{0}+\beta^*\delta\,\braket{1}{1}=\alpha^*\gamma+\beta^*\delta.
\end{equation*}

The norm of vector $\ket{\psi_1}$ is denoted by $\|\,\ket{\psi_1}\,\|$ and defined as

\begin{equation*}
\|\,\ket{\psi_1}\,\|=\sqrt{\braket{\psi_1}{\psi_1}}=\sqrt{|\alpha|^2+|\beta|^2},
\end{equation*}

where $|\alpha|$ is the absolute value of $\alpha$, that is

\[
|\alpha|=\sqrt{\alpha\cdot \alpha^*}.
\]

If $\alpha=a+b\,\ii $, where $\ii$ is the imaginary unit $(\ii =\sqrt{-1})$, $a$ is the real part and $b$ is the imaginary part, then

\[|\alpha|=\sqrt{(a+b\,\ii )\cdot (a-b\,\ii )}=\sqrt{a^2+b^2}.
\]

A complex number $\alpha$ such that $|\alpha|=1$ is called a unit complex number and can be written as $\e^{\ii\theta}=\cos\theta+\ii\sin\theta$, where $\theta$ is an angle.
In real vector spaces, the inner product is called scalar product and is given by

\begin{equation*}
\braket{\psi_1}{\psi_2}=\|\,\ket{\psi_1}\|\,\,\|\,\ket{\psi_2}\|\,\cos\theta,
\end{equation*}

where $\theta$ is the angle between vectors $\ket{\psi_1}$ and $\ket{\psi_2}$.

Using these definitions, we can show that the basis $\{\ket{0},\ket{1}\}$ is orthonormal, that is, vectors $\ket{0}$ and $\ket{1}$ are orthogonal and have norm 1, that is

\begin{eqnarray*}
\braket{0}{0} = 1,\,\,\,\,\,\,\,\,
\braket{0}{1} = 0,\,\,\,\,\,\,\,\,
\braket{1}{0} = 0,\,\,\,\,\,\,\,\,
\braket{1}{1} = 1.
\end{eqnarray*}

An algebraic way of denoting orthonormality and of compacting the last four equations into one is

\[
\braket{k}{\ell}=\delta_{k\ell},
\]

where $k$ and $\ell$ are bits and $\delta_{k\ell}$ is the Kronecker delta, defined as

\[
\delta_{k\ell}=\begin{cases} 1, \text{ if }k=\ell, \\ 0, \text{ if }k\neq \ell. \end{cases}
\]

§ QUBIT AND SUPERPOSITION

The basic memory unit of a classical computer is the bit, which takes on the values 0 or 1. Usually, the bit is implemented using two distinct voltages, following the convention that null or low voltage represents bit 0 and high voltage represents bit 1. To determine whether the output is bit 0 or 1 at the end of the computation, it is necessary to measure the voltage.

The basic memory unit of a quantum computer is the qubit, which also assumes, at the end of the computation, 0 or 1. The qubit is implemented using an electric current in a small superconductor, following the convention that clockwise current represents 0 and counter-clockwise current represents 1, or vice versa. The difference from the classical device happens during the computation since the qubit allows the simultaneous coexistence of 0 and 1. During the computation, or before the measurement, the state of a qubit is represented by a norm-1 two-dimensional vector and the states of a qubit corresponding to 0 and 1 are $\ket{0}$ and $\ket{1}$. The definition of state is a vector of norm 1 in a complex vector space endowed with the inner product presented in the previous Section.[A finite-dimensional vector space with an inner product is a Hilbert space.] The state can be thought of as the “value” of the qubit before the measurement. Quantum coexistence is represented mathematically by a linear combination of orthonormal vectors as follows

\[
\ket{\psi}=\alpha\ket{0}+\beta\ket{1},
\]

where $\alpha$ and $\beta$ are complex numbers that obey the constraint

\[
\]

The state of the qubit is vector $\ket{\psi}$ of norm 1 with the entries $\alpha$ and $\beta$. The complex numbers $\alpha$ and $\beta$ are the amplitudes of the state $\ket{\psi}$.

The coexistence of bits 0 and 1 cannot be implemented in a classical device, since it is not possible to have low and high voltage simultaneously, as everyone knows. In quantum mechanics, though hard to believe, it is possible to have a quantum system (usually microscopic) with low and high voltage at the same time. This coexistence can only be completely maintained if the quantum system is fully isolated from the surrounding macroscopic environment. When we measure the quantum system to determine the voltage value, the measuring device inevitably affects the voltage, outputting a stochastic result, which is either low or high voltage, similar to the classical bit. In other words, coexistence is only maintained when no one (and no thing) is trying to determine whether the voltage is high or low. Note that quantum mechanics is a scientific theory, meaning its laws and results can be tested objectively in laboratories. In addition, unnecessary laws and statements are promptly discarded. Therefore, the statement “coexistence is only maintained when the system is isolated” has practical consequences and is a statement that has been tested and re-tested for over 100 years in thousands of quantum mechanics laboratories worldwide. On the other hand, alternative theories that are more classically palatable, which could help in understanding or visualizing the quantum superposition, have been ruled out by experimental tests.

From a computational point of view, we have a qubit in superposition and we use this feature in a circuit. For example, the circuit

\[
\Qcircuit @C=2.3em @R=1.9em {
\lstick{\ket{\psi}}       &\qw & \meter & \rstick{
0 \textrm{ or }
\]

tells us that the initial “value” of the qubit is $\ket{\psi}$ and this information is conveyed unchanged from left to right until a measurement is performed, as shown by the meter (the display of a voltmeter). The measurement outputs 0 or 1. Classical information is conveyed by a double wire. If the state of the qubit is $\ket{\psi}=\ket{0}$, a measurement will necessarily output 0 and if the state is $\ket{1}$, a measurement will necessarily output 1. In the general case, if the state is $\alpha\ket{0}+\beta\ket{1}$, a measurement will return 0 with probability $|\alpha|^2$ or 1 with probability $|\beta|^2$, as shown in the circuit

\[
\Qcircuit @C=2.3em @R=1.9em {
\lstick{\alpha\ket{0}+\beta\ket{1}}       &\qw & \meter & \rstick{\begin{cases} 0, \text{ with probability }|\alpha|^2, \\ 1, \text{ with probability }|\beta|^2. \end{cases}}\cw
\]

The output can be depicted by a histogram of the probability distribution.
It is important to repeat the fact that $\alpha$ and $\beta$ are called amplitudes of the state $\alpha\ket{0}+\beta\ket{1}$ and are numbers that can be negative and may have an imaginary part. On the other hand, $|\alpha|^2$ and $|\beta|^2$ are positive real numbers in the interval $[0,1]$ and are called probabilities. A careless interchange between amplitudes and probabilities creates unforgivable errors.

Bloch sphere and the location of states $\ket{0}$, $\ket{1}$, $\ket{\pm}$, and $\ket{\pm \ii}$. An arbitrary state $\ket{\psi}$ is shown with spherical angles $\theta$ and $\varphi$.

The state of a qubit can be characterized by two angles $\theta$ and $\varphi$ as follows

\begin{equation*}
\ket{\psi}=\cos\frac{\theta}{2}\,\ket{0} +  \textrm{e}^{\ii \varphi}\sin\frac{\theta}{2}\, \ket{1},
\end{equation*}

where $0\le \theta \le \pi$ and $0\le \varphi < 2\pi$. This notation shows that there is a one-to-one correspondence between the set of states of a qubit and points on the surface of a sphere of radius 1, called Bloch sphere. The angles $\theta$ and $\varphi$ are spherical angles that describe the location of the state $\ket{\psi}$, as shown in Fig. <ref>. A point on the Bloch sphere is described by a three-dimensional vector with real entries

\begin{equation*}
\begin{pmatrix}
\sin \theta \cos\varphi \\
\sin \theta \sin\varphi \\
\cos \theta \\
\end{pmatrix}.
\end{equation*}

The locations on the Bloch sphere of states $\ket{0}$ and $\ket{1}$, whose spherical angles are $(\theta,\varphi)=(0,0)$ and $(\theta,\varphi)=(\pi,0)$, are pinpointed in Fig. <ref>. The locations of states

\begin{eqnarray*}
\ket{\pm}&=&\frac{\ket{0}\pm\ket{1}}{\sqrt{2}},\\
\ket{\pm \ii}&=&\frac{\ket{0}\pm \ii\ket{1}}{\sqrt{2}}
\end{eqnarray*}

are determined after figuring out the spherical angles, which are $(\theta,\varphi)$ = $(\pi/2,\pi/2 \mp \pi/2)$ and $(\theta,\varphi)$ = $(\pi/2,\pm \pi/2)$, respectively.[Do not try to understand $\pm$ simultaneously because our mind enters in undesired, superposed, entangled states. Please address first the upper sign of all expressions. Then, address the lower sign.] Then, their locations are the intersections of the $x$-axis with the Bloch sphere, and $y$-axis with the Bloch sphere.

If we have an arbitrary 1-qubit state $\alpha\ket{0}+\beta\ket{1}$ and we want to find the spherical angles $\theta$ and $\varphi$, the first thing to do is to write $\alpha$ and $\beta$ as $r_1\e^{\ii\varphi_1}$ and $r_2\e^{\ii\varphi_2}$, respectively, where $r_1=|\alpha|$ and $r_2=|\beta|$. Now we multiply the state by $\e^{-\ii\varphi_1}$ to obtain $r_1\ket{0}+\e^{\ii(\varphi_2-\varphi_1)}r_2\ket{1}$. Then, we take $\varphi=\varphi_2-\varphi_1$ and $\theta=2\arccos r_1$. Note that $r_2=\sin(\theta/2)$ because $r_1^2+r_2^2=1$. There is no problem in multiplying the state by a unit complex number such as $\e^{-\ii\varphi_1}$ because in quantum mechanics two quantum states that differ by a global factor are considered equivalent and have the same location on the Bloch sphere. The global factor must be a unit complex number and is usually called global phase factor.

§ SINGLE-QUBIT GATES

A single-qubit gate is a two-dimensional unitary square matrix. A matrix $U$ is unitary if multiplying $U$ by an arbitrary norm-1 vector results in a norm-1 vector. Formally, suppose that $\ket{\psi'}=U\ket{\psi}$, where $\ket{\psi}$ is a norm-1 two-dimensional vector. If $U$ is a unitary matrix, then $\ket{\psi'}$ will have norm 1. For example, the Hadamard matrix

H=\frac{1}{\sqrt 2}\begin{bmatrix}
1 & \,\,\,1 \\
1 & -1 \\
\end{bmatrix}

is unitary. Therefore, the multiplication of $H$ by the basis vectors has to result in norm-1 vectors. In fact,

\[
H\ket{0}\,\,=\,\,H\begin{pmatrix} 1 \\ 0 \end{pmatrix}\,\,=\,\,\frac{1}{\sqrt 2}\begin{pmatrix} 1 \\ 1 \end{pmatrix}\,\,=\,\,\frac{1}{\sqrt 2}\ket{0}+\frac{1}{\sqrt 2}\ket{1}.
\]

The resulting vector has norm 1. We denote this vector by $\ket{+}$, that is

\[\ket{+}=\frac{1}{\sqrt 2}\ket{0}+\frac{1}{\sqrt 2}\ket{1}.
\]

Multiplying $H$ by $\ket{1}$ yields vector $\ket{-}$ defined as

\[
\ket{-}=\frac{1}{\sqrt 2}\ket{0}-\frac{1}{\sqrt 2}\ket{1},
\]

which also has norm 1. These calculations are important because we need to learn the output of the gate. If the input is $\ket{0}$ then the output is $\ket{+}$. If the input is $\ket{1}$, the output is $\ket{-}$. If the input is a superposition $\alpha\ket{0}+\beta\ket{1}$, the output is the superposition of $\ket{+}$ and $\ket{-}$ with the same amplitudes, $\alpha\ket{+}+\beta\ket{-}$, because we use the linearity property of the gate, that is, instead of thinking that $H$ is a matrix, we use that $H$ is a linear operator and if $H$ is applied to a linear combination of vectors $\ket{0}$ and $\ket{1}$ with amplitudes $\alpha$ and $\beta$, the result is a linear combination of $H\ket{0}$ and $H\ket{1}$ with the same amplitudes $\alpha$ and $\beta$. While we could avoid this abstract perspective, when multiplying a matrix by a sum of vectors, we must distribute the multiplication over the sum of vectors.

To check that the multiplication of $H$ by the vectors of an orthonormal basis results in norm-1 vectors is not enough to show that $H$ is a unitary matrix. It is also necessary to show that the resulting vectors are orthogonal, that is, to show that $\braket{-}{+}=0$. At this point, it is easier to check that $H$ is unitary by calculating $HH^\dagger$, where $H^\dagger$ is obtained by transposing $H$ and conjugating each entry. If the result is the identity matrix, $H$ is unitary. For the record, $H^\dagger$ is called the Hermitian transpose of $H$.

A quantum circuit is a graphic representation of a quantum algorithm. The input qubit is located on the left, and the information (qubit's state) is transmitted unaltered from left to right until it encounters a logic gate. The gate receives the input from the left, processes the information, and the output is then passed to the right and proceeds further. The gate processing is accomplished by multiplying the unitary matrix, which represents the gate, by the vector that represents the qubit's state. For example, the expression
$\ket{+}=H\ket{0}$ is represented by the following circuit:

\[
\Qcircuit @C=2.3em @R=1.9em {
\lstick{\ket{0}}        &\gate{H}  &  \rstick{\ket{+}.}\qw
\]

The input is vector $\ket{0}$, which is conveyed unchanged by the wire to $H$, which acts on the input and transforms it into $\ket{+}$, which is then conveyed to the right. The gate action is calculated by multiplying $H$ by $\ket{0}$. Therefore, the result of the computation is $\ket{+}$. If at the end of the computation we perform a measurement, the circuit is

\[
\Qcircuit @C=2.3em @R=1.9em {
\lstick{\ket{0}}    & \gate{H} & \meter & \rstick{\begin{cases} 0, \text{ with probability }\frac{1}{2}, \vspace{0.1cm}\\ 1, \text{ with probability }\frac{1}{2}. \end{cases}}\cw
\]

The circuit shows that the output of the measurement of the qubit, whose state was $\ket{+}$, is 0 with probability 1/2 or 1 with the same probability. Fig. <ref> shows the histogram of the probability distribution generated in Qiskit[Qiskit is open-source software for running programs on IBM quantum computers.] with two iterations.

Histogram of the probability distribution generated by measuring a qubit whose state is $\ket{+}$.

An example that is simpler than the previous one is the $X$ gate, defined as

0 & 1 \\
1 & 0 \\
\end{bmatrix}.
$X$ is the quantum NOT gate because $\ket{1}=X\ket{0}$ and $\ket{0}=X\ket{1}$. We can verify these equations through the matrix multiplication of $X$ with $\ket{0}$ and $\ket{1}$. In a more compact form, we can write $\ket{j\oplus 1}=X\ket{j}$, where $\oplus$ is the XOR operation or sum modulo 2. Because of this, the gate $X$ is also represented as $\oplus$. A circuit using the $X$ gate is

\[
\Qcircuit @C=2.3em @R=1.9em {
\lstick{\ket{0}}    & \gate{X} & \meter & \rstick{1 \text{ with probability 1.}}\cw
\]

Now we can increase the complexity. How to generate a superposition such that the amplitudes of $\alpha\ket{0}+\beta\ket{1}$ are different and non-null? For example, how to generate a state $\alpha\ket{0}+\beta\ket{1}$ such that $|\alpha|^2=25\%$ and $|\beta|^2=75\%$ before the measurement? The answer is to use the most general 1-qubit gate, whose algebraic expression is

\[
\left[\begin{array}{cc}
\cos\frac{\theta}{2} &  -\e^{ \ii \lambda}\sin\frac{\theta}{2} \\
\e^{ \ii \phi}\sin\frac{\theta}{2}   &  \e^{ \ii (\lambda+\phi)}\cos\frac{\theta}{2}
\end{array}\right].
\]

After applying $U(\theta,0,0)$ on $\ket{0}$, we obtain

\[
\]

We must choose $\theta=2\pi/3$, because $\cos^2(\pi/3)=1/4$. The previous example using the Hadamard gate can be reproduced by taking $\theta=\pi/2$ and $\lambda=\pi$ because $H=U(\pi/2,0,\pi)$.

$U(\theta,\phi,\lambda)$ is a wildcard gate because it represents all 1-qubit gates (modulo a global phase factor). For instance, three useful gates obtained from $U$ are

\begin{align*}
U\Big(\theta,-\frac{\pi}{2},\frac{\pi}{2}\Big) &= R_x(\theta)=\left[\begin{array}{cc}
\cos\frac{\theta}{2} &  -\ii\sin\frac{\theta}{2} \vspace{2pt}\\
-\ii\sin\frac{\theta}{2}   &  \cos\frac{\theta}{2}
\end{array}\right],\\
U(\theta,0,0) &= R_y(\theta)=\left[\begin{array}{cc}
\cos\frac{\theta}{2} &  -\sin\frac{\theta}{2} \vspace{2pt}\\
\sin\frac{\theta}{2}   &  \cos\frac{\theta}{2}
\end{array}\right],\\
U(0,0,\lambda) &=\e^{\ii \lambda/2}R_z(\lambda)=
\left[\begin{array}{cc}
1 &  0 \\
0   &  \e^{ \ii \lambda}
\end{array}\right].
\end{align*}

where $R_x$, $R_y$, and $R_z$ are the operators that rotate the Bloch sphere about the $x$, $y$, and $z$-axis, respectively. Unfortunately, $U$ is too perfect to be true for it would be possible to choose $\theta$ as small as we want at the cost of one single gate. Errors would eventually prevent obtaining good results after choosing very small angles.

To determine the computational complexity of an algorithm, we have to restrict ourselves to a finite set of single-qubit gates. The most important 1-qubit gates are

\[
I_2 \,\,=\,\, \begin{bmatrix}
1 & 0 \\
0 & 1 \\
\end{bmatrix},\hspace{0.4cm}
X \,\,=\,\,  \begin{bmatrix}
0 & 1 \\
1 & 0 \\
\end{bmatrix}, \hspace{0.4cm}
Y \,\,=\,\,  \begin{bmatrix}
0 & -\ii \\
\ii & 0 \\
\end{bmatrix}, \hspace{0.4cm}
Z \,\,=\,\,  \begin{bmatrix}
1 & 0 \\
0 & -1 \\
\end{bmatrix}
\]

known as Pauli matrices,

\[
H=\frac{1}{\sqrt 2}\begin{bmatrix}
1 & \,\,\,1 \\
1 & -1 \\
\end{bmatrix},\hspace{0.3cm}
S= \begin{bmatrix}
1 & 0 \\
0 & \ii \\
\end{bmatrix},\hspace{0.2cm}
S^\dagger= \begin{bmatrix}
1 & 0 \\
0 & -\ii \\
\end{bmatrix},\hspace{0.3cm}
T= \begin{bmatrix}
1 & 0 \\
0 & \textrm{e}^{\frac{\ii \pi}{4}} \\
\end{bmatrix},\hspace{0.2cm}
T^\dagger= \begin{bmatrix}
1 & 0 \\
0 & \textrm{e}^{-\frac{\ii \pi}{4}} \\
\end{bmatrix}
\]

known as Hadamard gate, phase gate, its conjugate gate, $\pi/8$ gate or $T$ gate and its conjugate.[The $T^\dagger$ gate is in fact the transpose-conjugate gate, but since $T$ is diagonal, $T^\dagger$ is simply the conjugate gate.] The complex numbers
$\textrm{e}^{\pm\frac{\ii \pi}{4}} $
are equal to

\[
\textrm{e}^{\pm\frac{\ii \pi}{4}} = \frac{1\pm \ii}{\sqrt 2}.
\]

Every quantum circuit without meters has an equivalent algebraic expression. For example, if $A$, $B$, $C$ are single-qubit gates, the circuit

\[
\Qcircuit @C=2.3em @R=1.9em {
\lstick{\ket{0}}    & \gate{A}  & \gate{B}  & \gate{C} & \rstick{\ket{\psi}} \qw
\]

is equivalent to the algebraic expression

\[
\ket{\psi} \,=\, C\cdot B\cdot A \cdot \ket{0},
\]

where $\,\cdot\,$ is the matrix product, which is usually omitted. The algebraic expression equivalent to the circuit has the reverse order. Therefore, the last circuit can also be written as

\[
\Qcircuit @C=2.3em @R=1.9em {
\lstick{\ket{0}}    & \gate{CBA}  & \rstick{\ket{\psi},} \qw
\]

where $CBA$ is a $2\times 2$ unitary matrix. For example, the following circuits are equivalent:

\[
\Qcircuit @C=2.3em @R=1.9em {
\lstick{}    & \gate{H}  & \gate{X}  & \gate{H} & \rstick{\,\,\equiv} \qw & & \gate{Z}   & \rstick{,}\qw
\]

because $Z=HXH$. The equivalent algebraic expression can be used to simplify the circuit and predict its output.

In quantum computing, we have to take advantage of classical computing notation. For instance, think that $\ell$ in $\ket{\ell}$ is a classical bit. Then, $\ket{\ell}$ represents both $\ket{0}$ and $\ket{1}$. This notation is used in $\ket{\ell\oplus 1}=X\ket{\ell}$. Similarly, we have $(-1)^\ell\ket{\ell}=Z\ket{\ell}$ and $(-1)^\ell \ii \,\ket{\ell\oplus 1}=Y\ket{\ell}$. Those expressions are used to determine the output of gates $X$, $Y$, and $Z$ when the input is a vector of the computational basis. For the gate $U(0,0,\lambda)$, we have $ \e^{ \ii \lambda\ell}\ket{\ell}=U(0,0,\lambda)\ket{\ell}$, which includes $S$, $T$, and their conjugate gates as subcases. All those gates don't create superposition. The only one that does is the Hadamard gate, whose output is

\[
\frac{\ket{0}+(-1)^\ell\ket{1}}{\sqrt 2} \,=\, H \ket{\ell}.
\]

Now we are ready to show that

\[
\Qcircuit @C=1.5em @R=0.9em {
\lstick{\ket{\ell}}  & \qw  & \gate{X}     & \gate{H} & \rstick{\frac{\ket{0}-(-1)^{\ell}\ket{1}}{\sqrt 2}} \qw
\]

\[
\Qcircuit @C=1.5em @R=0.9em {
\lstick{\ket{\ell}}  & \qw  & \gate{H}     & \gate{X} & \rstick{\frac{(-1)^\ell\ket{0}+\ket{1}}{\sqrt 2}.} \qw
\]

With a little more effort, we show up to a global phase that

\[
\Qcircuit @C=1.5em @R=0.9em {
\lstick{\ket{0}}  & \qw  & \gate{H}     & \gate{T}  & \gate{H}    & \rstick{\frac{\ket{0}-\ii\left(\sqrt{2}-1\right)\ket{1}}{\sqrt{2}\sqrt{2-\sqrt{2}}}.} \qw   &
\]

§.§.§ Implementing on IBM quantum computers.

At this point, utilizing IBM's composer is a great idea. To access it, log in to IBM's website[<https://quantum-computing.ibm.com/>] (registration is required), and click on Launch Composer. IBM's composer is user-friendly, allowing you to drag available gates into the circuit. For now, let's stick to basic usage. Fig. <ref> displays a circuit with the Hadamard gate followed by a measurement. We simply drag $H$ and drop it onto the first wire of the circuit, then drag the meter and drop it after $H$. The meter's arrow indicates that the output is redirected to an auxiliary classical register at the bottom of the circuit.

Example of a circuit with a Hadamard gate and a meter (Reprint Courtesy of IBM Corporation ©)

Output of the circuit with a Hadamard gate and a meter (Reprint Courtesy of IBM Corporation ©)

After the circuit is ready, we click on Setup and run, and then we have two options: (1) Run the circuit on a quantum computer by selecting one of the available quantum systems, or (2) simulate the circuit by selecting a simulator. It is usually better to start with the second option. We select ibm_qasm_simulator as the provider, then we select the number of shots and then we click on Run at the bottom. Fig. <ref> shows the output of an execution. The result 000 was obtained 503 times and 001 was obtained 521 times out of 1024 shots. The first two bits must be discarded because they refer to qubits that have not been used (qubits q$_2$ and q$_1$). The output uses the order q$_2$q$_1$q$_0$, different from the order adopted in most textbooks on quantum computing. As we can see, the composer runs the experiment several times (up to 8192) and shows the histogram of the cumulative frequency distribution. In the case of the Hadamard gate, the most probable result is 50% each, but results close to 50% have non-negligible probabilities and frequently occur. To obtain results closer to 50%, we have to increase the number of shots.

If we choose to run on a quantum computer, the circuit will be queued and may take a long time. We can check the queue size when selecting the system. The output from the quantum computer is usually different from the simulator  due to errors that degrade the result. Increasing the number of shots doesn't guarantee that the probability distribution converges to the correct distribution. It is important to check the correctness of the circuit through the simulator before running on the quantum system.

§ QUANTUM STATES AND ENTANGLEMENT

The state of two qubits is described by a vector of norm 1 that belongs to a four-dimensional vector space because there are four possible results after measuring the qubits: 00, 01, 10, 11. The first bit refers to the first qubit and the second bit to the second qubit, as is usual in textbooks on quantum computing, and the least significant bit is on the right, as usual.

Following the laws of quantum mechanics, there is a one-to-one correspondence between the canonical basis and the possible measurement outcomes as follows:

\begin{equation*}
\ket{00}  = \left(
\begin{array}{r}
1 \\ 0 \\ 0 \\ 0
\end{array}
\right),\,\,\ \
\ket{01}  =\left(
\begin{array}{r}
0 \\ 1 \\ 0 \\ 0
\end{array}
\right),\,\,\ \
\ket{10}  =\left(
\begin{array}{r}
0 \\ 0 \\ 1 \\ 0
\end{array}
\right),\,\,\ \
\ket{11}  =\left(
\begin{array}{r}
0 \\ 0 \\ 0 \\ 1
\end{array}
\right).
\end{equation*}

In the classical case, the state of two bits is either 00 or 01 or 10 or 11, exclusively. In the quantum case, the state of two qubits is the linear combination

\[
\ket{\psi}= a_0\ket{00}+a_1\ket{01}+a_2\ket{10}+a_3\ket{11},
\]

where $a_0$, $a_1$, $a_2$, and $a_3$ are complex numbers. When the state of two qubits is $\ket{\psi}$, the outcome of a measurement in the computational basis is either 00 or 01 or 10 or 11, exclusively and stochastically; there is no way of predicting the measurement outcome even knowing $\ket{\psi}$. However, if we know $\ket{\psi}$, then we know the probabilities of outcomes, which are

\begin{align*}
\end{align*}

The sum of those probabilities is 1.
If we don't know state $\ket{\psi}$, a single measurement doesn't allow the determination of $\ket{\psi}$, that is, we cannot find the amplitudes $a_0$, $a_1$, $a_2$, and $a_3$. There is an important theorem in quantum mechanics known as non-cloning theorem [20, 47, 66].

(No cloning)
Using unitary operators, it is impossible to make an identical copy of an arbitrary unknown quantum state that is available to us.

This theorem severely restricts any possibility of determining $\ket{\psi}$ through measurements. However, if we can generate $\ket{\psi}$ again and again, for example, through a circuit, we can repeat the whole process several times and obtain an approximation for $\text{prob}(00)$, $\text{prob}(01)$, $\text{prob}(10)$, and $\text{prob}(11)$. For example, by repeating 1000 times, we can determine these probabilities with two digits. Unfortunately, we are still unable to determine $\ket{\psi}$ exactly because knowing $|a_0|^2$ doesn't allow us to determine $a_0$ exactly. It may seem that this is unimportant—false. Let's consider a critical example. Suppose that

\[
\text{prob}(00)=\frac{1}{2},\,\,\,\,\,\,\,\,\,\,  \text{prob}(01)=0,\,\,\,\,\,\,\,\,\,\, \text{prob}(10)=0,\,\,\,\,\,\,\,\,\,\,  \text{prob}(11)=\frac{1}{2}.
\]

We have at least two possibilities for $\ket{\psi}$:

\[
\ket{\psi_1}=\frac{\ket{00}+\ket{11}}{\sqrt 2}\,\,\,\,\,\,\, \text{ and }\,\,\,\,\,\,\, \ket{\psi_2}=\frac{\ket{00}-\ket{11}}{\sqrt 2}.
\]

Note that $\ket{\psi_1}$ and $\ket{\psi_2}$ are orthogonal. This shows that we can make a serious mistake. We don't know whether two circuits are equivalent when their probability distributions are the same.

At this point, the following question is relevant: Suppose that we know $\ket{\psi}$, is it possible to determine the state of each qubit? The answer is “depends on $\ket{\psi}$”. If $\ket{\psi}$ is one of the states of the computational basis then we know the state of each qubit. For example, suppose $\ket{\psi}=\ket{10}$. We have to factorize $\ket{\psi}$ as

\[
\ket{10}\,=\,\ket{1}\ket{0}\,=\,\ket{1}\otimes\ket{0},
\]

where $\otimes$ is called Kronecker product. When factorization is successful, we know the state of each qubit. In this case, the state of the first qubit is $\ket{1}$ and the state of the second is $\ket{0}$. When we write $\ket{1}\ket{0}$, the Kronecker product is implicitly assumed.

The Kronecker product[There is a more abstract formulation of the Kronecker product called tensor product. In this work, we use these terms interchangeably. The notation $A\otimes B$ reads “A tensor B”; however, note that the terms tensor and tensor product are used in other areas of mathematics with differing meaning, such as in differential geometry.] of two vectors or two matrices is defined as follows. Let $A$ be a $m\times n$ matrix and $B$ a $p\times q$ matrix. Then,

\begin{equation*}
A\otimes B = \begin{bmatrix}
a_{11} B & \cdots & a_{1n} B \\
& \ddots &  \\
a_{m1} B & \cdots & a_{mn} B \\
\end{bmatrix}.
\end{equation*}

The result is a $mp\times nq$ matrix. The Kronecker product of vectors $\ket{1}$ and $\ket{0}$ is calculated by viewing these vectors as $2\times 1$ matrices and is given by

\begin{equation*}
\ket{1}\otimes\ket{0}=
\begin{bmatrix}
0 \\
1 \\
\end{bmatrix}\otimes \begin{bmatrix}
1 \\
0 \\
\end{bmatrix}\,=\,
\begin{bmatrix}
1 \\
0 \\
\end{bmatrix} \\ \\
1 \\
0 \\
\end{bmatrix}
\end{bmatrix}  \,=\,
\begin{bmatrix}
0 \\
0 \\
1 \\
\end{bmatrix}=\ket{10}.
\end{equation*}

Note that the Kronecker product is noncommutative. For example, $\ket{1}\otimes\ket{0}\neq \ket{0}\otimes\ket{1}$. An important hint is to never change the order of the Kronecker product.

From the laws of quantum mechanics, if the state of a qubit is $\ket{\psi_1}$ and the state of a second one is $\ket{\psi_2}$, then the state $\ket{\psi}$ of the composite system, two interacting qubits, will initially be

\[
\ket{\psi}=\ket{\psi_1}\otimes\ket{\psi_2}.
\]

We can always obtain the state of the composite system when we know the states of the parts. However, the reverse process is not possible in general. For example, suppose that the state of two qubits is

\[
\ket{\psi}=\frac{\ket{00}+\ket{11}}{\sqrt 2}.
\]

We want to find 1-qubit states $\ket{\psi_1}=\alpha\ket{0}+\beta\ket{1}$ and $\ket{\psi_2}=\gamma\ket{0}+\delta\ket{1}$ such that

\[
(\alpha\ket{0}+\beta\ket{1})\otimes(\gamma\ket{0}+\delta\ket{1}) = \frac{\ket{00}+\ket{11}}{\sqrt 2}.
\]

Expanding the left-hand side, we obtain the following system of equations:

\begin{align*}
\alpha\gamma=\frac{1}{\sqrt 2},\ \
\alpha\delta=0,\ \
\beta\gamma=0,\ \
\beta\delta=\frac{1}{\sqrt 2}.
\end{align*}

Since this system has no solution, the 2-qubit state $\ket{\psi}$ cannot be written as the Kronecker product of 1-qubit states. In quantum mechanics, a composite quantum system may have a definite state $\ket{\psi}$ while parts of the system have no definite state.

A quantum state of a composite system that cannot be factorized in terms of the Kronecker product is called an entangled state. Entangled states are very important in quantum computing because without them the computational power of the quantum computer would be badly impaired. However, the presence of entanglement in a quantum algorithm doesn't guarantee that this algorithm is more efficient than its classical counterpart.

The term “definite state” $\ket{\psi}$ in quantum mechanics means pure state. A state of a quantum system is called a pure state if we are 100% sure that the system is described by a norm-1 vector $\ket{\psi}$. On the other hand, if we are not 100% sure, that is, if we know that the state of the system is $\ket{\psi_1}$ with probability $0<p<1$ or $\ket{\psi_2}$ with probability $1-p$, then the state is mixed and is represented by an ensemble or a matrix $\rho$ such that $\mathrm{Tr}(\rho)=1$. When the state of a composite quantum system is entangled, the state of any sub-system is always a mixed state.

We can generalize the discussion of this Section to $n$ qubits, where $n\ge 1$. The computational basis has $2^n$ vectors, each vector with $2^n$ entries,

\begin{equation*}
\ket{0\cdots 00}  = \left(
\begin{array}{r}
1 \\ 0 \\ \vdots \\ 0
\end{array}
\right),\,\,\ \
\ket{0 \cdots 01}  =\left(
\begin{array}{r}
0 \\ 1 \\ \vdots \\ 0
\end{array}
\right),\,\,\ \
\cdots,\,\,\ \
\ket{1\cdots 11}  =\left(
\begin{array}{r}
0 \\ 0 \\ \vdots \\ 1
\end{array}
\right).
\end{equation*}

Note that the binary number inside the ket, for instance, $0\cdots 0$ in $\ket{0\cdots 0}$, has $n$ bits and the state itself is the Kronecker product of $n$ 1-qubit states. The binary number $0\cdots 0$ can be written in the decimal notation as $\ket{0\cdots 0}\rightarrow\ket{0}$. Each binary number inside the kets can be written in the decimal notation as

\[
\ket{0\cdots 00}\rightarrow\ket{0}, \,\,\,\,\,\ket{0\cdots 01}\rightarrow\ket{1}, \,\,\,\,\,\ket{0\cdots 10}\rightarrow\ket{2}, \,\,\,\,\, ..., \,\,\,\,\, \ket{1\cdots 11}\rightarrow\ket{2^n-1}.
\]

A generic state $\ket{\psi}$ belongs to a $2^n$-dimensional vector space. Then,

\[
\ket{\psi}=a_0\,\ket{0}+a_1\,\ket{1}+a_2\,\ket{2}+ \cdots +a_{2^n-1}\,\ket{2^n-1},
\]

\[
\left|a_0\right|^2+\left|a_1\right|^2+\left|a_2\right|^2+\cdots+\left|a_{2^n-1}\right|^2=1.
\]

After a measurement of all qubits, we obtain a random $n$-bit string with the following probability distribution: The outcome is either the $n$-bit string $0\cdots 00$ with probability $\left|a_0\right|^2$, or the $n$-bit string $0\cdots 01$ with probability $\left|a_1\right|^2$, and so on. We have a sample space comprising those $n$-bit strings and a probability distribution given by prob$(\ell)=\left|a_\ell\right|^2$, where $\ell$ is a $n$-bit string. The measurement outcome is a random variable that takes a value $\ell$ in this sample space with probability prob$(\ell)$.

As we have said before, a vector of the computational basis of $n$ qubits can be written as the Kronecker product of $n$ 1-qubit vectors. For example, for $n=3$ qubits, we can obtain the second vector of the computational basis using the Kronecker product as

\begin{equation*}
\ket{0}\otimes\ket{0}\otimes\ket{1}\,\,=\,\,
\begin{bmatrix}
1 \\
0 \\
\end{bmatrix}\otimes \begin{bmatrix}
1 \\
0 \\
\end{bmatrix}\otimes
\begin{bmatrix}
0 \\
1 \\
\end{bmatrix}\,=\,
\begin{bmatrix}
0 \\
1 \\
0 \\
0 \\
0 \\
0 \\
0 \\
\end{bmatrix}\,\,=\,\,\ket{001}.
\end{equation*}

In the decimal notation, $\ket{0}$ can be confused with the state of 1 qubit. To avoid confusion, we have to know what is the number of qubits. For example, if $\ket{0}$ refers to the state of 3 qubits in the decimal notation, then in binary we have $\ket{000}$.

In this section, we have defined entangled states. It is not a good idea to try to understand this concept without using mathematics at the outset. Learning the basic definition of entanglement is similar to learning what a prime number is in basic arithmetic. Suppose we know nothing and are going to learn the basics of arithmetic, starting with addition. After attending classes, doing many exercises, and memorizing tables, we master the concept of addition. The next step is multiplication. We go through the same process of classes, exercises, and table memorization, and eventually, we master the concept of multiplication. Then we are ready to learn the reverse process, factorization. We learn that the factors of 15 are 3 and 5. When we try 17, we find that there are no two positive numbers strictly less than 17 that, when multiplied, give 17. Then we are ready to understand the concept of prime numbers, which is very important in mathematics. If we understand prime numbers, then we are ready to understand entangled states. But this time, we have to learn the direct sum of vectors and the Kronecker product of vectors before attempting to factorize a vector. That is, we have to find two vectors $\ket{\psi_1}$ and $\ket{\psi_2}$ that have fewer entries than $\ket{\psi}$ so that $\ket{\psi}=\ket{\psi_1}\otimes\ket{\psi_2}$. Entangled states are the irreducible vectors of composite quantum systems in terms of the Kronecker product. A single-qubit state is not entangled because a single-qubit is not a composite system. We need at least two qubits. Although there is a long road ahead of us, two qubits are a good starting point. In the next section, we will see how to produce an entangled state in a quantum computer.

§ TWO-QUBIT QUANTUM GATES

The most important 2-qubit gate is CNOT or controlled-NOT gate, also denoted by $C(X)$ or $CX$. It is defined as

and is represented by the circuit

\[
\Qcircuit @C=2.3em @R=1.9em {
\lstick{\ket{k}}    & \ctrl{1} &  \rstick{\ket{k}} \qw \\
\lstick{\ket{\ell}}  & \targ    &  \rstick{X^k\ket{\ell}=\ket{\ell \oplus k},}  \qw \\
\]

where $k$ and $\ell$ are bits. The state of the first qubit (control) doesn't change after applying CNOT. The state of the second qubit (target) changes only if bit $k$ is 1. In this case the output is $X\ket{\ell}=\ket{\ell\oplus 1}$. If $k=0$ then $X^0=I_2$ and $I_2\ket{\ell}=\ket{\ell}$, where $I_2$ is the $2\times 2$ identity matrix. We have defined CNOT by showing its action on the vectors of the computational basis. In linear algebra, this definition is complete, because to know the action of CNOT on an arbitrary vector, which is a linear combination of vectors of the computational basis, we use the linearity of this gate. For example, in the circuit below the first input is in superposition:

\[
\Qcircuit @C=3.3em @R=1.em {
\lstick{\frac{\ket{0}+\ket{1}}{\sqrt 2}}   & \ctrl{2} &   \qw \\
&  &  & \frac{\ket{00}+\ket{11}}{\sqrt 2}. \\
\lstick{\ket{0}}                           & \targ    &   \qw  \gategroup{1}{1}{3}{3}{.7em}{\}}
\]

What is the output? The best way to determine the output is via algebraic calculations. After using the distributive property of the Kronecker product over the sum of vectors, the input to the circuit is

\[
\frac{\ket{0}+\ket{1}}{\sqrt 2}\otimes \ket{0} \,\,\,=\,\,\, \frac{1}{\sqrt 2}\,\ket{0}\otimes\ket{0}+ \frac{1}{\sqrt 2}\,\ket{1}\otimes\ket{0} \,\,\,=\,\,\, \frac{\ket{00}+\ket{10}}{\sqrt 2}.
\]

To calculate the action of CNOT on a sum of vectors, we use the linearity of the matrix product, that is,

\[
\text{CNOT}\cdot\left( \frac{\ket{00}+\ket{10}}{\sqrt 2}\right)\,\,=\,\, \frac{1}{\sqrt 2}\,\text{CNOT}\cdot\ket{00}+ \frac{1}{\sqrt 2}\,\text{CNOT}\cdot\ket{10},
\]

where $\text{CNOT}\cdot\ket{00}$ denotes the multiplication of the CNOT matrix by vector $\ket{00}$. Using the definition given at the beginning of the Section, we obtain $\text{CNOT}\ket{00}=\ket{00}$ and  $\text{CNOT}\ket{10}=\ket{11}$, and we confirm that the output is

\[
\frac{\ket{00}+\ket{11}}{\sqrt 2}.
\]

Since this result is an entangled state, we cannot factorize it and therefore we cannot write the output for each qubit.

The same result is obtained if we use the matrix representation, which is

\[
\text{CNOT} =
\begin{bmatrix}
I_2 &  \\
& X \\
\end{bmatrix}
\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0
\end{bmatrix},
\]

and the representation of $\ket{00}$ and $\ket{10}$ as 4-dimensional vectors, that is,

\[
\frac{1}{\sqrt 2}
\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0
\end{bmatrix}
\begin{bmatrix}
1  \\
0  \\
0  \\
\end{bmatrix}
\frac{1}{\sqrt 2}
\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0
\end{bmatrix}
\begin{bmatrix}
0  \\
0  \\
1  \\
\end{bmatrix}
\frac{1}{\sqrt 2}
\begin{bmatrix}
1  \\
0 \\
0  \\
\end{bmatrix}.
\]

The complete circuit that implements the entangled state above when the initial state of the qubits is $\ket{00}$ is

\[
\Qcircuit @C=2.3em @R=0.7em {
\lstick{\ket{0}} & \gate{H}   & \ctrl{2} &  \meter \qw & \cw \\
&  &  &  &  & &  {\substack{\text{   00 with probability 0.5,} \\ \text{   11 with probability 0.5.}}} \\
\lstick{\ket{0}} &\qw            & \targ    &  \meter \qw &\cw \gategroup{1}{1}{3}{5}{.7em}{\}}
\]

Since the state of the first qubit is initially $\ket{0}$, we have to use $H$ to generate $(\ket{0}+\ket{1})/2$. In fact, we have

\[
\text{CNOT}\cdot (H \otimes I)\,\ket{00}=\text{CNOT}\cdot\big(H\ket{0}\otimes\ket{0})=\frac{\ket{00}+\ket{11}}{\sqrt 2}.
\]

The next example is simpler than the previous one. Consider the circuit without measurements

\[
\Qcircuit @C=2.3em @R=0.7em {
\lstick{\ket{0}}    & \gate{H} &  \rstick{\ket{+}} \qw \\
\lstick{\ket{0}}  & \gate{H}  &  \rstick{\ket{+}.}  \qw \\
\]

What is the output? Usually, to calculate the output, we convert the circuit to its equivalent algebraic expression. For this circuit, we have
$(H\otimes H)\ket{00}.$
The calculation is performed in the following way:

\[
(H\otimes H)\ket{00}\,\,=\,\,(H\otimes H)\cdot(\ket{0}\otimes\ket{0})\,\,=\,\,(H\ket{0})\otimes (H\ket{0})\,\,=\,\,\ket{+}\otimes\ket{+}.
\]

In the second equality, we use the following property of the Kronecker product:

\[
(A\otimes B)\cdot(C\otimes D)\,\,=\,\,(A\cdot C)\otimes (B\cdot D),
\]

for matrices $A$, $B$, $C$, $D$, or

\[
(A\otimes B)\cdot(\ket{\psi_1}\otimes\ket{\psi_2})\,\,=\,\,(A\ket{\psi_1})\otimes (B\ket{\psi_2}),
\]

which is valid for any matrices $A$ and $B$ and vectors $\ket{\psi_1}$ and $\ket{\psi_2}$ as long as the number of entries of the vectors is equal to the corresponding number of columns of the matrices.

So the output of the circuit is

\[
\ket{+}\otimes\ket{+}\,\,=\,\,\frac{\ket{0}+\ket{1}}{\sqrt 2} \otimes \frac{\ket{0}+\ket{1}}{\sqrt 2}\,\,=\,\,\frac{\ket{0}+\ket{1}+\ket{2}+\ket{3}}{2}.
\]

Let us consider another example. Take the following circuit without measurements:

\[
\Qcircuit @C=2.3em @R=1.0em {
\lstick{\ket{0}}    & \gate{H} &  \rstick{\ket{+}} \qw \\
\lstick{\ket{0}}  & \qw  &  \rstick{\ket{0}.}  \qw \\
\]

How to calculate the output using the equivalent algebraic expression? The hint is to use the following equivalent circuit:

\[
\Qcircuit @C=2.3em @R=0.7em {
\lstick{\ket{0}}    & \gate{H} &  \rstick{\ket{+}} \qw \\
\lstick{\ket{0}}  & \gate{I_2}  &  \rstick{\ket{0},}  \qw \\
\]

where $I_2$ is the two-dimensional identity matrix. The algebraic calculation is done as follows:
\[
(H\otimes I_2)\ket{00}\,\,=\,\,(H\ket{0})\otimes (I_2\ket{0})\,\,=\,\,\ket{+}\otimes\ket{0}\,\,=\,\,\frac{\ket{00}+\ket{10}}{\sqrt 2}.
\]

When we convert a quantum circuit to its equivalent algebraic expression, we must use the Kronecker product for gates in the same column and the matrix product for gates in the same wire or in sequence; however, we must reverse the order of the gates in the second case. For example, the algebraic expression equivalent to the circuit

\[
\Qcircuit @C=2.3em @R=0.7em {
\lstick{\ket{0}}  & \gate{A} & \gate{B} & \multigate{2}{D} & \qw \\
\lstick{}         &          &          &                  &  & {\ket{\psi},\,\,\,\,\,\,}  \\
\lstick{\ket{0}}  & \qw      & \gate{C} & \ghost{D}        &  \qw
\gategroup{1}{1}{3}{5}{.7em}{\}}
\]

where $A$, $B$, and $C$ are 1-qubit gates and $D$ is a 2-qubit gate, is

\[
\ket{\psi} \,=\, D\cdot (B\otimes C)\cdot (A\otimes I_2)\cdot \ket{00}.
\]

We can simplify this expression a little and write

\[
\ket{\psi} \,=\, D \, (B A\,\otimes \,C) \ket{00}.
\]

Only $D$ can create or destroy entanglement. Operators $A$, $B$, and $C$ neither create nor destroy entanglement. The proof that $A$ cannot create or destroy entanglement is as follows. Suppose that the input state is $\ket{\psi_1}\otimes \ket{\psi_2}$ (unentangled). The action of $A$ outputs $(A\ket{\psi_1})\otimes \ket{\psi_2}$, which is unentangled. Now suppose that the input is an entangled state $\ket{\psi}$. The action of $A$ outputs $(A\otimes I)\ket{\psi}$. If this state is unentangled, that is, there exist $\ket{\psi_1}$ and $\ket{\psi_2}$ such that $(A\otimes I)\ket{\psi}=\ket{\psi_1}\otimes \ket{\psi_2}$, we reach a contradiction because the last equation is equivalent to $\ket{\psi}=(A^\dagger\ket{\psi_1})\otimes \ket{\psi_2}$.

CNOT is so important that we describe a variant that is CNOT activated by 0. It is defined by

and is represented by the circuit

\[
\Qcircuit @C=2.3em @R=1.9em {
\lstick{\ket{k}}    & \ctrlo{1} &  \rstick{\ket{k}} \qw \\
\lstick{\ket{\ell}}  & \targ    &  \rstick{X^{(1-k)}\ket{\ell}=\ket{\ell\oplus k\oplus 1}.}  \qw \\
\]

Note that the control qubit is denoted by the empty circle indicating that the CNOT's control is not activated if the state of the control qubit is $\ket{1}$. This gate is obtained from the usual CNOT by multiplying $(X\otimes I_2)$ on both sides, as shown in the following circuit equivalence:

\[
\Qcircuit @C=1.5em @R=0.7em {
& \gate{X}      & \ctrl{2} & \gate{X}   &          \qw   & & & \ctrlo{2} & \qw   \\
&          &          &       & \rstick{\,\,\equiv} & &  \\
\lstick{}    & \qw & \targ & \qw  &  \qw       & & & \targ   & \rstick{.}\qw
\]

This gate is represented by a block matrix of the form

$$ (X\otimes I_2)\cdot CNOT \cdot (X\otimes I_2) =
\begin{bmatrix}
& I_2 \\
I_2 &  \\
\end{bmatrix}
\begin{bmatrix}
I_2 &  \\
& X \\
\end{bmatrix}
\begin{bmatrix}
& I_2 \\
I_2 &  \\
\end{bmatrix} =
\begin{bmatrix}
X &  \\
& I_2 \\
\end{bmatrix}.

An alternative way to obtain the matrix representation is by listing sequentially the output of each vector of the computational basis

\begin{align*}
\ket{00}\xrightarrow{\circ\text{\textemdash}\oplus}\ket{01},\\
\ket{01}\xrightarrow{\circ\text{\textemdash}\oplus}\ket{00},\\
\ket{10}\xrightarrow{\circ\text{\textemdash}\oplus}\ket{10},\\
\ket{11}\xrightarrow{\circ\text{\textemdash}\oplus}\ket{11}.
\end{align*}

Then convert each output into the vector notation and join them side by side to form a matrix:

\begin{pmatrix}
0  \\
1 \\
0  \\
\end{pmatrix}
\begin{pmatrix}
1  \\
0 \\
0  \\
\end{pmatrix}
\begin{pmatrix}
0  \\
0 \\
1  \\
\end{pmatrix}
\begin{pmatrix}
0  \\
0 \\
0  \\
\end{pmatrix}\longrightarrow
\begin{bmatrix}
0 & 1 & 0 & 0 \\
1 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1
\end{bmatrix}=
\begin{bmatrix}
X &  \\
& I_2 \\
\end{bmatrix}.

The second most important 2-qubit gate is the controlled $Z$ gate, denoted by $C(Z)$ or $CZ$. Its circuit representations are

\[
\Qcircuit @C=1.5em @R=0.7em {
& \ctrl{2} & \qw  & & & \gate{Z} & \qw  & & & \ctrl{2} & \qw   \\
&          & \rstick{\,\,\equiv} & & &  &     \rstick{\,\,\equiv} & &  \\
\lstick{}& \gate{Z} & \qw  & & & \ctrl{-2} & \qw   & & & \ctrl{-2}   & \rstick{.}\qw
\]

It doesn't matter which qubit is the control or target, that is, $Z$ may be controlled by the first qubit, and target on the second, or the other way around. The third representation is interesting because the qubits are on an equal footing. There is only one matrix representation given by

\[
C(Z) =
\begin{bmatrix}
I_2 &  \\
& Z \\
\end{bmatrix}
\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & -1
\end{bmatrix}.
\]

The CNOT and $C(Z)$ gates are connected as shown by the following circuit equivalence:

\[
\Qcircuit @C=1.5em @R=0.9em {
& \qw      & \ctrl{2} & \qw   &          \qw   & & & \ctrl{2} & \qw   \\
&          &          &       & \rstick{\,\,\equiv} & &  \\
\lstick{}    & \gate{H} & \targ & \gate{H}  &  \qw       & & & \gate{Z}   & \rstick{.}\qw
\]

The equivalence follows from

\[ (I\otimes H)\,\text{CNOT}\,(I\otimes H)=C(Z), \]

which can be shown using the matrix representation. There is an alternative way of showing the equivalence by using the fact that $H^2=I$ and then $I\otimes H$ can be replaced by $C(H)$ because two $H$'s act trivially if the CNOT's control is not activated. Then

\[ (I\otimes H)\,\text{CNOT}\,(I\otimes H)=C(H)C(X)C(H)=C(HXH)=C(Z), \]

because $HXH=Z$ and $C(A)C(B)=C(AB)$ for any 1-qubit gates $A$ and $B$.

Now we are ready to show that the control and target of a CNOT invert when we multiply CNOT by $H\otimes H$ on both sides. Indeed,

\[ (H\otimes H)\,\text{CNOT}\,(H\otimes H)= (H\otimes I)(I\otimes H)\,\text{CNOT}\,(I\otimes H)(H\otimes I)=(H\otimes I)C(Z)(H\otimes I). \]

Consider the first qubit as the target of $C(Z)$. Then we have $HZH=X$ controlled by the second qubit, and we are done. The circuit representation is

\[
\Qcircuit @C=1.5em @R=0.7em {
& \gate{H}      & \ctrl{2} & \gate{H}   &          \qw   & & & \targ & \qw   \\
&          &          &       & \rstick{\,\,\equiv} & &  \\
\lstick{}    & \gate{H} & \targ & \gate{H}  &  \qw       & & & \ctrl{-2}   & \rstick{.}\qw
\]

The third most important 2-qubit gate is the SWAP gate. Its circuit representations are

\[
\Qcircuit @C=1.5em @R=0.9em {
&\ctrl{2}& \targ  &\ctrl{2} & \qw           &&&\targ    &\ctrl{2}& \targ   & \qw            & & & \qswap & \qw   \\
&         &        &          & \rstick{\,\,\equiv}&&&         &        &         & \rstick{\,\,\equiv} & & &  \qwx       &\\
\lstick{}&\targ    &\ctrl{-2}& \targ    & \qw           &&&\ctrl{-2}& \targ  &\ctrl{-2}& \qw            & & & \qswap \qwx  & \rstick{.}\qw
\]

The matrix representation is

\[
\text{SWAP}
\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1
\end{bmatrix}.
\]

This gate inverts an unentangled state $\ket{\psi_1}\ket{\psi_2}$ into $\ket{\psi_2}\ket{\psi_1}$, which follows from the fact that

\[
\text{SWAP}\ket{00}=\ket{00},\,\,\,\,\text{SWAP}\ket{01}=\ket{10},\,\,\,\,\text{SWAP}\ket{10}=\ket{01},\,\,\,\,\text{SWAP}\ket{11}=\ket{11}.
\]

§.§ Preparing an arbitrary 2-qubit state

An arbitrary 1-qubit state is prepared up to a global phase with gates $R_y(\theta)$ and $R_z(\varphi)$, as follows

\[
R_z(\varphi)R_y(\theta)\ket{0}=\e^{-\frac{\ii \varphi}{2}}\left(\cos\frac{\theta}{2}\,\ket{0}+\e^{\ii \varphi}\sin\frac{\theta}{2}\,\ket{1} \right),
\]

\begin{align*}
\cos\frac{\theta}{2} &  -\sin\frac{\theta}{2} \vspace{3pt}\\
\sin\frac{\theta}{2}   &  \cos\frac{\theta}{2}
\end{array}\right]
\end{align*}

\begin{align*}
R_z(\varphi)=\e^{-\frac{\ii \varphi}{2}}
\left[\begin{array}{cc}
1 &  0 \\
0   &  \e^{ \ii \varphi}
\end{array}\right].
\end{align*}

Supposing that the initial state of 2 qubits is $\ket{00}$, how do we prepare an arbitrary 2-qubit state $\ket{\psi}=a_0\ket{00}+a_1\ket{01}+a_2\ket{10}+a_3\ket{11}$? This new state can be used as the initial state of an algorithm instead of $\ket{00}$. To simplify the discussion, suppose that the amplitudes are real numbers. The output of the circuit

\[
\Qcircuit @C=1.3em @R=.3em {
\lstick{\ket{0}} & \gate{R_y(2\theta_1)}&\ctrlo{2}           &\ctrl{2}            & \rstick{} \qw \\
\lstick{}         &          &          &                  &  & {\,\,\,\ket{\psi}}  \\
\lstick{\ket{0}} & \qw                 &\gate{R_y(2\theta_2)}&\gate{R_y(2\theta_3)}& \rstick{}  \qw
\gategroup{1}{1}{3}{5}{.7em}{\}} }
\]

\[
\cos\theta_1\cos\theta_2\,\ket{00}+\cos\theta_1\sin\theta_2\,\ket{01}+\sin\theta_1\cos\theta_3\,\ket{10}+\sin\theta_1\sin\theta_3\,\ket{11}.
\]

Then, after solving the system of equations

\begin{align*}
\cos\theta_1\cos\theta_2 &= a_0,\\
\cos\theta_1\sin\theta_2 &= a_1,\\
\sin\theta_1\cos\theta_3 &= a_2,\\
\sin\theta_1\sin\theta_3 &= a_3,
\end{align*}

we find $\theta_1$, $\theta_2$, and $\theta_3$, which must be used in the circuit as parameters of $R_y$.

For example, to prepare state $\frac{1}{2}\left(\ket{00}+\ket{01}+\ket{10}+\ket{11}\right)$, the solution of the system of equations is $\theta_1=\theta_2=\theta_3=\pi/4$. When $\theta_2=\theta_3$, the product of the controlled gates simplifies to only one gate $R_y(2\theta_2)$ applied on the second qubit. Then,

\[
R_y\left(\frac{\pi}{2}\right)\otimes R_y\left(\frac{\pi}{2}\right)\,\ket{00}\,=\,\frac{1}{2}\left(\ket{00}+\ket{01}+\ket{10}+\ket{11}\right).
\]

§.§.§ Implementing on IBM quantum computers.

The implementation of the circuit with gates $H$ and CNOT on the IBM composer is shown in Fig. <ref>. We need to drag and drop an $H$ gate and a CNOT gate so that the control of CNOT is qubit q$_0$ and the target is qubit q$_1$. We also have to drag and drop two meters. If we want to see the exact simulation of the probability distribution in the composer, we must remove the meters. Note that in the composer, qubit q$_0$ represents the rightmost qubit, meaning the order of the qubits is $\ket{\text{q}_2\text{q}_1\text{q}_0}$, and the output refers to $\text{q}_2\text{q}_1\text{q}_0$. In this work and most papers and books, the opposite order is assumed. The output of a simulation with 1024 repetitions is shown in Fig. <ref>. The figure shows that the result 000 was obtained 507 times, 001 21 times, 010 51 times, and 011 445 times. We must discard the unused qubit q$_2$ (leftmost qubit). Therefore, the result shows that the algorithm returns 00 with probability of approximately 49,5% and 11 with probability of approximately 43,5%, which is unexpected based on the analytical calculation. The incorrect results 01 and 10 were obtained because quantum computers are error-prone.

Circuit with gates $H$ and CNOT (Reprint Courtesy of IBM Corporation ©)

Output of the circuit of Fig. <ref> using an IBM backend (Reprint Courtesy of IBM Corporation ©)

§ MULTIQUBIT GATES

The most important 3-qubit gate is the Toffoli gate, denoted by CCNOT or $C^2(X)$, defined by

and represented by the circuit

\[
\Qcircuit @C=2.3em @R=1.3em {
\lstick{\ket{j}}    & \ctrl{1} &  \rstick{\ket{j}} \qw \\
\lstick{\ket{k}}    & \ctrl{1} &  \rstick{\ket{k}} \qw \\
\lstick{\ket{\ell}}  & \targ    &  \rstick{X^{jk}\ket{\ell}=\ket{\ell\oplus(j \text{ AND } k)}.}  \qw \\
\]

This gate has two controls and one target. $X$ acts on the target qubit if and only if both control qubits are set to one. If one control is set to zero, the target doesn't change. This gate can be seen as the quantum version of the classical AND gate because if $\ell=0$, the output of the third qubit is $(j \text{ AND } k)$.
The matrix representation of the Toffoli gate is a diagonal block matrix given by

\[
C^2(X)= \begin{bmatrix}
I_2 &  &  &  \\
& I_2 &  &  \\
&  & I_2 &  \\
&  &  & X
\end{bmatrix}.
\]

There are variants of the Toffoli gate activated when the control qubits are set to zero. For example, the circuit

\[
\Qcircuit @C=2.3em @R=1.3em {
\lstick{\ket{j}}    & \ctrlo{1} &  \rstick{\ket{j}} \qw \\
\lstick{\ket{k}}    & \ctrlo{1} &  \rstick{\ket{k}} \qw \\
\lstick{\ket{\ell}}  & \targ    &  \rstick{X^{(1-j)(1-k)}\ket{\ell}}  \qw \\
\]

implements a gate that applies $X$ on the third qubit if and only if the first two control qubits are set to zero. It can be implemented using a standard Toffoli gate and $X$ gates, as shown in the following circuit equivalence:

\[
\Qcircuit @C=0.8em @R=0.6em {
\lstick{}&\ctrlo{1}&\rstick{} \qw           & & & & &\gate{X}    &\ctrl{1}   &\gate{X}  & \qw            \\
\lstick{}&\ctrlo{1}&\rstick{\,\,\,\,\,\equiv} \qw& & & & &\gate{X}    &\ctrl{1} &\gate{X}   &\qw          \\
\lstick{}&  \targ &\rstick{} \qw            & & & & &\qw         &\targ   & \qw &\rstick{.}\qw
\]

The multiqubit Toffoli gate $C^{n}(X)$ is a $(n+1)$-qubit gate with $n$ control qubits and one target. It is defined by

C^{n}(X)\ket{q_0}\ket{q_1}\cdots\ket{q_{n-1}}\ket{q_n}=\ket{q_0}\ket{q_1}\cdots\ket{q_{n-1}}X^{q_0q_1\cdots q_{n-1}}\ket{q_n},

and is represented by the circuit

\[
\Qcircuit @C=2.3em @R=1.5em {
\lstick{\ket{q_0}}    & \ctrl{1} &  \rstick{\ket{q_0}} \qw \\
\lstick{\ket{q_1}}    & \ctrl{0} &  \rstick{\ket{q_1}} \qw \\
\lstick{\vdots}    & \vdots &  \rstick{\vdots} \\
\lstick{\ket{q_{n-1}}}    & \ctrl{1} &  \rstick{\ket{q_{n-1}}} \qw \\
\lstick{\ket{q_n}}  & \targ    &  \rstick{X^{q_0q_1\cdots q_{n-1}}\ket{q_n},}  \qw \\
\]

where $q_0q_1\cdots q_{n-1}$ is the product of bits $q_0$, $q_1$, ..., $q_{n-1}$. Therefore, the state of the target qubit changes if and only if all control qubits are set to 1. The state of each control qubit doesn't change when we describe this gate acting on the computational basis. The action on a generic vector is obtained by writing the vector as a linear combination of vectors of the computational basis and then using linearity.

The simplest way to decompose the multiqubit Toffoli gate in terms of the usual Toffoli gate is by using $(n-2)$ draft qubits called ancillas. The ancillary qubits are interlaced with the control qubits, the first ancilla qubit being inserted between the second and third qubits. The best way to explain the decomposition is to show an example. Consider the gate $C^5(X)$, whose decomposition requires three ancillas, as shown in the following circuit equivalence:

\[
\Qcircuit @C=1.3em @R=0.7em {
\lstick{}& \ctrl{1}& \rstick{} \qw      & & &                & &\ctrl{1}& \qw     & \qw     & \qw     & \qw    &  \qw   & \ctrl{1} & \qw \\
\lstick{}& \ctrl{2}& \rstick{} \qw      & & &                & &\ctrl{1} & \qw     & \qw     & \qw     & \qw    &  \qw   & \ctrl{1} & \qw\\
\lstick{}&    ---- &                    & & &&\lstick{\ket{0}} &\targ    &\ctrl{1} & \qw     & \qw     & \qw    &\ctrl{1}& \targ& \rstick{\ket{0}}\qw \\
\lstick{}& \ctrl{2}&  \rstick{} \qw     & & &                & &\qw      &\ctrl{1}& \qw     & \qw     & \qw    &\ctrl{1}& \qw &\qw\\
\lstick{}&    ---- &\rstick{\,\,\,\,\,\equiv}& & &&\lstick{\ket{0}} &\qw      &\targ    &\ctrl{1} &\qw      &\ctrl{1}& \targ& \qw& \rstick{\ket{0}}\qw \\
\lstick{}& \ctrl{2}&  \rstick{} \qw     & & &                & &\qw      &\qw      &\ctrl{1}&\qw      &\ctrl{1}& \qw& \qw& \qw \\
\lstick{}&  ----   &                    & & &&\lstick{\ket{0}} &\qw      &\qw      &\targ    &\ctrl{1} &\targ& \qw& \qw& \rstick{\ket{0}}\qw \\
\lstick{}& \ctrl{1}&  \rstick{} \qw     & & &                & &\qw      &\qw      &\qw      &\ctrl{1} &\qw& \qw& \qw& \qw \\
\lstick{}& \targ   &  \rstick{} \qw     & & &                & &\qw      &\qw      &\qw      &\targ    &\qw& \qw& \qw& \rstick{.}\qw \\
\]

The multiqubit Toffoli gate can also be activated when the controls are set to zero. In this case, the control qubit is shown as an empty circle. For $n$ qubits, we have $2^n$ multiqubit Toffoli gates that can implement any Boolean function of $n$ bits, as described in Sec. <ref>.

§.§ Preparing an arbitrary 3-qubit state

Supposing that the initial state of 3 qubits is $\ket{000}$, we prepare an arbitrary 3-qubit state $\ket{\psi}=\sum_{j=0}^7 a_j \ket{j}$ with real amplitudes using the circuit

\[
\Qcircuit @C=0.7em @R=1.0em {
\lstick{\ket{0}} & \gate{R_y(2\theta_1)}&\ctrlo{1}                          &\ctrl{1}                             &\ctrlo{1}                         &\ctrlo{1}                          &\ctrl{1}                          &\ctrl{1}                          & \rstick{} \qw \\
\lstick{\ket{0}} & \qw                                  &\gate{R_y(2\theta_2)}&\gate{R_y(2\theta_3)}&\ctrlo{1}                          &\ctrl{1}                             &\ctrlo{1}                          &\ctrl{1}                         &  \qw& \rstick{\ket{\psi}} \\
\lstick{\ket{0}} & \qw                                  &\qw                                   &\qw                                   &\gate{R_y(2\theta_4)}&\gate{R_y(2\theta_5)}&\gate{R_y(2\theta_6)}&\gate{R_y(2\theta_7)}& \rstick{} \qw
\gategroup{1}{1}{3}{9}{.7em}{\}}}\vspace{0.2cm}
\]

and by solving the system of equations

\begin{align*}
\cos\theta_1\cos\theta_2\cos\theta_4 &= a_0,\,\,\,\,\,\,\,\,\,\,\,\cos\theta_1\cos\theta_2\sin\theta_4 = a_1,\\
\cos\theta_1\sin\theta_2\cos\theta_5 &= a_2,\,\,\,\,\,\,\,\,\,\,\,\,\cos\theta_1\sin\theta_2\sin\theta_5 = a_3,\\
\sin\theta_1\cos\theta_3\cos\theta_6 &= a_4,\,\,\,\,\,\,\,\,\,\,\,\,\sin\theta_1\cos\theta_3\sin\theta_6 = a_5,\\
\sin\theta_1\sin\theta_3\cos\theta_7 &= a_6,\,\,\,\,\,\,\,\,\,\,\,\,\,\sin\theta_1\sin\theta_3\sin\theta_7 = a_7,
\end{align*}

in order to find $\theta_1,...,\theta_7$, which are used in the circuit as parameters of $R_y$.

§ CIRCUIT OF A BOOLEAN FUNCTION

Suppose we want to evaluate a Boolean expression on a quantum computer. How do we implement the circuit? We need to know the types of bricks we have, some of which are shown in Fig. <ref>.

\[
\Qcircuit @C=1.0em @R=1.9em {
\lstick{a}    & \ctrl{1} &  \rstick{a} \qw \\
\lstick{b}    & \ctrl{1} &  \rstick{b} \qw \\
\lstick{0}  & \targ    &  \rstick{a\wedge b}  \qw \\
\Qcircuit @C=1.0em @R=1.8em {
\lstick{a}  & \ctrlo{1} &  \rstick{a} \qw \\
\lstick{b}  & \ctrlo{1} &  \rstick{b} \qw \\
\lstick{1}  & \targ &  \rstick{a\vee b}  \qw \\
} \hspace{2.5cm}
\Qcircuit @C=1.0em @R=1.93em {
\lstick{}    &  &  \rstick{} \\
\lstick{a}    & \ctrl{1} &  \rstick{a} \qw \\
\lstick{b}  & \targ    &  \rstick{a\oplus b}  \qw \\
\Qcircuit @C=1.em @R=2.0em {
\lstick{}   &  &  \rstick{} \\
\lstick{}  &  &  \rstick{} \\
\lstick{a}  &\targ    &  \rstick{\bar a}  \qw \\
\]

Basic bricks to build a Boolean expression.  To implement the AND and OR gates, we must add an extra ancilla bit initialized as 0 and 1, respectively.

The Boolean function[We use the following equivalent notations: $\text{AND}\,\equiv\wedge$, $\text{OR}\,\equiv\vee$, $\text{NOT}\,\equiv\,\bar{\,}$ .] $f(a,b)=a\wedge b$ is not reversible, then we need an extra bit to implement $U_f$, so that $U_f\ket{a,b,0}=\ket{a,b,a\wedge b}$. Note that we also have to keep the input bits. That is why the AND and OR gates require an extra ancilla bit, while the XOR and NOT gates don't. The ancilla bit must be initialized as 0 for the AND gate and as 1 for the OR gate. For the OR gate, the ancilla bit can be initialized as 0 followed by a NOT gate. We obtain other useful gates with these bricks, for instance, the NAND gate is obtained by placing a NOT gate before or after a AND gate in the following way:

\[
\Qcircuit @C=1.3em @R=1.6em {
\lstick{a}     &\qw & \ctrl{1}&  \rstick{a} \qw \\
\lstick{b}    &\qw& \ctrl{1}  &  \rstick{b} \qw \\
\lstick{0}  & \targ    & \targ &  \rstick{\bar a\vee \bar b.}  \qw \\
\]

Alternatively, we can simply initialize the ancilla qubit as 1 instead of adding the NOT gate. The output is $\overline{a\wedge b}$, which is equivalent to $\bar a\vee \bar b$ by De Morgan's laws, which is described in Fig. <ref>.  The exact same methods can be applied to obtain the NOR gate.

Involution     $\bar{\bar a} = a$

Idempotent     $a\wedge a = a$     $a\vee a = a$

Commutative       $a\wedge b = b\wedge a$     $a\vee b = b\vee a$

De Morgan     $\overline{a\wedge b} = \bar a\vee \bar b$     $\overline{a\vee b}=\bar a\wedge \bar b$

Associative     $(a\wedge b)\wedge c = a\wedge(b\wedge c)$       $(a\vee b)\vee c = a\vee(b\vee c)$

Distributive     $a\wedge (b\vee c) = (a\wedge b)\vee(a\wedge c)$       $a\vee(b\wedge c) = (a\vee b)\wedge(a\vee c)$

Complement     $a\wedge \bar a = 0$ $\bar 0=1$      $a\vee \bar a = 1$  $0=\bar 1$

Identity     $a\wedge 0 = 0$  $a\wedge 1 = a$     $a\vee 0 = a$   $a\vee 1 = 1$

Simplification rules for Boolean expressions.

The output of the XOR gate of Fig. <ref> does not show explicitly the input bits, at least not all of them. This introduces a challenge if we need to reuse the input bits. A useful implementation of the XOR gate, at the cost of losing efficiency, is

\[
\Qcircuit @C=1.3em @R=1.6em {
\lstick{a}     &\qw & \ctrl{2}&  \rstick{a} \qw \\
\lstick{b}    &\ctrl{1}& \qw  &  \rstick{b} \qw \\
\lstick{0}  & \targ    & \targ &  \rstick{ a\oplus b.}  \qw \\
\]

The same problem happens if we implement the Boolean expression $(\bar a\wedge b)$ as follows

\[
\Qcircuit @C=1.3em @R=1.6em {
\lstick{a}     &\targ & \ctrl{1}&  \rstick{\bar a} \qw \\
\lstick{b}    &\qw& \ctrl{1}  &  \rstick{b} \qw \\
\lstick{0}  & \qw    & \targ &  \rstick{\bar a\wedge b.}  \qw \\
\]

We cannot reuse the first input bit straightway. It is usually better to implement this Boolean expression placing a NOT before and after the first control, which is equivalent to an  empty control as follows

\[
\Qcircuit @C=1.3em @R=1.6em {
\lstick{a}    & \ctrlo{1}&  \rstick{a} \qw \\
\lstick{b}    & \ctrl{1}  &  \rstick{b} \qw \\
\lstick{0}    & \targ &  \rstick{\bar a\wedge b.}  \qw \\
\]

What about the ancilla bits, how can we reuse them? This is also possible but we need a larger example to show how it is done. Consider the following Boolean function:

\begin{equation}\label{eq:Boolean-expr}
f(a,b,c)\,=\, a\wedge (c\vee (a\wedge \bar b\wedge \bar c) ),
\end{equation}

which is implemented in the following way:

\[
\Qcircuit @C=1.9em @R=1.em {
\lstick{a}&\ctrl{1} & \qw     &\ctrl{4}& \qw     &\ctrl{1}    &\rstick{a} \qw \\
\lstick{b}&\ctrlo{1}& \qw     &\qw     & \qw     &\ctrlo{1}   &\rstick{b} \qw \\
\lstick{c}&\ctrlo{1}&\ctrlo{1}&\qw     &\ctrlo{1}&\ctrlo{1}   &\rstick{c} \qw \\
\lstick{0}& \targ   &\ctrlo{1}&\qw     &\ctrlo{1}& \targ      &\rstick{0} \qw \\
\lstick{1}& \qw     & \targ   &\ctrl{1}& \targ   & \qw        &\rstick{1} \qw \\
\lstick{0}& \qw     & \qw     &\targ   & \qw     & \qw        &\rstick{f(a,b,c).} \qw
\gategroup{1}{5}{5}{6}{1.5em}{--}
\]

We start the implementation by selecting the expression inside the innermost parentheses, which is $(a\wedge \bar b\wedge \bar c)$. We use 3 wires for the inputs $a$, $b$, and $c$ and an ancilla wire (4th bit) for the output of this sub-expression. We use a multiqubit Toffoli gate with full control for $a$ and empty controls for $\bar b$ and $\bar c$. Besides, the ancilla bit is initialized as 0 for the AND case. The second gate implements the OR of the output of the previous gate with $c$. All controls are empty and the new ancilla bit is initialized as 1 for the OR case. The third gate implements the AND of the last output with $a$. All controls are full and the new ancilla bit is initialized as 0 for the AND case. The output of the last ancilla bit is $f(a,b,c)$. To reuse the ancilla bits (except the last one) we have to include the gates in the dashed box, which is the mirror of the gates of the first part.

Before building the circuit of a Boolean expression, it is a good idea to simplify the expression by applying the simplification rules listed in Fig. <ref>. Expression (<ref>) simplifies to

\[
f(a,b,c)\,=\, a\wedge (\bar b\vee c),
\]

which can be implemented using 3 Toffoli gates and 2 ancilla bits in the following way:

\[
\Qcircuit @C=1.9em @R=0.9em {
\lstick{a}&\qw      &\ctrl{3}&\qw    &\rstick{a} \qw \\
\lstick{b}&\ctrl{1} &\qw     &\ctrl{1}   &\rstick{b} \qw \\
\lstick{c}&\ctrlo{1}&\qw     &\ctrlo{1}   &\rstick{c} \qw \\
\lstick{1}& \targ   &\ctrl{1}& \targ      &\rstick{1} \qw \\
\lstick{0}& \qw     &\targ   & \qw        &\rstick{f(a,b,c).} \qw
\]

This last example shows that we obtain equivalent circuits by manipulating the Boolean expression. For example, we know that

\[
a\wedge b\wedge c\wedge d\wedge e = (((a\wedge b)\wedge c)\wedge d)\wedge e.
\]

The left-hand side is implemented with one multiqubit Toffoli gate and one ancilla bit, while the right-hand side is implemented with 7 standard Toffoli gates and 4 ancillas bits. This provides a decomposition of the multiqubit Toffoli gate in terms of the Toffoli gates, identical to the one presented at the end of Subsec. <ref>.

§.§ Circuit of a truth table

Let's show how to obtain the quantum circuit of a truth table. We only need multiqubit Toffoli gates. To show that the multiqubit Toffoli gates can implement any truth table on a quantum computer, we take a 3-bit Boolean function $f(a,b,c)$ defined by the following truth table as an example:

a     b    c     f(a,b,c)

0     0     0     0

0     0     1     1

0     1     0     0

0     1     1     0

1     0     0     0

1     0     1     0

1     1     0     1

1     1     1     0

After this example, it is evident how the general case is obtained. Since $f$ has three input bits, we use multiqubit Toffoli gates with three controls. The 4th qubit is the target. The output of $f$ is the output of a measurement of the target qubit. Since $f$ has two clauses in the disjunctive normal form (there are two outputs 1 in the truth table), we use two multiqubit Toffoli gates.[In the disjunctive normal form, we only consider rows of the truth table whose output is 1. For each row with output 1, we write a conjunction of three literals, using NOT for each input 0. Then we write a disjunction of the conjunctions, like this, $f(a,b,c)=(\bar a\wedge\bar b\wedge c)\vee (a\wedge b\wedge \bar c)$, where $(\bar a\wedge\bar b\wedge c)$ is true only for input 001 and $(a\wedge b\wedge \bar c)$ only for input 110. Then $f$ is true only for these inputs.]
The first gate must be activated by the input $\ket{001}$ and the second by $\ket{110}$, which correspond to the rows of the truth table whose output is 1. The following circuit implements $f$:

\[
\Qcircuit @C=2.3em @R=1.6em {
\lstick{\ket{0}}    & \ctrlo{1} & \ctrl{1} &  \rstick{\ket{0}} \qw \\
\lstick{\ket{0}}    & \ctrlo{1} & \ctrl{1} &  \rstick{\ket{0}} \qw \\
\lstick{\ket{1}}    & \ctrl{1} & \ctrlo{1} & \rstick{\ket{1}} \qw \\
\lstick{\ket{0}}  & \targ  & \targ  &  \rstick{\ket{1}.}  \qw \\
\]

If the input is $\ket{a,b,c}\ket{0}$ then the output is $\ket{a,b,c}\ket{f(a,b,c)}$.
This shows that the quantum computer can calculate any $n$-bit Boolean function using a multiqubit Toffoli gate with $(n+1)$ qubits for each output 1 of the truth table. The goal here is not to implement classical algorithms on quantum computers because it makes no sense to build a much more expensive machine to run only classical algorithms. However, the implementation we have just described can be used for inputs in superposition, which is not allowed on a classical computer. Unfortunately, this quantum circuit construction technique for calculating truth tables is not efficient in general, since the number of multiqubit Toffoli gates increases exponentially as a function of the number of qubits in the worst case.

§ QUANTUM PARALLELISM

The most standard model of quantum computing is described by the circuit

\[
\Qcircuit @C=2.3em @R=0.7em {
\lstick{\ket{0}} & \gate{H} & \multigate{5}{\,\,\,U\,\,\,} &\meter  & \rstick{0 \text{ or } 1} \cw \\
\lstick{}  &  &        &        & \rstick{}  \\
\lstick{\vdots \,\,\,}  & {\vdots} &        &    {\vdots}   & & \lstick{\vdots}  \\
\lstick{}  &  &        &        & \rstick{}  \\
\lstick{}  &  &        &        & \rstick{}  \\
\lstick{\ket{0}} & \gate{H} & \ghost{\,\,\,U\,\,\,}        & \meter & \rstick{0 \text{ or } 1.} \cw
\]

The initial state of each qubit is $\ket{0}$. Then, the Hadamard gate is applied to each qubit, preparing for the quantum parallelism. Then, the unitary matrix $U$ is applied to all qubits. Finally, there is a meter for each qubit, returning a bit string.

Quantum parallelism is the simultaneous execution of an algorithm with more than one input to a single quantum processor. To execute the same task on a classical computer would require an exponential number of classical processors. To understand this concept, we focus only on $U$ without considering the $H$ gates. $U$ and the meters can be interpreted as a randomized algorithm in the classical sense. If $x$ is a $n$-bit string and $U$ is a $2^n\times 2^n$ matrix, then $U\ket{x}$ is a linear combination of $2^n$ vectors of the computational basis. After the measurements, a $n$-bit string $y$ returned, where $\ket{y}$ is one of the terms of the linear combination. That is, if the input to $U$ is $x$, the output after the measurement is $y$. $U$ is an “algorithm”, which is executed for a single input $x$ when the computation $U\ket{x}$ is performed. Now let us bring the $H$ gates back.

The first step of the circuit is to perform the following computation: $(H\ket{0})\otimes\cdots\otimes(H\ket{0})$, that is

\[
\left(\frac{\ket{0}+\ket{1}}{\sqrt 2}\right)\otimes\cdots\otimes\left(\frac{\ket{0}+\ket{1}}{\sqrt 2}\right).
\]

After expanding this product, we obtain
\[
\frac{1}{\sqrt{2^n}}\big(\ket{0\cdots 0}+\ket{0\cdots 01}+\ket{0\cdots 10}+\cdots+\ket{1\cdots 1}   \big).
\]

Each $n$-bit string is inside a ket of the sum above. That is, all possible inputs of a classical algorithm are represented by kets in the sum above. The next step in the standard model is to apply $U$. Due to the linearity of linear algebra, $U$ is applied to all kets of the sum above simultaneously. Therefore, it is possible to perform $2^n$ simultaneous computations on a $n$-qubit quantum computer. Note, however, that the result of these computations is a superposition state and, after a measurement, the final output is a single $n$-bit string.

We can refine the standard model by adding an extra register for draft calculations. Since unitary gates are invertible, the whole calculation process without measurement is reversible. This means that no information is erased. The number of output qubits must be equal to the number of input qubits. We postpone the discussion about this refinement and present it after describing and analyzing the basic quantum algorithms.

CHAPTER: DEUTSCH'S ALGORITHM

Deutsch's algorithm is the first algorithm to exploit quantum parallelism. It uses two qubits (only one in the economical version) and has a modest gain, but it has inspired the development of several new quantum algorithms that are more efficient than their classical counterparts. Deutsch's problem was posed in 1985 [17] without yet using the quantum circuit model. The concepts of universal gates and quantum circuits were first presented in [18], approximately four years later. A generalization of Deutsch's algorithm was described in [19] and is known as the Deutsch-Jozsa algorithm (see the next Chapter). The version described here follows the modern view of Deutsch's algorithm [14, 45], which differs slightly from the original one. In the final Section, we describe an implementation of Deutsch's algorithm with only one qubit.

§ PROBLEM FORMULATION

Suppose we have a 1-bit Boolean function $f:\{0,1\}\longrightarrow\{0,1\}$ without knowing the details of the implementation of $f$. We want to determine whether this function is balanced or constant. A 1-bit Boolean function is balanced if $f(0)\neq f(1)$; otherwise, the function is constant, in which case $f(0)=f(1)$. There are four Boolean functions $f$, whose truth tables are described in Fig. <ref> with names $f_0$ to $f_3$.

$x$     $f_0(x)$     $f_1(x)$     $f_2(x)$     $f_3(x)$

0     0     0     1     1

1     0     1     0     1

Truth tables of all 1-bit Boolean functions.

The disjunctive normal forms are

\begin{align*}
&f_2(x)=\bar x,\\
&f_3(x)=\bar x\vee x,
\end{align*}

where $\bar x=\text{NOT}\, x$. The Boolean expression of $f_3$ can be simplified since $\bar x\vee x=1$.

A classical algorithm that finds the solution to this problem needs to evaluate $f$ twice, meaning it must evaluate both $f(0)$ and $f(1)$. However, Deutsch's algorithm uses a unitary operator $U_f$ that implements $f$ and calls this operator only once. In this case, $f(0)$ and $f(1)$ are also evaluated, but the difference is that the evaluations are performed simultaneously. This idea is used recurrently in quantum algorithms.

In the quantum case, $f$ is implemented through a 2-qubit unitary operator $U_f$ defined as

\[
U_f\ket{x}\ket{j}=\ket{x}\ket{j\oplus f(x)},
\]

where $\oplus$ is the XOR operation or addition modulo 2. This is a recipe that can be used to implement an arbitrary $n$-bit Boolean function. We must ensure that $x$ is the input to the first register, and to obtain $f(x)$, we set $j=0$ as the input to the second register and then we look at the output of the second register. Now we use the technique described in Chapter <ref> to obtain the quantum circuit of functions $f_0$ to $f_3$. We use their disjunctive normal forms and we have to use one multiqubit Toffoli gate for each output 1 in the truth table. In the case of two qubits, a multiqubit Toffoli gate is a CNOT activated by either 0 or 1. There is no output 1 in the truth table of $f_0$. Then,

$$U_{f_0}=I\otimes I.$$

There is one output 1 in the truth table of $f_1$, which corresponds to input 1. We use the standard CNOT, which is activated when the control is set to 1. Then,

There is one output 1 in the truth table of $f_2$, which corresponds to input 0. We use the CNOT that is activated when the control is set to 0. Then,

$$U_{f_2}=(X\otimes I)\cdot \text{CNOT} \cdot (X\otimes I).$$

Finally, there are two outputs 1 in the truth table of $f_3$ with inputs 0 and 1. We use the standard CNOT and the CNOT that is activated when the control is set to 0. Then,

$$U_{f_3}=(X\otimes I)\cdot \text{CNOT} \cdot (X\otimes I) \cdot \text{CNOT}.$$

It is evident that using the general recipe to implement Boolean functions based on their truth tables can produce unnecessarily large circuits. In such cases, it is necessary to simplify the Boolean expression before building the circuit. At this point, there is no specific recipe to guide us, except for our skill in handling Boolean functions and designing circuits. For $f_3$, we know that $f_3(x)=1$ and the output must be 1 regardless of the input $x$ to the first qubit. Since the input to the second qubit is 0, output 1 is obtained by using a $X$. Then, the simplified version of $U_{f_3}$ is

$$U_{f_3}=I\otimes X.$$

Note that $U_f$ is unitary in all cases.

§ THE ALGORITHM

Deutsch's algorithm
A Boolean function $f:\{0,1\}\longrightarrow \{0,1\}$.
$0$ if $f$ is constant, 1 if $f$ is balanced. Prepare the initial state $\ket{0}\ket{1}$
Apply $H\otimes H$
Apply $U_f$
Apply $H\otimes H$
Measure the first qubit in the computational basis.

Deutsch's algorithm is described in Algorithm <ref> and the (non-economical) circuit is

\[
\Qcircuit @C=2.0em @R=1.6em {
\lstick{\ket{0}}        & \gate{H} & \multigate{1}{\,\,\,U_f\,\,\,} & \gate{H} & \meter  & \rstick{f(0)\oplus f(1)} \cw \\
\lstick{\ket{1}}        & \gate{H} & \ghost{\,\,\,U_f\,\,\,}        & \gate{H}&   \rstick{\ket{1}.} \qw \\
\ustick{\hspace{0.7cm}\ket{\psi_0}} & \ustick{\hspace{1.4cm}\ket{\psi_1}}& \ustick{\hspace{2.0cm}\ket{\psi_2}} & \ustick{\hspace{1.4cm}\ket{\psi_3}}
\]

We easily check that the circuit corresponds exactly to the steps of Algorithm <ref>. The output $f(0)\oplus f(1)$ is $0$ if $f$ is constant, and 1 if $f$ is balanced. Note that the last Hadamard gate applied to the second qubit can be eliminated without affecting the algorithm. This gate is here because the central part of the circuit is symmetric and the analysis of the algorithm is neater with it than without it. The states at the bottom of the circuit are used in the analysis of the algorithm.

§ ANALYSIS OF THE ALGORITHM

After the first step, the state of the qubits is

\[
\ket{\psi_0}=\ket{0}\otimes\ket{1}.
\]

After the second step, the state of the qubits is

\begin{eqnarray*}
\ket{\psi_1} &=& (H\ket{0})\otimes(H\ket{1})\\
&=&\frac{\ket{0}+\ket{1}}{\sqrt 2}\otimes \ket{-},
\end{eqnarray*}

where $\ket{-}=(\ket{0}-\ket{1})/\sqrt 2$. After the third step, the state of the qubits is

\begin{eqnarray*}
\ket{\psi_2} &=& U_f\ket{\psi_1}\\
&=&\frac{U_f\ket{0}\ket{-}+U_f\ket{1}\ket{-}}{\sqrt 2}.
\end{eqnarray*}

To simplify $\ket{\psi_2}$, let us show the following proposition:

Let $f:\{0,1\}^n\longrightarrow\{0,1\}$ be a $n$-bit Boolean function and define $U_f$ as

\[
U_f=\sum_{x\in \{0,1\}^n}\sum_{j=0}^1 \, \ket{x,j\oplus f(x)}\bra{x,j}.
\]

\[
U_f\big(\ket{x}\otimes\ket{-}\big) \,=\,(-1)^{f(x)}\ket{x}\otimes\ket{-}.
\]

Using the definition of $\ket{-}$, we obtain

\[
U_f\big(\ket{x}\otimes\ket{-}\big) \,=\, \frac{U_f\ket{x}\ket{0}-U_f\ket{x}\ket{1}}{\sqrt 2}.
\]

Using the definition of $U_f$, we obtain

\[
U_f\big(\ket{x}\otimes\ket{-}\big) \,=\, \frac{\ket{x}\ket{f(x)}-\ket{x}\ket{1\oplus f(x)}}{\sqrt 2}.
\]

If $f(x)=0$, the right-hand side is $\ket{x}\ket{-}$ and if $f(x)=1$, the right-hand side is $-\ket{x}\ket{-}$. Then, joining these results together, we have $(-1)^{f(x)}\ket{x}\otimes\ket{-}$.

Using the proposition above, $\ket{\psi_2}$ simplifies to

\begin{eqnarray*}
\ket{\psi_2}
&=&\frac{(-1)^{f(0)}\ket{0}+(-1)^{f(1)}\ket{1}}{\sqrt 2}\otimes \ket{ -}\\
&=& \begin{cases}
\pm\,\ket{+}\otimes\ket{-}, & \text{if }f(0)=f(1),\\
\pm\,\ket{-}\otimes\ket{-}, & \text{if }f(0)\neq f(1).
\end{cases}
\end{eqnarray*}

In the last passage, we have simplified the state of the first qubit without specifying exactly what is the sign of the amplitude. This sign has no effect on the output of the algorithm.
After the fourth step, the state of the qubits is

\begin{eqnarray*}
\ket{\psi_3} &=& (H\otimes H)\ket{\psi_2}\\
&=& \begin{cases}
\pm\,\ket{0}\otimes\ket{1}, & \text{if }f(0)=f(1),\\
\pm\,\ket{1}\otimes\ket{1}, & \text{if }f(0)\neq f(1),
\end{cases}
\end{eqnarray*}

where we have used the fact that $H\ket{+}=\ket{0}$ and $H\ket{-}=\ket{1}$, which can be deducted using $\ket{+}=H\ket{0}$, $\ket{-}=H\ket{1}$, and $H^2=I$. The state $\ket{\psi_3}$ can be further simplified to

\begin{eqnarray*}
\ket{\psi_3} &=& \pm \,\ket{f(0)\oplus f(1)}\otimes\ket{1}.
\end{eqnarray*}

After the fifth step, the measurement of the first qubit in the computational basis returns $f(0)\oplus f(1)$, which is $0$ if $f$ is constant and 1 if $f$ is balanced, concluding the analysis of the algorithm.

Note that the sign of $\ket{\psi_3}$ has no influence on the measurement result because the probability of obtaining $f(0)\oplus f(1)$ is $|\pm 1|^2=1.$ It is easy to check, if relevant, that this sign is $(-1)^{f(0)}$.

§ ANALYSIS OF THE ENTANGLEMENT

Summarizing the set of states of the qubits after each step, we have

\begin{align*}
\ket{\psi_0}&=\ket{0}\otimes\ket{1},\\
\ket{\psi_1}&=\ket{+}\otimes\ket{-},\\
\ket{\psi_2}&=\begin{cases}
\pm\,\ket{+}\otimes\ket{-}, & \text{if }f(0)=f(1),\\
\pm\,\ket{-}\otimes\ket{-}, & \text{if }f(0)\neq f(1),
\end{cases}\\
\ket{\psi_3}&=\pm \,\ket{f(0)\oplus f(1)}\otimes\ket{1}.
\end{align*}

Regardless of $f$, the qubits are unentangled during the execution of Deutsch's algorithm because each state $\ket{\psi_i}$ for $i$ from 1 to 3 is a tensor product of 1-qubit pure states. The qubits are unentangled all the time. This means that Deutsch's algorithm is faster than classical algorithms making use of quantum parallelism only.

There is an alternate route to analyze entanglement. No 2-qubit operator $A\otimes B$ creates or destroys entanglement. In Deutsch's algorithm, only CNOT can create entanglement and it is used at most one time. Then, for each function $f$ we can simplify the whole algorithm in order to obtain only one final operator, whose input is $\ket{01}$. If we simplify the algorithm for each $f$, we obtain

\begin{align*}
(H\otimes H)\, U_{f_0} (H\otimes H) &= (H\otimes H)\cdot (H\otimes H) = I\otimes I  ,\\
(H\otimes H)\, U_{f_1} (H\otimes H) &= (H\otimes H)\cdot\text{CNOT}\cdot (H\otimes H) = \text{CNOT}_{10}  ,\\
(H\otimes H)\, U_{f_2} (H\otimes H) &= (Z\otimes I)\cdot \text{CNOT}_{10}\cdot (Z\otimes I),\\
(H\otimes H)\, U_{f_3} (H\otimes H) &=  I\otimes Z,
\end{align*}

where the control of $\text{CNOT}_{10}$ is the second qubit and the target is the first qubit. We conclude right away that no entanglement is created when $f$ is $f_0$ or $f_3$. For $f_1$ and $f_2$, the CNOT's control qubit is set to 1 because the input is $\ket{01}$, in these cases, no entanglement is created because CNOT creates entanglement only if the state of the control qubit is a superposition state.

We can take advantage of the simplified version of the algorithm to check the output again and reanalyze the algorithm. The states of the qubits just before the measurement are

\begin{align*}
\ket{\psi_3}\big|_{f_0} &= (I\otimes I)\ket{0,1}=\ket{0,1},\\
\ket{\psi_3}\big|_{f_1} &= \text{CNOT}_{10}\ket{0,1} =\ket{1,1},\\
\ket{\psi_3}\big|_{f_2} &= (Z\otimes I)\cdot \text{CNOT}_{10}\cdot (Z\otimes I)\ket{0,1} =-\ket{1,1},\\
\ket{\psi_3}\big|_{f_3} &= (I\otimes Z)\ket{0,1} =-\ket{0,1}.
\end{align*}

The output of a measurement of the first qubit is 0 for $f_0$ and $f_3$, which are the constant functions, and 1 for $f_1$ and $f_2$, which are the balanced functions. We can also check that the sign is $(-1)^{f(0)}$ because $f_0(0)=f_1(0)=+1$ and $f_2(0)=f_3(0)=-1$.

§ WHO IMPLEMENTS THE ORACLE?

Deutsch's algorithm is said to be more efficient than its classical counterpart in a limited context known as  “query complexity” [30]. In this context, we must compare the number of evaluations of $f$ in the classical case with the number of times $U_f$ is used in the quantum case. This is a rule of the game. Deutsch's algorithm applies $U_f$ only once and the classical algorithm needs to evaluate $f$ two times. Therefore, Deutsch's is faster.

The analysis of Deutsch's algorithm shows that $f$ is evaluated at two distinct points in the domain simultaneously. This is not possible using a sequential classical algorithm. However, it is possible to be carried out in a classical computer with parallel processors if the number of simultaneous threads does not scale up. Since Deutsch's algorithm uses a fixed number of qubits, we cannot scale it up and it is not possible to perform an asymptotic analysis. In terms of time complexity, the quantum version has no gain. The importance of Deutsch's algorithm lies in the fact that it stimulated the search for generalizations, such as the Deutsch-Jozsa, Bernstein-Vazirani, and Simon algorithms, which inspired Shor in the development of a quantum algorithm for factoring composite integers and a quantum algorithm for calculating discrete logarithms.

Lastly, it is important to note that implementing the oracle is not our responsibility. It is someone else's job. Without this understanding, we face a contradiction—we need to know the answer before even starting to implement the algorithm that will find the answer. We are allowed to query function $f$ implemented by someone else without looking at its implementation details. We are given what is called a black box quantum computer with $U_f$ already implemented, which we can use more than once, and we may add new gates, but cannot examine the inner workings of the black box that implements $U_f$.

§ ECONOMICAL CIRCUIT OF DEUTSCH'S ALGORITHM

Deutsch's algorithm can be implemented with only one qubit in the following way:

\[
\Qcircuit @C=2.0em @R=1.6em {
\lstick{\ket{0}}        & \gate{H} & \gate{\,\,\,{U'_f}^{\mbox{}}\,\,\,} & \gate{H} & \meter  & \rstick{f(0)\oplus f(1),} \cw
\]

\[
U'_f = \sum_{x=0}^1 (-1)^{f(x)}\ket{x}\bra{x}.
\]

From Proposition <ref>, we see that the second qubit is not necessary for the algorithm, although it is necessary if we want to obtain $f(x)$ in the classical sense, as shown ahead. By expanding the sum, we obtain

\[
U'_f = \left[\begin{array}{cc}
(-1)^{f(0)} & 0 \\
0 & (-1)^{f(1)}
\end{array}\right].
\]

\[
U'_f=\begin{cases} \pm I, \text{ if }f(0)=f(1), \\ \pm Z, \text{ if }f(0)\neq f(1). \end{cases}
\]

The analysis of the algorithm reduces to calculating

\begin{eqnarray*}
HU'_fH \ket{0}= \begin{cases}
\pm\,I\ket{0}, & \text{if }f(0)=f(1),\\
\pm\,X\ket{0}, & \text{if }f(0)\neq f(1).
\end{cases}
\end{eqnarray*}

Using that $f(0)\oplus f(1)=0$ if $f(0)=f(1)$, and $f(0)\oplus f(1)=1$ if $f(0)\neq f(1)$, we obtain

\[
HU'_fH \ket{0}= \pm \ket{f(0)\oplus f(1)}.
\]

After a measurement, the output is $f(0)\oplus f(1)$ with probability $|\pm 1|^2=1$.

Now it is straightforward to check that there is no entanglement in Deutsch's algorithm because a qubit cannot entangle with itself. Entanglement requires at least two qubits.

§.§ Consulting the oracle

In the non-economical circuit, if the input to the first qubit of $U_f$ is $\ket{x}$, $U_f$ returns $f(x)$ when we perform a measurement of the second qubit. In the economical circuit, we obtain $f(x)$ in the classical sense using the circuit

\[
\Qcircuit @C=2.0em @R=1.6em {
\lstick{\ket{x}}        & \qw & \gate{U'_f}        & \qw&   \rstick{\ket{x}} \qw \\
\lstick{\ket{0}}        & \gate{H} & \ctrl{-1} & \gate{H} & \meter  & \rstick{f(x).} \cw
\]

Indeed, the steps of this circuit are

\begin{align*}
\ket{x}\ket{0} \xrightarrow[\text{}]{I\otimes H} \ket{x}\ket{+} \xrightarrow[\text{}]{\fbox{$U'_f$}-\bullet} \frac{\ket{x}\ket{0}+(-1)^{f(x)}\ket{x}\ket{1}}{\sqrt 2} \xrightarrow[\text{}]{I\otimes H} \ket{x}\ket{f(x)}.
\end{align*}

To calculate the last step, we use that $f(x)$ is either 0 or 1 for a fixed $x$. Firstly, we suppose that $f(x)=0$, then $I\otimes H$ is applied to $\ket{x}\ket{+}$ resulting in $\ket{x}\ket{f(x)}$, and secondly, we suppose that $f(x)=1$, then $I\otimes H$ is applied to $\ket{x}\ket{-}$ resulting in $\ket{x}\ket{f(x)}$. After measuring the second qubit in the computational basis, we obtain $f(x)$ with probability 1.

CHAPTER: DEUTSCH-JOZSA ALGORITHM

The Deutsch-Jozsa algorithm is a deterministic quantum algorithm, a generalization of Deutsch's algorithm, and the first example that is exponentially faster than its equivalent classical deterministic algorithm. It was published in 1992 [19] and revisited in 1998 [14]. Many books [30, 34, 37, 40, 45, 65] and papers [43, 52, 53] have reviewed and generalized this algorithm.

§ PROBLEM FORMULATION

Let $f:\{0,1\}^n \longrightarrow \{0,1\}$ be a $n$-bit Boolean function, $n\ge 2$, with the following property: $f$ is either balanced or constant. A Boolean function is balanced if the inverse image of point 0 has cardinality $2^{n-1}$, and it is constant if the inverse image of point 0 has cardinality 0 or $2^{n}$. Suppose we are able to evaluate this function at any point in the domain; however, we don't have access to the details of the implementation of $f$, that is, we are given a black-box quantum computer with $f$ already implemented. The Deutsch-Jozsa algorithm solves the following problem: Determine whether $f$ is balanced or constant using this black-box quantum computer.

There are only two constant functions, which are $f(x)=0$ and $f(x)=1$ for all $n$-bit string $x$, but there are many balanced functions. The best classical deterministic algorithm that solves this problem, given a black-box function $f$ that is either balanced or constant implemented on a $n$-bit classical computer, is the following: Evaluate $f$ at $2^{n-1}+1$ distinct points in its domain and check whether the output is always the same ($f$ is constant) or not ($f$ is balanced).

The Deutsch-Jozsa algorithm, on the other hand, is a deterministic quantum algorithm that uses a black-box unitary operator $U_f$ only once. The action of $U_f$ on the computational basis is

\[
U_f\ket{x}\ket{j}=\ket{x}\ket{j\oplus f(x)},
\]

where $x\in\{0,1\}^n$ and $j\in\{0,1\}$. The qubits are split into two quantum registers with sizes $n$ and 1.[A quantum register is a set of qubits.] After making a superposition of vectors $\ket{x}$ for all $x$, the Deutsch-Jozsa algorithm is able to compute $f(x)$ for all $x$ with a single application of $U_f$ and after quick post-processing is able to determine whether $f$ is constant or balanced.

In the next proposition, we show that $U_f$ is unitary. Then, since each entry of $U_f$ is either 0 or 1, $U_f$ is a $2^{n+1}$-dimensional permutation matrix.[A permutation matrix is a square binary matrix such that each row and each column has exactly one entry equal to 1 and zeroes elsewhere.]

$U_f$ is unitary for any $n$-bit Boolean

Let us show that $U_f^\dagger U_f=I$. Using the definition of $U_f$, we have

\begin{align*}
\bra{x'}\bra{j'}U_f^\dagger U_f\ket{x}\ket{j} &= \braket{x'}{x}\,\braket{j'\oplus f(x')}{j\oplus f(x)}\\
&= \delta_{xx'}\,\braket{j'\oplus f(x')}{j\oplus f(x)}.
\end{align*}

Using that $\delta_{xx'}\neq 0$ only if $x=x'$, we have $\delta_{xx'}\braket{j'\oplus f(x')}{j\oplus f(x)}=\delta_{xx'}\braket{j'}{j}$. Then

\begin{align*}
\bra{x'}\bra{j'}U_f^\dagger U_f\ket{x}\ket{j} &= \delta_{xx'}\delta_{jj'}.
\end{align*}

Since $j,j'$ are arbitrary bits and $x,x'$ arbitrary $n$-bit strings, the proof is done.

§ THE QUANTUM ALGORITHM

Deutsch-Jozsa algorithm
A black-box $U_f$ implementing a $n$-bit Boolean function $f:\{0,1\}^n\longrightarrow \{0,1\}$, which is either balanced or constant.
$0$ if $f$ is constant; otherwise, $f$ is balanced. Prepare the initial state $\ket{0}^{\otimes n}\ket{1}$
Apply $H^{\otimes(n+1)}$
Apply $U_f$
Apply $H^{\otimes(n+1)}$
Measure the first register in the computational basis.

The Deutsch-Jozsa algorithm is described in Algorithm <ref> and the $(n+1)$-qubit circuit is

\[
\Qcircuit @C=2.0em @R=1.6em {
\lstick{\ket{0}}        & \gate{H} & \multigate{3}{\,\,\,U_f\,\,\,} & \gate{H} & \meter  & \rstick{0 \text{ or } 1} \cw \\
\lstick{\vdots}         & \vdots   &                                & \vdots   &  \vdots  & \rstick{}  \\
\lstick{\ket{0}}        & \gate{H} & \ghost{\,\,\,U_f\,\,\,}        & \gate{H} & \meter  & \rstick{0 \text{ or } 1} \cw \\
\lstick{\ket{1}}        & \gate{H} & \ghost{\,\,\,U_f\,\,\,}        & \gate{H} & \rstick{\ket{1}.} \qw \\
\ustick{\hspace{0.7cm}\ket{\psi_0}} & \ustick{\hspace{1.4cm}\ket{\psi_1}}& \ustick{\hspace{2.0cm}\ket{\psi_2}} & \ustick{\hspace{1.4cm}\ket{\psi_3}}
\]

We easily check that the circuit corresponds exactly to the steps of Algorithm <ref>. The output is the $n$-bit string $0$ if $f$ is constant, and different from $0$ if $f$ is balanced. Note that the last Hadamard gate applied to the last qubit can be eliminated without affecting the algorithm. This gate is here because the central part of the circuit is symmetric and the analysis of the algorithm is neater with it than without it. The states at the bottom of the circuit are used in the analysis of the algorithm.

§ ANALYSIS OF THE ALGORITHM

After the first step, the state of the qubits is

\[
\ket{\psi_0}=\ket{0}^{\otimes n}\otimes\ket{1}.
\]

After the second step, the state of the qubits is

\begin{eqnarray*}
\ket{\psi_1} &=& (H\ket{0})^{\otimes n}\otimes(H\ket{1})\\
\end{eqnarray*}

where $\ket{-}=(\ket{0}-\ket{1})/\sqrt 2$. After the third step, the state of the qubits is

\begin{eqnarray*}
\ket{\psi_2} &=& U_f\ket{\psi_1}\\
\end{eqnarray*}

To simplify $\ket{\psi_2}$, we use Proposition <ref> on Page prop:U_fxminus, which states that

\[
U_f\big(\ket{x}\ket{-}\big) \,=\, (-1)^{f(x)}\ket{x}\ket{-}.
\]

We obtain

\[
\ket{\psi_2} \,=\,\frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1} (-1)^{f(x)}\ket{x}\ket{-}.
\]

After the fourth step, the state of the qubits is

\begin{eqnarray*}
\ket{\psi_3} &=& H^{\otimes (n+1)}\ket{\psi_2}\\
&=&  \frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1} (-1)^{f(x)} \big(H^{\otimes n}\ket{x}\big)\otimes \big(H\ket{-}\big).
\end{eqnarray*}

To simplify $\ket{\psi_3}$, let us show the following proposition:

Let $x\in\{0,1\}^n$ be a $n$-bit string $x_0\cdots x_{n-1}$.

\[
H^{\otimes n}\ket{x} \,=\, \frac{1}{\sqrt{2^n}}\sum_{y=0}^{2^n-1}(-1)^{x\cdot y}\ket{y},
\]

where $x\cdot y=x_{0}y_{0}+  \cdots + x_{{n-1}}y_{{n-1}}\mod 2$.

Using that $x=(x_0\cdots x_{n-1})_2$,
we obtain

\begin{eqnarray*}
H^{\otimes n}\ket{x} &=& \big(H\ket{x_0}\big)\otimes \cdots \otimes \big(H\ket{x_{n-1}}\big) \\
&=&  \Big(\frac{1}{\sqrt{2}}\sum_{y_0=0}^{1} (-1)^{x_0y_0} \ket{y_0}\Big)\otimes \cdots \otimes \Big(\frac{1}{\sqrt{2}}\sum_{y_{n-1}=0}^{1} (-1)^{x_{n-1}y_{n-1}} \ket{y_{n-1}}\Big).
\end{eqnarray*}

Putting all sums at the beginning, we obtain

\begin{eqnarray*}
H^{\otimes n}\ket{x} &=& \frac{1}{\sqrt{2^n}}\sum_{y_0=0}^{1}\,\,\cdots \sum_{y_{n-1}=0}^{1} (-1)^{\left(x_0y_0+\cdots+x_{n-1}y_{n-1}\right)} \ket{y_0}\otimes \cdots \otimes \ket{y_{n-1}}.
\end{eqnarray*}

Using the definition of $x\cdot y$ and converting to the decimal notation, we complete the proof.

Using the proposition above, $\ket{\psi_3}$ simplifies to

\begin{equation*}
\ket{\psi_3}\,=\,\frac{1}{{2^n}}\sum_{y=0}^{2^n-1}\left(\sum_{x=0}^{2^n-1}(-1)^{x\cdot y+f(x)}\right)\ket{y}\otimes\ket{1}.
\end{equation*}

The amplitude of state $\ket{0}\ket{1}$ (0 in decimal) is

\begin{equation*}
\frac{1}{{2^n}}\sum_{x=0}^{2^n-1}(-1)^{f(x)}.
\end{equation*}

The probability that a measurement of the first register returns $y=0$ (in decimal) is

\begin{equation*}
\end{equation*}

If $f$ is constant, $p(0)=1$ and we know with certainty that the output is $y=0$. If $f$ is balanced, $p(0)=0$ and we know with certainty that the output is $y\neq 0$.

§ ANALYSIS OF THE ENTANGLEMENT

There is no entanglement between the registers because $\ket{\psi_0}$ to $\ket{\psi_3}$ can be written either as $\ket{\psi}\otimes\ket{1}$ or $\ket{\psi}\otimes\ket{-}$, for some state $\ket{\psi}$. We have to check the first register only.
From the circuit of the algorithm, we realize that the only operator that creates or destroys entanglement is $U_f$. Then, it is enough to analyze

\[
\ket{\psi} \,=\,\frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1} (-1)^{f(x)}\ket{x},
\]

which is the state of the first register after applying $U_f$. We ask ourselves whether there are $a_i$ and $b_i$ so that

\[
\ket{\psi} \,=\,\frac{a_0\ket{0}+b_0\ket{1}}{\sqrt{2}}\otimes\cdots\otimes\frac{a_{n-1}\ket{0}+b_{n-1}\ket{1}}{\sqrt{2}},
\]

where each pair $(a_i,b_i)$ must obey $|a_i|^2+|b_i|^2=2$.  This is the only way of having no entanglement at all.
Equivalently, we ask whether the system of equations

\begin{align*}
a_0...a_{n-2}a_{n-1} &= (-1)^{f(0...00)}\\
a_0...a_{n-2}b_{n-1} &= (-1)^{f(0...01)}\\
a_0...b_{n-2}a_{n-1} &= (-1)^{f(0...10)}\\
a_0...b_{n-2}b_{n-1} &= (-1)^{f(0...11)}\\
b_0...b_{n-2}b_{n-1} &= (-1)^{f(1...11)}
\end{align*}

admits a solution or not. It is straightforward to check that $a_i\neq 0$ and $b_i\neq 0$ for all $i$. Besides, we need not worry about phases of $a_i$. In fact, without loss of generality, we consider $a_i$ real and positive because a global factor can be discarded. Then, by selecting equation

\begin{align*}
b_0a_1a_2...a_{n-2}a_{n-1} &= (-1)^{f(1...00)},
\end{align*}

we conclude that $b_0$ is also real. The same applies to the other $b_i$. Now, let us show that $a_i= 1$ and $b_i=\pm 1$. Let us start with $a_0$ and $b_0$ by selecting the following equations:

\begin{align*}
a_0a_1a_2...a_{n-2}a_{n-1} &= (-1)^{f(0...00)},\\
b_0a_1a_2...a_{n-2}a_{n-1} &= (-1)^{f(1...00)}.
\end{align*}

Dividing them, we obtain $a_0\pm b_0 =0$. This result together with the constraint $a_0^2+b_0^2=2$ implies that $a_0=1$ and $b_0=\pm 1$. The same applies to the other $a_i$ and $b_i$. Now, counting the number of unentangled states, we obtain at most $2^{n}$, up to a global sign. Or, at most $2^{n+1}$.

There are only two constant functions: $f(x)=0$ and $f(x)=1$ for all $x$, which correspond to $\ket{\psi}=\big(H\ket{0}\big)^{\otimes n}$ and $\ket{\psi}=-\big(H\ket{0}\big)^{\otimes n}$, respectively. In both cases, there is no entanglement. Then, let us count the number of balanced functions. The exact number is the number of subsets with cardinality $2^{n-1}$ because as soon as we find such a subset $S$, we define a balanced function taking $f(x)=0$ if $x\in S$ and $f(x)=1$ otherwise. When we cover all such subsets, we have obtained all balanced functions. Since the domain has cardinality $2^n$, the number of balanced functions is $\binom{2^n}{2^{n-1}}$.[An alternative way of counting the number of balanced functions is by considering the number of permutations of a list with $2^{n-1}$ zeros and $2^{n-1}$ ones.]

The number of balanced functions grows quicker than the number of unentangled states. Indeed, using the asymptotic approximation[<https://en.wikipedia.org/wiki/Binomial_coefficient>]

\[
\binom{2p}{p}\approx \frac{2^{2p}}{\sqrt{\pi p}}
\]

we obtain

\[
\binom{2^n}{2^{n-1}}\approx \frac{\sqrt{2}}{\sqrt{\pi}}\frac{2^{2^n}}{\sqrt{2^n}}.
\]

We conclude that when $n$ increases, there are more and more balanced functions $f$ with $U_f$ creating entanglement.

The discussion above shows that there is $n_0\ge 2$, such that for all $n\ge n_0$, $U_f$ creates entanglement. Since, $\binom{2^n}{2^{n-1}}>2^{n+1}$ for $n\ge 3$, we can take $n_0=3$. The only remaining case that may have no entanglement is $n=2$. For $n=2$, there are 6 balanced functions, whose truth tables are described in Fig. <ref> with function names $f_0$ to $f_5$.

$x_0\,\,x_1$     $f_0(x)$     $f_1(x)$     $f_2(x)$     $f_3(x)$     $f_4(x)$     $f_5(x)$

0    0     0     0     0     1     1     1

0    1     0     1     1     0     0     1

1    0     1     0     1     0     1     0

1    1     1     1     0     1     0     0

Truth tables of all 2-bit balanced functions.

It is enough to analyze $f_0$ to $f_2$ because the other functions complement those ones. For instance, $f_5$ is the complement of $f_0$, which means that state $\ket{\psi}$ created by $U_{f_5}$ is equal to the state created by $U_{f_0}$ up to a global phase. States $\ket{\psi}$ that correspond to $f_0$ to $f_2$ (without normalization) are

\begin{align*}
\ket{00}+\ket{01}-\ket{10}-\ket{11} &= \big(\ket{0}-\ket{1}\big)\otimes\big(\ket{0}+\ket{1}\big),\\
\ket{00}-\ket{01}+\ket{10}-\ket{11} &= \big(\ket{0}+\ket{1}\big)\otimes\big(\ket{0}-\ket{1}\big),\\
\ket{00}-\ket{01}-\ket{10}+\ket{11} &= \big(\ket{0}-\ket{1}\big)\otimes\big(\ket{0}-\ket{1}\big),
\end{align*}

respectively. All those states are unentangled. We conclude that there is no entanglement in the Deutsch-Jozsa algorithm when $n=2$.

§ IMPLEMENTING THE ORACLE

In general, it is not up to us to implement the oracle, unless there is a formula for $f$ that doesn't reveal the solution beforehand. Without this understanding, we face a contradiction—we have to know the answer before starting to implement the algorithm that will find the answer. It is allowed to us to evaluate function $f$ without looking at its implementation details. We are given what is called a black-box quantum computer with $U_f$ already implemented, which we can use and add new gates, but cannot see inside. In the classical case, we have to count the number of evaluations of $f$. In the quantum case, we have to count the number of applications of $U_f$. This is how we calculate the query complexity of oracle-based algorithms. Note that it does not matter whether the evaluation of $f$ is efficient or not.

With this understanding, let us show how to implement oracle $U_f$ for the following entangling balanced function: $f(x)=0$ if $x\in\{000,010,100,101\}$ and $f(x)=1$ if $x\in\{001,011,110,111\}$. Using the disjunctive normal form, we add to the circuit one multiqubit Toffoli gate for each point in $\{001,011,110,111\}$, as follows

\[
\Qcircuit @C=2.3em @R=1.9em {
\lstick{\ket{x_0}}    & \ctrlo{1} & \ctrlo{1} & \ctrl{1} & \ctrl{1} &  \rstick{\ket{x_0}} \qw \\
\lstick{\ket{x_1}}    & \ctrlo{1} & \ctrl{1} & \ctrl{1} & \ctrl{1} &  \rstick{\ket{x_1}} \qw \\
\lstick{\ket{x_2}}    & \ctrl{1} & \ctrl{1} & \ctrlo{1} & \ctrl{1} & \rstick{\ket{x_2}} \qw \\
\lstick{\ket{0}}  & \targ  & \targ  & \targ  & \targ  &  \rstick{\ket{f(x)}.}  \qw \\
\]

Since the first and second gates have opposite controls in the second qubit and identical controls in the first and third qubits (the third and fourth gates have a similar feature), this circuit can be simplified to

\[
\Qcircuit @C=2.3em @R=1.9em {
\lstick{\ket{x_0}}    & \ctrlo{2} & \ctrl{1} &  \rstick{\ket{x_0}} \qw \\
\lstick{\ket{x_1}}    & \qw & \ctrl{2} &  \rstick{\ket{x_1}} \qw \\
\lstick{\ket{x_2}}    & \ctrl{1} & \qw & \rstick{\ket{x_2}} \qw \\
\lstick{\ket{0}}  & \targ  & \targ  &  \rstick{\ket{f(x)}.}  \qw \\
\]

This example helps to show how to implement any balanced oracle using $n+1$ qubits. It is possible to implement the Deutsch-Jozsa algorithm with only $n$ qubits, but this discussion is postponed and fully addressed in Chapter <ref>.

§ FINAL REMARKS

There are efficient randomized classical algorithms that solve the Deutsch-Jozsa problem.
It is possible to find the correct solution with high probability by consulting the classical oracle a few times. More formally, consider the following randomized algorithm: (1) Select uniformly at random $k\ge 2$ points $x_0$, ..., $x_{k-1}$ in the domain, repetitions are allowed, (2) if $f(x_0)=\cdots=f(x_{k-1})$, return “$f$ is constant”; otherwise, return “$f$ is balanced”. This algorithm returns the output “$f$ is balanced” with certainty because as soon as we obtain two different values after evaluating $f$, we claim the promise that $f$ is either balanced or constant—it must be balanced. The probability that the output “$f$ is constant” is correct is $1-1/2^{k-1}$.[To calculate the probability that the output “$f$ is constant” is correct, we start by calculating the probability that “$f$ is constant” is wrong. The output “$f$ is constant” is wrong when $f$ is balanced and $f(x_0)=\cdots=f(x_{k-1})$. The probability that $f(x_0)=\cdots=f(x_{k-1})=0$ is $1/2^k$ because each evaluation is independent. Likewise, the probability that $f(x_0)=\cdots=f(x_{k-1})=1$ is $1/2^k$. Then, the probability that “$f$ is constant” is wrong is $2/2^k$ because all results equal to 0 and all results equal to 1 are mutually exclusive. Then, the probability that “$f$ is constant” is correct is $1-1/2^{k-1}$.] The success probability quickly tends to 1, for instance, take $k=10$, the success probability is at least 99.8%.

CHAPTER: BERNSTEIN-VAZIRANI ALGORITHM

The Bernstein-Vazirani algorithm was first presented at a conference in 1993 [8], and the full paper was published in 1997 [9]. It was the the first deterministic quantum algorithm to demonstrate a linear gain over the best deterministic or randomized classical algorithm. The Bernstein-Vazirani algorithm exploits quantum parallelism, but interestingly, it has no entanglement at all. This algorithm is described in some books [40, 44, 54].

§ PROBLEM FORMULATION

Let $s=s_0...s_{n-1}$ be an unknown $n$-bit string. Although we don't know $s$, we have at our disposal a Boolean function $f:\{0,1\}^n\longrightarrow\{0,1\}$ defined as

\[
f(x)=s\cdot x=s_0x_0+...+s_{n-1}x_{n-1}\mod 2,
\]

where $x_0,...,x_{n-1}$ are the bits of $x$. Note that $f$ is a linear function and each linear Boolean function is characterized by a specific hidden $s$. Our goal is to find $s$ by evaluating $f$ without knowing its implementation details. In quantum computing, the operator that implements this function is called an oracle, as if an oracle reveals $f(x)$ without showing $s$ explicitly, and $f(x)$ can be used to determine $s$. When we build the circuit of the algorithm, $f$ is implemented by another person, because we don't know $s$. It is important to understand this, as it helps avoid the mistaken impression that we need to know the answer to find the answer, which is absurd.

In the classical version of this problem, we have to consult the classical oracle at least $n$ times. In fact, we chose $x=10...0$ and ask the oracle what $f(10...0)$ is. The answer is $s_0$. Next we choose $x=010...0$ and ask the oracle what $f(010...0)$ is. The answer is $s_1$. The last query is $f(0...01)$, whose answer is $s_{n-1}$. This shows that we need to consult the oracle $n$ times and there is no way to reduce this number without introducing an error in the algorithm. In the quantum case, we consult the quantum oracle only once, which allows us to find all bits of $s$, as described below.

In the quantum case, the function $f(x)=s\cdot x$ is implemented using the unitary operator $U_f$ of $n+1$ qubits, defined as

\[
U_f\ket{x}\ket{j}=\ket{x}\ket{j\oplus f(x)},
\]

where $x\in\{0,1\}^n$, $j$ is a bit, and $\oplus$ is the XOR operation or sum modulo 2. This operator uses two registers, with sizes $n$ and 1, respectively. We can use $U_f$ as many times as we wish. However, it is used only once in the Bernstein-Vazirani algorithm.

Summing up, the classical algorithm queries the classical oracle $n$ times using a $n$-bit classical computer. The quantum algorithm queries the quantum oracle only one time using a $(n+1)$-qubit quantum computer. In the last Section of this Chapter, we show that the algorithm can be implemented on a $n$-qubit quantum computer.

§ THE ALGORITHM

Bernstein-Vazirani algorithm
A Boolean function $f:\{0,1\}^n\longrightarrow \{0,1\}$ such that $f(x)=s\cdot x$.
$s$ with probability equal to 1. Prepare the initial state $\ket{0}^{\otimes n}\ket{1}$
Apply $H^{\otimes (n+1)}$
Apply $U_f$
Apply $H^{\otimes (n+1)}$
Measure the first register in the computational basis.

The Bernstein-Vazirani algorithm is described in Algorithm <ref> and the circuit is

\[
\Qcircuit @C=2.3em @R=0.9em {
\lstick{\ket{0}}        & \gate{H} & \multigate{4}{\,\,\,U_f\,\,\,} & \gate{H} & \meter  & \rstick{s_0} \cw \\
\lstick{\vdots \,\,\,}  & {\vdots} &                                &{\vdots}&{\vdots} & \rstick{\vdots}  \\
\lstick{}               &          &                                &&         & \rstick{}  \\
\lstick{\ket{0}}        & \gate{H} & \ghost{\,\,\,U_f\,\,\,}        & \gate{H}& \meter  & \rstick{s_{n-1}}  \cw\\
\lstick{\ket{1}}        & \gate{H} & \ghost{\,\,\,U_f\,\,\,}        & \gate{H}&   \rstick{\ket{1}.} \qw  \\
\lstick{}               &          &                                &&         & \rstick{}  \\
\ustick{\hspace{0.7cm}\ket{\psi_0}} & \ustick{\hspace{1.4cm}\ket{\psi_1}}& \ustick{\hspace{2.0cm}\ket{\psi_2}} & \ustick{\hspace{1.4cm}\ket{\psi_3}}
\]

This circuit is identical to the circuit of the Deutsch-Jozsa algorithm, with the only difference being the function used in the Bernstein-Vazirani algorithm, which need not be constant nor balanced. Furthermore, in the Deutsch-Jozsa algorithm, we check whether all outputs are 0 to conclude that the function is constant; otherwise, it is balanced. In the Bernstein-Vazirani algorithm, each output is valuable for determining the unknown $s$. The states at the bottom of the circuit are used in the analysis of the algorithm.

§ ANALYSIS OF THE ALGORITHM

After the first step, the state of the qubits is

\[
\ket{\psi_0}=\ket{0}^{\otimes n}\ket{1}.
\]

After the second step, the state of the qubits is

\begin{eqnarray*}
\ket{\psi_1} &=& (H^{\otimes n}\ket{0}^{\otimes n})\otimes(H\ket{1})\\
&=& \frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}\ket{x}\otimes \ket{-},
\end{eqnarray*}

where $\ket{-}=(\ket{0}-\ket{1})/\sqrt{2}$ and $x$ is written in the decimal notation. After the third step, the state of the qubits is

\begin{eqnarray*}
\ket{\psi_2} &=& U_f\ket{\psi_1}\\
&=& \frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1} U_f\ket{x}\otimes\ket{-}.
\end{eqnarray*}

To simplify $\ket{\psi_2}$, we use Proposition <ref> on Page prop:U_fxminus, which states that

\[
U_f\big(\ket{x}\ket{-}\big) \,=\, (-1)^{f(x)}\ket{x}\ket{-}.
\]

We obtain

\begin{eqnarray*}
\ket{\psi_2} &=& \frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}(-1)^{s\cdot x}\ket{x}\otimes\ket{-}.
\end{eqnarray*}

After the fourth step, the state of the qubits is

\begin{eqnarray}\label{eq:BV-psi3}
\ket{\psi_3} &=& H^{\otimes (n+1)}\ket{\psi_2}\nonumber\\
&=&  H^{\otimes n}\left(\frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}(-1)^{s\cdot x}\ket{x}\right)\otimes(H\ket{-}).
\end{eqnarray}

To simplify $\ket{\psi_3}$, we use Proposition <ref> on Page prop:Hnx, which states that for any $s=(s_0...s_{n-1})_2$

\[
H^{\otimes n}\ket{s} \,=\, \frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}(-1)^{s\cdot x}\ket{x},
\]

where $s\cdot x=s_{0}x_{0}+ \cdots + s_{{n-1}}x_{{n-1}}\mod 2$. Then we use $H^2=I$ to obtain

\[
\ket{s}=H^{\otimes n}\left(\frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}(-1)^{s\cdot x}\ket{x}\right).
\]

We replace this result in Eq. (<ref>) to obtain

\begin{eqnarray*}
\ket{\psi_3} &=&  \ket{s}\otimes\ket{1}.
\end{eqnarray*}

The output of the measurement of the first register is $s_0,...,s_{n-1}$ with probability 1 because $\ket{s}=\ket{s_0}\otimes\cdots\otimes\ket{s_{n-1}}$.

$U_f$ is applied only one time, so we say that a single query was made to the quantum oracle. Note that $U_f$ is applied to a superposition of all vectors of the computational basis, which means that $f$ is evaluated simultaneously at all points in the domain—all $n$-bit strings.  The result of this massive evaluation is a superposition state, which is often useless in many cases. However, in the Bernstein-Vazirani algorithm, applying $H^{\otimes n}$ to the first register at the end reveals $s$. Before the last step, $s$ was a phase. After, $s$ went into the kernel of a “ket”. This distinction is crucial because a phase is associated with the probability of obtaining a certain result, while the kernel of the “ket” is associated with the measurement result.

§ BERNSTEIN-VAZIRANI ALGORITHM HAS NO ENTANGLEMENT

The analysis of the entanglement follows at the beginning the same track used in the Deutsch-Jozsa algorithm.

Examining the algorithm's circuit, we realize that the only operator that creates or destroys entanglement is $U_f$.Thus, it is sufficient to analyze $\ket{\psi_2}$. There is entanglement in the Bernstein-Vazirani algorithm if and only if $\ket{\psi_2}$ is totally or partially entangled. State $\ket{\psi_2}$ is given by

\[
\ket{\psi_2} \,=\,\frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1} (-1)^{s\cdot x}\ket{x}\otimes\ket{-}.
\]

Proposition <ref> on Page prop:Hnx states that for any $s=(s_0...s_{n-1})_2$

\[
H^{\otimes n}\ket{s} \,=\, \frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}(-1)^{s\cdot x}\ket{x}.
\]

Then $\ket{\psi_2}$ can be written as

\[
\ket{\psi_2} \,=\,\big(H^{\otimes n}\ket{s}\big)\otimes\ket{-},
\]

which can be fully factorized as

\[
\ket{\psi_2} \,=\,\big(H\ket{s_0}\big)\otimes\cdots\otimes \big(H\ket{s_{n-1}}\big)\otimes\ket{-}.
\]

Note that $\ket{\psi_2}$ has no entanglement at all because it is the Kronecker product of 1-qubit pure states [41, 21].

§ CIRCUIT OF THE ORACLE

In oracle-based algorithms, the oracle is not implemented by us—it is implemented by someone else. However, it is important to know how it is done in order to understand the whole process. Let us show an example with $n=4$ and $s=1011$ that is enough to understand the general case. In this particular case, $f$ is

\[
f(x)=s\cdot x= x_0+x_2+x_3\mod 2
\]

and the action of $U_f$ on an arbitrary vector of the computational basis $\ket{x}\ket{j}$ is

\[
U_f\ket{x_0x_1x_2x_3}\ket{j}=\ket{x_0x_1x_2x_3}\ket{j\oplus f(x)}=
\ket{x_0x_1x_2x_3}\ket{j\oplus x_0 \oplus x_2 \oplus x_3}.
\]

Let CNOT$_{04}$ be the CNOT gate acting on qubits 0 and 4. Without showing qubits 1, 2, and 3, we have

\[
\text{CNOT}_{04}\ket{x_0}\ket{j}=\ket{x_0}X^{x_0}\ket{j}=\ket{x_0}\ket{j\oplus x_0}.
\]

If we use $\text{CNOT}_{04}$, $\text{CNOT}_{24}$, and $\text{CNOT}_{34}$, we generate the expected result $j\oplus x_0 \oplus x_2 \oplus x_3$ in the second register. Then,

\[
\]

whose circuit is

\[
\Qcircuit @C=1.3em @R=0.9em {
\lstick{\ket{x_0}}  & \ctrl{4}&\qw     & \qw       &\rstick{\ket{x_0}}\qw \\
\lstick{\ket{x_1}}  & \qw     &\qw     & \qw       &\rstick{\ket{x_1}}\qw \\
\lstick{\ket{x_2}}  & \qw     &\ctrl{2}& \qw       &\rstick{\ket{x_2}}\qw \\
\lstick{\ket{x_3}}  & \qw     &\qw     & \ctrl{1}  &\rstick{\ket{x_3}}\qw \\
\lstick{\ket{j}}    & \targ   &\targ   & \targ     &\rstick{\ket{j\oplus x_0 \oplus x_2 \oplus x_3}.}\qw \\
\]

From this example, we can generalize the implementation to an arbitrary $s=s_0\cdots s_{n-1}$. Just consider

\[
\]

where CNOT$_{ij}$ is controlled by qubit $i$ and the target is qubit $j$, and  $\left(\text{CNOT}_{ij}\right)^{s_k}$ is the identity operator if $s_k=0$, and the standard $\text{CNOT}_{ij}$ if $s_k=1$.
Note that the order of the CNOT gates is irrelevant. There is a CNOT for each bit 1 of $s$.

Let us finish the circuit of the Bernstein-Vazirani algorithm for our example. The whole circuit is

\[
\Qcircuit @C=1.3em @R=0.3em {
\lstick{\ket{0}}& \gate{H} & \ctrl{4}&\qw     & \qw      & \gate{H} & \meter  & \rstick{1} \cw \\
\lstick{\ket{0}}& \gate{H} & \qw     &\qw     & \qw      & \gate{H} & \meter  & \rstick{0} \cw \\
\lstick{\ket{0}}& \gate{H} & \qw     &\ctrl{2}& \qw      & \gate{H} & \meter  & \rstick{1} \cw \\
\lstick{\ket{0}}& \gate{H} & \qw     &\qw     & \ctrl{1} & \gate{H} & \meter  & \rstick{1} \cw \\
\lstick{\ket{1}}& \gate{H} & \targ   &\targ   & \targ    & \gate{H} &\rstick{\ket{1},}\qw \\
\]

which is equivalent to

\[
\Qcircuit @C=1.3em @R=0.3em {
\lstick{\ket{0}}& \gate{H} & \ctrl{4}& \gate{H} &\qw&\qw &\qw &\qw &\qw  & \qw      & \meter  & \rstick{1} \cw \\
\lstick{\ket{0}}& \qw & \qw  &\qw   &\qw  &\qw   & \qw   &\qw  &\qw & \qw & \meter  & \rstick{0} \cw \\
\lstick{\ket{0}}& \qw    &\qw &\qw& \gate{H} &\ctrl{2}& \gate{H} & \qw  &\qw  &\qw  & \meter  & \rstick{1} \cw \\
\lstick{\ket{0}}& \qw  &\qw   &\qw &\qw &\qw &\qw  & \gate{H} & \ctrl{1} & \gate{H} & \meter  & \rstick{1} \cw \\
\lstick{\ket{1}}& \gate{H} & \targ &\gate{H} &\gate{H}  &\targ &\gate{H} &\gate{H}  & \targ    & \gate{H} &\rstick{\ket{1},}\qw \\
\]

because $H^2=I$. Using that $(H\otimes H)\cdot \text{CNOT}_{ij}\cdot (H\otimes H) = \text{CNOT}_{ji}$, the last circuit simplifies to

\[
\Qcircuit @C=1.9em @R=0.5em {
\lstick{\ket{0}}  & \targ    &\qw      & \qw       & \meter  & \rstick{1} \cw \\
\lstick{\ket{0}}  & \qw      &\qw      & \qw       & \meter  & \rstick{0} \cw \\
\lstick{\ket{0}}  & \qw      &\targ    & \qw       & \meter  & \rstick{1} \cw \\
\lstick{\ket{0}}  & \qw      &\qw      & \targ     & \meter  & \rstick{1} \cw \\
& \\
\lstick{\ket{1}}  & \ctrl{-5}&\ctrl{-3}&\ctrl{-2}  &\rstick{\ket{1}.}  \qw \\
\]

Using this example, we can easily derive the generic case, which can always be expressed as CNOTs controlled by the last qubit and with targets being the qubits corresponding to the bits of $s$ that are equal to 1. This simplification helps to understand that the Bernstein-Vazirani algorithm has no entanglement because $U_f$ is multiplied by $H^{\otimes (n+1)}$, which neither creates nor destroys entanglement. The depiction of $U_f$ in the circuit of the algorithm gives us the impression that $U_f$ creates entanglement, which is misleading.

§ ECONOMICAL CIRCUIT OF THE BERNSTEIN-VAZIRANI ALGORITHM

The Bernstein-Vazirani algorithm can be implemented with $n$ qubits instead of $n+1$. Indeed, we have learned that $U_f$ is a product of CNOT's

\[
\]

where CNOT$_{ij}$ is controlled by qubit $i$ and the target is qubit $j$, and  $\left(\text{CNOT}_{ij}\right)^{s_k}$ is the identity if $s_k=0$, and $\text{CNOT}_{ij}$ if $s_k=1$.  In the algorithm, just before the action of $U_f$, the state of the $n$-th qubit is $\ket{-}$. The circuit that describes the action of $\text{CNOT}_{0n}$ is

\[
\Qcircuit @C=2.0em @R=1.6em {
\lstick{\ket{x_0}}       &\ctrl{1} \qw&   \rstick{(-1)^{x_0}\ket{x_0}} \qw \\
\lstick{\ket{-}}         & \targ  \qw  & \rstick{\ket{-},} \qw
\]

where we have depicted only the first and the last qubits and we have placed $(-1)^{x_0}$ in the first qubit because this is mathematically allowed. This circuit is equivalent to

\[
\Qcircuit @C=2.0em @R=1.6em {
\lstick{\ket{x_0}}       &\gate{Z} \qw&   \rstick{(-1)^{x_0}\ket{x_0}.} \qw
\]

We can convert all CNOT's  of $U_f$ into $Z$'s and then

\[
U'_f \,=\, Z^{s_0}\otimes\cdots\otimes  Z^{s_{n-1}}.
\]

If a bit $s_i$ of $s$ is 0, $Z^{s_i}=I$. Then

\[
U'_f\ket{x}\,=\, (-1)^{s\cdot x}\ket{x}.
\]

Function $f$ is the same as before. What changes is the way we implement $f$ as a unitary operator.

The circuit of the economical version of the  Bernstein-Vazirani algorithm is

\[
\Qcircuit @C=2.3em @R=0.9em {
\lstick{\ket{0}}        & \gate{H} & \multigate{3}{\,\,\,U'_f\,\,\,} & \gate{H} & \meter  & \rstick{s_0} \cw \\
\lstick{\vdots \,\,\,}  & {\vdots} &                                &{\vdots}&{\vdots} & \rstick{\vdots}  \\
\lstick{}               &          &                                &&         & \rstick{}  \\
\lstick{\ket{0}}        & \gate{H} & \ghost{\,\,\,U'_f\,\,\,}        & \gate{H}& \meter  & \rstick{s_{n-1}.}  \cw\\
\]

As before, this circuit simplifies to

\[
H^{\otimes n}U'_fH^{\otimes n} \,=\, X^{s_0}\otimes\cdots\otimes  X^{s_{n-1}}
\]

because $HZH=X$. Now, it is straightforward to check that there is no entanglement in the Bernstein-Vazirani algorithm. $U'_f$ is not a genuine $n$-qubit gate, but instead is the tensor product of $n$ 1-qubit gates. The depiction of the circuit is misleading.

§.§ Consulting the oracle

In the non-economical circuit, if the input to the first register of $U_f$ is $\ket{x}$, $U_f$ returns $f(x)=(-1)^{s\cdot x}$ when we perform a measurement of the last qubit. In the economical circuit, we obtain $f(x)$ using the circuit

\[
\Qcircuit @C=2.0em @R=1.6em {