Quantum Information and Computing for Beginners: Basics of Qubit Transformations and Quantum Algorithms

Archit Dhingra

doi:10.2478/qic-2025-0040

Full Article

1.

Introduction

1.1.

Basics of Quantum Information

Quantum information is the information of the state of a quantum system. Here, a state refers to a physical state of the system. State is a set of variables describing a system, without any reference to its history. Simply put, a quantum state refers to any element |ψ〉 ∈ H of Hilbert space. Technically, a quantum state provides a probability distribution for the value of each observable (a measurable physical quantity). Therefore, knowledge of the quantum state, along with the interpretation, and applications of rules for the system’s evolution in time can help us predict the system’s behavior.

The fundamental concept of classical information (or computation) is a bit. Likewise, the fundamental concept of quantum information is a quantum bit, or qubit (for short). The difference between the classical bit and the qubit, is that the former one has two possibilities (or possible states); namely: 0 or 1. However, the latter one can have any state: either |0〉 or |1〉 or any linear combination of those two states. This linear combination is written mathematically as 1 $| ψ 〉 = α | 0 〉 + β | 1 〉$ |\psi \rangle = \alpha |0\rangle + \beta |1\rangle

The special states, |0〉 and |1〉, in equation 1 are known as the computational basis states and the linear combination is called the superposition (of the aforementioned basis states). Also, the numbers in Equation (1), α and β, are complex numbers [1]. The state of a qubit, |ψ〉, given by Equation (1) can be represented as a vector on the Bloch sphere (Figure 1). Bloch sphere (named after Felix Bloch [2]) is, hence, a geometrical representation of the pure state (a vector in Hilbert space) space of a qubit.

Another difference between the classical bit and the qubit lies in the fact that one can always examine whether the former is in the state 0 or 1, whereas examining a qubit to determine its quantum state cannot be achieved. However, quantum physics dictates that measuring a qubit will result in 0, with probability |α|², or it will result in 1, with probability |β|². And, of course, the normalization condition for equation 1 indicates 2 $| α |^{2} + | β |^{2} = 1$ |\alpha {|^2} + |\beta {|^2} = 1

On a more fundamental level, measuring classical information is carried out using Shannon entropy [3] whereas measurement of its quantum counterpart involves application of Von Neumann entropy [4,5]. This difference arises because, of course, classical information follows the classical statistical mechanics while quantum information follows the quantum statistical mechanics model.

Shannon entropy is mathematically described as [6] 3 $S = - \sum_{i} P_{i} \log P_{i}$ S = - \sum\limits_i {{P_i}} \log {P_i} here, P_i is the probability mass function.

And, Von Neumann entropy is represented as [7] 4 $S = - Tr (ρ \ln ρ)$ S = - {\mathop{\rm Tr}\nolimits} (\rho \ln \rho ) here, ρ is the density matrix of the statistical ensemble of quantum mechanical systems.

1.2.

Quantum Computation

Quantum computation comprises of the techniques and algorithms involved in manipulation (processing) of quantum information. However, there are some theorems that invoke some limitations on the way quantum information (or qubits) can be manipulated [1]. These theorems are:

No-teleportation theorem: states that a qubit cannot be converted into classical bits, which implies that cannot be read [8,9].
No-cloning theorem: states that an arbitrary bit cannot be copied [8,10].
No-deleting theorem: states that an arbitrary bit cannot be deleted [11].
No-broadcasting theorem: states that even though a qubit is allowed to be transported from one place to another, it cannot be delivered to multiple recipients (simultaneously) [12].

Abiding by the limitations invoked by the above-mentioned theorems, we can manipulate quantum information by performing quantum Fourier transform (QFT) [13]. Here it is worth mentioning that the prospective reader is only expected to understand that QFT is a linear transformation on qubits and is analogous to, its classical counterpart, inverse discrete Fourier transform (IDFT). As far as the message of this tutorial is concerned, understanding of the proper mathematical formalism of QFT is not as crucial as it is to know its function, i.e.,: implementing QFT to qubits is how one gets basic quantum circuits operating on qubits – called quantum logic gates – to perform manipulation of information.

1.2.1.

Single-Qubit Transformations

Hadamard gate, Pauli-X gate, Pauli-Y gate, Pauli-Z gate, Square root of NOT gate, Phase shift gate, etc. are some of the examples of single-qubit gates which can be used to perform transformations. The two single-qubit transformations (or gates) that deserve special attention, as far as this paper is concerned, are the Hadamard transformation (H) and the phase shifter transformation (Φ).

Hadamard transformation (H) [1,14]: represented as H gate (see Figure 2), is a single-qubit rotation that maps the basis states |0〉 and |1〉 to two superposition states with equal weights.

In Dirac notation, H is represented as 5 $H = \frac{| 0 〉 + | 1 〉}{\sqrt{2}} 〈 0 | + \frac{| 0 〉 - | 1 〉}{\sqrt{2}} 〈 1 |$ H = {{|0\rangle + |1\rangle } \over {\sqrt 2 }}\langle 0| + {{|0\rangle - |1\rangle } \over {\sqrt 2 }}\langle 1|

Above equation for H (Equation (5)) gives us the transformation matrix H′ (i.e., just the 2 × 2 matrix operator without the computational basis states |0〉 and |1〉) corresponding to the Hadamard gate H (which performs the single-qubit Hadamard transformation on the computational basis states |0〉 and |1〉) as [15] 6 $H^{'} = \frac{1}{\sqrt{2}} [\begin{matrix} 1 & 1 \\ 1 & - 1 \end{matrix}]$ {H^\prime } = {1 \over {\sqrt 2 }}\left[ {\matrix{ 1 & 1 \cr 1 & { - 1} \cr } } \right]

Coefficients of 〈0| and 〈1| in Equation (5), together, form the polar basis in the realm of quantum computation. Coefficient of 〈0|, $\frac{| 0 〉 + | 1 〉}{\sqrt{2}}$ {{|0\rangle + |1\rangle } \over {\sqrt 2 }}, is represented as |+〉 whereas the coefficient of 〈1:, $\frac{| 0 〉 - | 1 〉}{\sqrt{2}}$ {{|0\rangle - |1\rangle } \over {\sqrt 2 }}, is represented as |–〉.

Phase shifter transformation (Φ) [14]: represented by Φ gate (see Figure 3), is a single-qubit transformation that modifies the phase of the qubit but not the probability of measuring its basis states (|0〉 and |1〉).

In Dirac notation, Φ can be represented as 7 $Φ = | 0 〉〈 0 | + e^{i ϕ} | 1 〉〈 1 |$ {\rm{\Phi }} = |0\rangle \langle 0| + {{\rm{e}}^{{\rm{i}}\phi }}|1\rangle \langle 1|

While its corresponding transformation matrix Φ′ is given as 8 $Φ^{'} = [\begin{matrix} 1 & 0 \\ 0 & e^{i ϕ} \end{matrix}]$ {\Phi ^\prime } = \left[ {\matrix{ 1 & 0 \cr 0 & {{{\rm{e}}^{{\rm{i}}\phi }}} \cr } } \right]

From above Equations (7) and (8), it is easy to see how Φ gate only shifts the phase of |1〉 state by ϕ as it is changed to e^iϕ|1〉. However, |0〉 is left unaltered.

Applications of, both, the H gate and the Φ gate can be seen when their corresponding transformations are applied to the problem at hand.

Problem:

Assume that the input state is a general qubit 9 $| Q 〉 = α | 0 〉 + β | 1 〉$ |{\cal Q}\rangle = \alpha |0\rangle + \beta |1\rangle

Find the state of the output qubit after the transformation HΦH.

Solution:

There are two ways to solve the given problem: either by using Dirac notation (Equations (5) and (7)) for the H gate and the Φ gate or by using the transformation matrices (Equations (6) and (8)) corresponding to the respective gates.

HΦH applied to Equation (9), gives 10 $H (Φ (H | Q 〉)) = H (Φ (H (α | 0 〉 + β | 1 〉)))$ H(\Phi (H|{\cal Q}\rangle )) = H(\Phi (H(\alpha |0\rangle + \beta |1\rangle )))

Now by using Equations (5) and (9) and the fact that basis states are orthonormal (i.e., 〈i|j〉 = δ_ij, where i, j ϵ {0, 1}), we get 11 $\begin{array}{l} H | Q 〉 & = & (\frac{| 0 〉 + | 1 〉}{\sqrt{2}} 〈 0 | + \frac{| 0 〉 - | 1 〉}{\sqrt{2}} 〈 1 |) (α | 0 〉 + β | 1 〉) \\ \Rightarrow & H | Q 〉 = \frac{| 0 〉 + | 1 〉}{\sqrt{2}} α + \frac{| 0 〉 - | 1 〉}{\sqrt{2}} β \end{array}$ \matrix{ {H|{\cal Q}\rangle } \hfill & = \hfill & {\left( {{{|0\rangle + |1\rangle } \over {\sqrt 2 }}\langle 0| + {{|0\rangle - |1\rangle } \over {\sqrt 2 }}\langle 1|} \right)(\alpha |0\rangle + \beta |1\rangle )} \hfill \cr {} \hfill & \Rightarrow \hfill & {H|{\cal Q}\rangle = {{|0\rangle + |1\rangle } \over {\sqrt 2 }}\alpha + {{|0\rangle - |1\rangle } \over {\sqrt 2 }}\beta } \hfill \cr }

Now, by using Equations (7) and (11), we get 12 $\begin{array}{l} Φ (H | Q 〉) & = & (| 0 〉〈 0 | + e^{i ϕ} | 1 〉〈 1 |) (\frac{| 0 〉 + | 1 〉}{\sqrt{2}} α + \frac{| 0 〉 - | 1 〉}{\sqrt{2}} β) \\ \Rightarrow & Φ (H | Q 〉) = \frac{(α + β)}{\sqrt{2}} | 0 〉 + \frac{(α - β) e^{i ϕ}}{\sqrt{2}} | 1 〉 \end{array}$ \matrix{ {\Phi (H|{\cal Q}\rangle )} \hfill & = \hfill & {\left( {|0\rangle \langle 0| + {{\rm{e}}^{{\rm{i}}\phi }}|1\rangle \langle 1|} \right)\left( {{{|0\rangle + |1\rangle } \over {\sqrt 2 }}\alpha + {{|0\rangle - |1\rangle } \over {\sqrt 2 }}\beta } \right)} \hfill \cr {} \hfill & \Rightarrow \hfill & {\Phi (H|{\cal Q}\rangle ) = {{(\alpha + \beta )} \over {\sqrt 2 }}|0\rangle + {{(\alpha - \beta ){{\rm{e}}^{{\rm{i}}\phi }}} \over {\sqrt 2 }}|1\rangle } \hfill \cr }

Finally, by using equations (5) and (12), we get 13 $\begin{array}{l} H (Φ (H | Q 〉)) & = & (\frac{| 0 〉 + | 1 〉}{\sqrt{2}} 〈 0 | + \frac{| 0 〉 - | 1 〉}{\sqrt{2}} 〈 1 |) (\frac{(α + β)}{\sqrt{2}} | 0 〉 + \frac{(α - β) e^{i ϕ}}{\sqrt{2}} | 1 〉) \\ \Rightarrow H (Φ (H | Q 〉)) = (\frac{(α + β)}{2} + \frac{(α - β) e^{i ϕ}}{2}) | 0 〉 + (\frac{(α + β)}{2} - \frac{(α - β) e^{i ϕ}}{2}) | 1 〉 \end{array}$ \matrix{ {H(\Phi (H|{\cal Q}\rangle ))} \hfill & = \hfill & {\left( {{{|0\rangle + |1\rangle } \over {\sqrt 2 }}\langle 0| + {{|0\rangle - |1\rangle } \over {\sqrt 2 }}\langle 1|} \right)\left( {{{(\alpha + \beta )} \over {\sqrt 2 }}|0\rangle + {{(\alpha - \beta ){{\rm{e}}^{{\rm{i}}\phi }}} \over {\sqrt 2 }}|1\rangle } \right)} \hfill \cr {} \hfill & {} \hfill & { \Rightarrow H(\Phi (H|{\cal Q}\rangle )) = \left( {{{(\alpha + \beta )} \over 2} + {{(\alpha - \beta ){{\rm{e}}^{{\rm{i}}\phi }}} \over 2}} \right)|0\rangle + \left( {{{(\alpha + \beta )} \over 2} - {{(\alpha - \beta ){{\rm{e}}^{{\rm{i}}\phi }}} \over 2}} \right)|1\rangle } \hfill \cr }

Equation (13) is, therefore, the solution to our problem.

1.2.2.

Two-Qubit Gates and Entangled States

Building up on our knowledge about the fundamentals and functionality of single-qubit transformations/gates, we can now proceed to multiple qubit gates. The scope of this article, however, is limited to two-qubit gates.

Swap (SWAP) gate, Square root of Swap gate $(\sqrt{S W A P})$ (\sqrt {SWAP} ), Controlled (CNOT) gate, etc. are some examples of two-qubit gates with CNOT being the most important among them all [16,17].

SWAP gate: it swaps two qubits. Its matrix (with respect to the basis |00〉, |01〉, |10〉, |11〉) is represented as: $S W A P = [\begin{array}{l} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{array}]$ SWAP = \left[ {\matrix{ 1 \hfill & 0 \hfill & 0 \hfill & 0 \hfill \cr 0 \hfill & 0 \hfill & 1 \hfill & 0 \hfill \cr 0 \hfill & 1 \hfill & 0 \hfill & 0 \hfill \cr 0 \hfill & 0 \hfill & 0 \hfill & 1 \hfill \cr } } \right]

$\sqrt{S W A P}$ \sqrt {SWAP} gate: it performs a “half-way” two-qubit swap, and its matrix can be represented as: $\sqrt{S W A P} = [\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & \frac{1}{2} (1 + i) & \frac{1}{2} (1 - i) & 0 \\ 0 & \frac{1}{2} (1 - i) & \frac{1}{2} (1 + i) & 0 \\ 0 & 0 & 0 & 1 \end{matrix}]$ \sqrt {SWAP} = \left[ {\matrix{ 1 & 0 & 0 & 0 \cr 0 & {{1 \over 2}(1 + i)} & {{1 \over 2}(1 - i)} & 0 \cr 0 & {{1 \over 2}(1 - i)} & {{1 \over 2}(1 + i)} & 0 \cr 0 & 0 & 0 & 1 \cr } } \right]

Here, the Dirac notation of the SWAP and $\sqrt{SWAP}$ \sqrt {{\rm{ SWAP }}} is not shown, but rather left as a trivial exercise for the readers (hint: since the transformation matrix for these gates are given in Figure 4 and Figure 5, and the basis vectors are provided as |00〉, |01〉, |10〉, |11〉, their corresponding Dirac notations can be derived by working along the lines of what is shown in Equations (7) and (8).

CNOT gate: has two input qubits with one of them acting as the “control” qubit, while the other qubit is the “target” qubit. If the control qubit is |0〉, then the target qubit is unchanged. But, if the control qubit is |1〉 then the target is flipped [1,16,17]. Its operation can be summarized as, 14 $| A, B 〉 \to | A, B \oplus A 〉$ |{\rm{A}},{\rm{B}}\rangle \to |{\rm{A}},{\rm{B}} \oplus {\rm{A}}\rangle

What makes controlled-NOT gate the most important amongst all the multiple qubit gates (some pertinent examples are represented in the left panel of Figure 6) is the universality result, which states: Any multiple qubit logic gate may be composed from CNOT(right panel of Figure 6) and single qubit gates [1].

Application of these gates lies in the production (or creation) of Bell (or entangled¹) states [18]–[21], which are defined as B1 $| Φ^{+} 〉 = \frac{1}{\sqrt{2}} (| 0 〉_{A} \otimes | 0 〉_{B} + | 1 〉_{A} \otimes | 1 〉_{B})$ \left| {{\Phi ^ + }} \right\rangle = {1 \over {\sqrt 2 }}\left( {|0{\rangle _A} \otimes |0{\rangle _B} + |1{\rangle _A} \otimes |1{\rangle _B}} \right) B2 $| Φ^{-} 〉 = \frac{1}{\sqrt{2}} (| 0 〉_{A} \otimes | 0 〉_{B} - | 1 〉_{A} \otimes | 1 〉_{B})$ \left| {{\Phi ^ - }} \right\rangle = {1 \over {\sqrt 2 }}\left( {|0{\rangle _A} \otimes |0{\rangle _B} - |1{\rangle _A} \otimes |1{\rangle _B}} \right) B3 $| Ψ^{+} 〉 = \frac{1}{\sqrt{2}} (| 0 〉_{A} \otimes | 1 〉_{B} + | 1 〉_{A} \otimes | 0 〉_{B})$ \left| {{\Psi ^ + }} \right\rangle = {1 \over {\sqrt 2 }}\left( {|0{\rangle _A} \otimes |1{\rangle _B} + |1{\rangle _A} \otimes |0{\rangle _B}} \right) B4 $| Ψ^{-} 〉 = \frac{1}{\sqrt{2}} (| 0 〉_{A} \otimes | 1 〉_{B} - | 1 〉_{A} \otimes | 0 〉_{B})$ \left| {{\Psi ^ - }} \right\rangle = {1 \over {\sqrt 2 }}\left( {|0{\rangle _A} \otimes |1{\rangle _B} - |1{\rangle _A} \otimes |0{\rangle _B}} \right)

There are numerous ways in which quantum circuits can be used to create the entangled Bell states (states described by Equations (B1)–(B4)), and using the combination of a Hadamard gate and a controlled-NOT gate is one of them. The mechanism of this combinational circuit can be understood with the following example:

The combinational quantum circuit (Figure 7) takes |00〉 as the two-qubit input and produces the first Bell state (Equation (B1)) as the output. Manifestly, H gate acts on |00〉 and gives |+〉|0〉² as its output. H gate’s output will now act as the control qubit (input) for the CNOT gate, which will invert the target qubit when the control qubit is |1〉. Therefore, the resultant qubit will be the first Bell state (|Φ⁺〉). In a similar fashion, one can produce the remaining Bell states as well. The aforementioned production of Bell states (given by Equations (B1)–(B4)) can be, mathematically, summarized as 15 $| B (x, y) 〉 = \frac{1}{\sqrt{2}} (| 0, y 〉 + {(- 1)}^{x} | 1, Y 〉)$ |{\rm{B}}(x,y)\rangle = {1 \over {\sqrt 2 }}\left( {|0,y\rangle + {{( - 1)}^x}|1,Y\rangle } \right)

Here, |B(x, y)〉 stands for Bell states and Υ is the negation of y, where x, y ϵ {0, 1}.

1.2.3.

Quantum Algorithms

A quantum algorithm is a finite sequence of well-defined instructions for solving a problem by using quantum circuits for computation [22]. Quantum algorithms are based on two phenomena of quantum computation: quantum interference and quantum entanglement [23]. Quantum algorithms can be categorized under three classes. The first is: the class of quantum algorithms bases on quantum Fourier transform. This class includes, Deutsch-Jozsa algorithm [24] (its simpler case being Deutsch’s algorithm [25]), Bernstein-Vazirani algorithm [26], Simon’s algorithm, and Shor’s algorithms for discrete logarithms and factoring [27], to name a few. Second class consists of quantum search algorithms whose basic principles are given by Grover’s algorithm [28]. And, third class of quantum algorithms comprises of quantum simulation by a quantum computer to simulate a quantum system.

This paper talks about Deutsch–Jozsa algorithm (member of the first class of quantum algorithms) in detail while slight description of Grover’s algorithm (an example of second class of quantum algorithms) is also included.³

1.2.4.

Deutsch–Jozsa problem statement and algorithm

Problem statement: We are given a black box quantum computer that implements some function f : {0, 1}ⁿ → {0, 1}. That is to say, the function takes n-digit binary values as input and gives either 0 or 1 as the output for each value. Moreover, we are promised that f(x) is either constant (0 on all outputs or 1 on all outputs) for all values of values of x or balanced (equal to 1 on exactly half of the domain and 0 for the other half of the domain). Now, the problem reduces to determining if f is constant or balanced by using the oracle.

2.

Algorithm

This algorithm combines quantum parallelism and interference to solve the aforementioned problem.

Here, let’s digress for a bit to briefly describe what quantum parallelism truly is. It is a fundamental feature of many quantum algorithms [1], as it allows quantum computers to evaluate a function f (x) for several different values of x simultaneously. Its working can be understood by considering a function that has one-qubit domain and range, like the one considered in Deutsch’s algorithm⁴ (presented on page 12, with a sample circuit representation in Figure 9).

Now, coming back to Deutsch–Jozsa algorithm:⁵ The steps of this algorithm are shown in Figure 8. The input state is given as D1 $| ψ_{0} 〉 = | 0 〉^{\otimes n} | 1 〉$ \left| {{\psi _0}} \right\rangle = |0{\rangle ^{ \otimes n}}|1\rangle here the query register describes the state of n qubits prepared in state |0〉, whereas |1〉 is the answer register. Here, as a general note, it is worth mentioning that, regardless of the algorithm, both query and answer registers are equally important and, therefore, must be read at all times. Hadamard transform (a generalized 2ⁿ × 2ⁿ matrix applied to an n-qubit register) is applied to the query register, while Hadamard gate (which performs the single-qubit Hadamard transformation on the computational basis states |0〉 and |1〉) is applied to the answer register to produce D2 $| ψ_{1} 〉 = \sum_{x \in {0, 1}^{n}} \frac{| x 〉}{\sqrt{2^{n}}} [\frac{| 0 〉 - | 1 〉}{\sqrt{2}}]$ \left| {{\psi _1}} \right\rangle = \sum\limits_{x \in {{\{ 0,1\} }^n}} {{{|x\rangle } \over {\sqrt {{2^n}} }}} \left[ {{{|0\rangle - |1\rangle } \over {\sqrt 2 }}} \right]

Equation (D2) leaves us with query register in a superposition of all values, while the answer register is now an evenly weighted superposition of 0 and 1. Now, the function f is evaluated using U_f : |x, y〉→|x, y ⊗ f(x)〉, resulting in D3 $| ψ_{2} 〉 = \sum_{x} \frac{{(- 1)}^{f (x)} | x 〉}{\sqrt{2^{n}}} [\frac{| 0 〉 - | 1 〉}{\sqrt{2}}]$ \left| {{\psi _2}} \right\rangle = \sum\limits_x {{{{{( - 1)}^{f(x)}}|x\rangle } \over {\sqrt {{2^n}} }}} \left[ {{{|0\rangle - |1\rangle } \over {\sqrt 2 }}} \right]

We now have a set of qubits in which the result of U_f is stored in the amplitude of the qubit superposition state. Now, we have to interfere terms in the superposition using Hadamard transformation on the query register. We should, first, calculate H|x〉. By checking for x = 0 and x = 1, we see that for a single qubit D4 $H | x 〉 = \sum_{z} {(- 1)}^{x z} | z 〉 / \sqrt{2}$ H|x\rangle = \sum\limits_z {{{( - 1)}^{xz}}} |z\rangle /\sqrt 2

Therefore, we have D5 $H^{\otimes n} | x_{1}, \dots, x_{n} 〉 = \sum_{z_{1}, z_{2}, z_{3}, \dots, z_{n}} {(- 1)}^{x_{1} z_{1} + \dots + x_{n} z_{n}} | z_{1}, \dots, z_{n} 〉 / \sqrt{2^{n}}$ {H^{ \otimes n}}\left| {{x_1}, \ldots ,{x_n}} \right\rangle = \sum\limits_{{z_1},{z_2},{z_3}, \ldots ,{z_n}} {{{( - 1)}^{{x_1}{z_1} + \ldots + {x_n}{z_n}}}} \left| {{z_1}, \ldots ,{z_n}} \right\rangle /\sqrt {{2^n}}

Equation (D5) can be rewritten as D6 $H^{\otimes n} | x 〉 = \sum_{z} {(- 1)}^{x \cdot z} | z 〉 / \sqrt{2^{n}}$ {H^{ \otimes n}}|x\rangle = \sum\limits_z {{{( - 1)}^{x\cdotz}}} |z\rangle /\sqrt {{2^n}} here, x · z is bitwise inner product of x and z, modulo 2, which is (explicitly) written as D7 $x \cdot z = x_{1} z_{1} \oplus x_{2} z_{2} \oplus x_{3} z_{3} \oplus \dots \oplus x_{n} z_{n}$ x\;\cdot\;z = {x_1}{z_1} \oplus {x_2}{z_2} \oplus {x_3}{z_3} \oplus \cdots \oplus {x_n}{z_n}

Now, |ψ₃〉 can be calculated using (D2) and (D6) and is given as D8 $| ψ_{3} 〉 = \sum_{z} \sum_{x} \frac{{(- 1)}^{x \cdot z + f (x)} | z 〉}{2^{n}} [\frac{| 0 〉 - | 1 〉}{\sqrt{2}}]$ \left| {{\psi _3}} \right\rangle = \sum\limits_z {\sum\limits_x {{{{{( - 1)}^{x\cdotz + f(x)}}|z\rangle } \over {{2^n}}}} } \left[ {{{|0\rangle - |1\rangle } \over {\sqrt 2 }}} \right]

We can now observe the query register and realize that there are two possible cases – f is constant, and f is balanced – to see what happens. For the former case, the amplitude for |0〉^⊗n is +1 or –1, depending on the constant value that f(x) bears. Given the fact that |ψ₃〉 is of unit length, it’s trivial to conclude that all other amplitudes must be zero, and a measurement will lead 0s for all qubits in the query register. Now, for the latter case (where f is balanced) the negative and positive contributions to the amplitude for |0〉^⊗n cancel each other thus leaving a zero amplitude. This would imply that a measurement should give a result different from 0 on at least one of the qubits in the query register. In other words: if measurements result in all 0s then f is constant, and balanced otherwise.

2.1.

Deutsch’s algorithm

It combines quantum parallelism and interference, just like Deutsch – Jozsa does, and is actually a simpler case of (more general) Deutsch – Jozsa algorithm. The input state for Deutsch algorithm is given as D1′ $| ψ_{0} 〉 = | 01 〉$ \left| {{\psi _0}} \right\rangle = |01\rangle which, on passing through two H gates, gives D2′ $| ψ_{1} 〉 = [\frac{| 0 〉 + | 1 〉}{\sqrt{2}}] [\frac{| 0 〉 - | 1 〉}{\sqrt{2}}]$ \left| {{\psi _1}} \right\rangle = \left[ {{{|0\rangle + |1\rangle } \over {\sqrt 2 }}} \right]\left[ {{{|0\rangle - |1\rangle } \over {\sqrt 2 }}} \right]

Now, applying U_f to a state $| x 〉 [\frac{| 0 〉 - | 1 〉}{\sqrt{2}}]$ |x\rangle \left[ {{{|0\rangle - |1\rangle } \over {\sqrt 2 }}} \right] gives us the state $(- 1)^{f (x)} | x 〉 [\frac{| 0 〉 - | 1 〉}{\sqrt{2}}]$ {( - 1)^{f(x)}}|x\rangle \left[ {{{|0\rangle - |1\rangle } \over {\sqrt 2 }}} \right]. Therefore, U_f|ψ₁〉 gives us D3′a $| ψ_{2} 〉 = \pm [\frac{| 0 〉 + | 1 〉}{\sqrt{2}}] [\frac{| 0 〉 - | 1 〉}{\sqrt{2}}] if f (0) = f (1)$ \left| {{\psi _2}} \right\rangle = \pm \left[ {{{|0\rangle + |1\rangle } \over {\sqrt 2 }}} \right]\left[ {{{|0\rangle - |1\rangle } \over {\sqrt 2 }}} \right]\quad {\rm{ if }}f(0) = f(1) D3′b $| ψ_{2} 〉 = \pm [\frac{| 0 〉 - | 1 〉}{\sqrt{2}}] [\frac{| 0 〉 - | 1 〉}{\sqrt{2}}] if f (0) \neq f (1)$ \left| {{\psi _2}} \right\rangle = \pm \left[ {{{|0\rangle - |1\rangle } \over {\sqrt 2 }}} \right]\left[ {{{|0\rangle - |1\rangle } \over {\sqrt 2 }}} \right]\quad {\rm{ if }}f(0) \ne f(1)

Now, finally applying H gate on |ψ₂〉, we get D4′a $| ψ_{3} 〉 = \pm | 0 〉 [\frac{| 0 〉 - | 1 〉}{\sqrt{2}}] if f (0) = f (1)$ \left| {{\psi _3}} \right\rangle = \pm |0\rangle \left[ {{{|p\rangle - |1\rangle } \over {\sqrt 2 }}} \right]\quad {\rm{ if }}f(0) = f(1) D4′b $| ψ_{3} 〉 = \pm | 1 〉 [\frac{| 0 〉 - | 1 〉}{\sqrt{2}}] if f (0) \neq f (1)$ \left| {{\psi _3}} \right\rangle = \pm |1\rangle \left[ {{{|0\rangle - |1\rangle } \over {\sqrt 2 }}} \right]\quad {\rm{ if }}f(0) \ne f(1)

Equations (D4′a) and (D4′b) can be combined and written as D5 $| ψ_{3} 〉 = \pm | f (0) \oplus f (1) 〉 [\frac{| 0 〉 - | 1 〉}{\sqrt{2}}]$ \left| {{\psi _3}} \right\rangle = \pm |f(0) \oplus f(1)\rangle \left[ {{{|0\rangle - |1\rangle } \over {\sqrt 2 }}} \right]

Therefore, by measuring the first qubit, we can determine the global property of f(x), i.e., f(0) ⊕ f(1), by using a single evaluation of f(x). This is quite interesting because its classical counterpart would require at least two evaluations. Thus, making it faster than its classical counterpart.

Now, let’s have a transformation, U_f, acting on a state |x, y〉 such that it takes |x, y〉 → |x, y ⊕ f(x)〉. Here, the first register is called the data register while the second register is called the target register. If we have y = 0, then it is trivially concluded that the final state of the second qubit will be given by the value of the function f(x). Applying U_f to a superposition state $| x 〉 = \frac{| 0 〉 + | 1 〉}{\sqrt{2}}$ |x\rangle = {{|0\rangle + |1\rangle } \over {\sqrt 2 }}, while keeping |y〉 = |0〉, we get 16 $U_{f} | x, 0 〉 = | ψ 〉 = \frac{| 0, f (0) 〉 + | 1, f (1) 〉}{\sqrt{2}}$ {U_f}|x,0\rangle = |\psi \rangle = {{|0,f(0)\rangle + |1,f(1)\rangle } \over {\sqrt 2 }}

Here, $| x 〉 = \frac{| 0 〉 + | 1 〉}{\sqrt{2}}$ |x\rangle = {{|0\rangle + |1\rangle } \over {\sqrt 2 }} can be produced by applying H gate to |0〉. Figure 9 (below) summarizes the discussion about quantum parallelism.

2.2.

Deutsch’s Algorithm V/s Classical Algorithm

Comparison between Deutsch’s algorithm with a classical algorithm from the standpoint of number of steps involved can be carried out as follows:

Deutsch–Jozsa (or Deutsch’s) algorithm for n qubits: Recalling that for f to be balanced we must have at least one of the measurements resulting in a non-zero value. Otherwise, f will be constant. Moreover, x · z = x₁z₁ ⊕ x₂z₂ ⊕ x₃z₃ ⊕ ⋯ ⊕ x_nz_n (Equation (D7)) denotes that there will be at least n steps involved in solving the problem using this algorithm as one needs to evaluate all x_iz_i for i ∈ {1,2,3,4,…, n}. That is to say, Deutsch’s algorithm requires O(n) steps to determine f.

Classical algorithm: Exhaustive search is the fastest known classical algorithm [29] we have at our disposal for comparing the efficiency of classical algorithms with Deutsch’s algorithm. Following exhaustive search algorithm, one will have to carry out (at most) ‘2^n–1 + 1’ measurements to determine the nature of f. This is because for every bit we’ll have two possibilities, thus there are 2ⁿ possibilities for n bits. Now, the worst-case scenario would be that the first half of the measurements (i.e., 2^n–1 measurements) are all the same, which means result of the following ((2^n–1 + 1)^th) measurement will be mandatory to determine nature of f. Therefore, even the most efficient classical algorithm requires O(2ⁿ) steps to achieve the same task as performed by Deutsch’s algorithm.

2.3.

Grover’s Algorithm

It is a quantum search algorithm that solves the problem of finding an element satisfying a known property in a search size of N, with no prior knowledge about the structure of information in the given search space. Classical solution to this problem would require O(N) steps, whereas Grover’s algorithm requires $O (\sqrt{N})$ O(\sqrt N ) steps [1].

3.

Conclusions

Quantum information and quantum computing are based on the concept and manipulation of qubits, as opposed to classical bits. QFT based quantum circuits (quantum logic gates) are used to manipulate quantum information. An input state $| Q 〉 = α | 0 〉 + β | 1 〉$ |{\cal Q}\rangle = \alpha |0\rangle + \beta |1\rangle going through a Hadamard-Phase shifter-Hadamard transformation (HΦH) is examined, and the result of $H Φ H | Q 〉$ H\Phi H|{\cal Q}\rangle is given by equation 13. Two-qubit gates can be used (along with single qubit gates) for production of Bell (entangled) states. For example, in this paper, a combination of C-NOT gate and H gate is used to produce all four Bell states (described by Equations (B1)–(B4)).

Moreover, a direct comparison between Deutsch–Jozsa (or Deutsch’s) algorithm and the fastest available classical algorithm (exhaustive search algorithm) concludes that the former is way more efficient in comparison with the latter one. Quantitatively speaking, (for n-qubits) Deutsch’s algorithm requires O(n) steps whereas, on the other hand, any classical algorithm requires O(2ⁿ) steps (for n-bits) to perform the same task.

Finally, I would like to add that while there is a myriad of existing literature on the topics contained herein, what makes this tutorial stand out is its concise-yet-comprehensive nature in comparison with other great pieces of work in this field [30–33]. In other words, this tutorial is ideal for the readers who would like to take the first step towards understanding the marvels of quantum physics, applied to quantum information and computing, but do not have enough hours in a day to dedicate to the cause.

Quantum Information and Computing for Beginners: Basics of Qubit Transformations and Quantum Algorithms

Full Article

Paradigm

My account