The Qubit: introduction to quantum algorithms

27 Dec 2021

Introduction

In popular science contexts, the quantum computer is sometimes labeled as a particular computer that is “incredibly faster.” Although this characterization is not entirely detached from reality, some clarifications are necessary.

A quantum computer is structurally distinct from a classical computer, to such an extent that the logic governing its internal processes departs from conventional logic, as it can only be described through the laws of quantum mechanics.

In order to highlight the innovative aspects introduced by the quantum computational model, it is necessary to recall the classical model of computation, namely the method by which modern computers process information.

Data encoding is performed through sequences of bits. A single bit represents the basic unit of classical information and is described by two possible states, 0 and 1; therefore, any data processed by a computer are represented as a binary string (a sequence of 0s and 1s).

The most significant distinction lies precisely in the different unit of information adopted by a quantum processor: the classical concept of the bit is superseded and generalized by that of the quantum bit, or qubit.

The quantum states describing a qubit are not limited to the values 0 and 1, as is the case for a classical bit, but can assume infinitely many intermediate configurations, giving rise to the phenomenon known in quantum mechanics as superposition.

By exploiting this phenomenon, the scientific community has devised algorithms through which a quantum computer is able to compute a given result in a number of steps that is much smaller than that required by classical counterparts.

With the support of mathematical formalism, the following sections will provide a technical treatment of the qubit and of quantum computing. Finally, an example of quantum speed-up (i.e., a reduction in computational cost) with respect to the classical approach for solving a particular problem will be presented.

Definition of a Qubit

The quantum states 0 and 1 are denoted by the symbols^[1] $|0\rangle$ and $|1\rangle$ . A generic qubit is given by a linear combination of these two symbols

$|\psi\rangle:=\alpha|0\rangle + \beta|1\rangle\text{ con }\alpha,\beta\in\mathbb{C},$

Qubits are often represented as points on the so-called Bloch sphere.

Measurement or Observation

The term observation is particularly important in this context. In physics, an observable is defined as any quantity that can be measured directly by appropriate techniques; therefore, in what follows, observation and measurement will be treated as synonyms.

This concept is crucial in distinguishing between classical and quantum mechanics. In classical mechanics, measurement has no effect on the system, as it describes something pre-existing without altering it. For example, consider a runner whose speed is measured: it is evident that the act of measurement does not affect the observable (the speed, in this case) at any moment in time.

In quantum mechanics, by contrast, observing a superposition of quantum states causes the system to collapse irreversibly into a specific state. As a consequence, the original quantum state in its entirety becomes an entity inaccessible to any measuring instrument.

Indeed, in quantum computing, given a qubit $|\psi\rangle$ , it is not possible to determine exactly the values $\alpha$ and $\beta$ that define it. In general, the only feasible approach is to reproduce $|\psi\rangle$ multiple times, perform measurements, and estimate the probabilities based on the observed frequencies of 0 and 1 as outcomes.

In summary, the quantum circuit receives the qubit $|\psi\rangle$ as input

and returns, irreversibly transforming the qubit,

$\begin{aligned}|0\rangle\text{ con probabilità } |\alpha|^2, \\ |1\rangle \text{ con probabilità } |\beta|^2.\end{aligned}$

Quantum Gates

Before proceeding with the description of the transformations characterizing quantum circuits, we formally introduce the concatenation of multiple qubits. Let $|\psi_1\rangle$ = $\alpha_1|0\rangle+\beta_1|1\rangle$ and $|\psi_2\rangle$ = $\alpha_2|0\rangle+\beta_2|1\rangle$ be two qubits; their concatenation

is a 2-qubit system, and note that the coefficients of the symbols $|00\rangle,|01\rangle,|10\rangle,|11\rangle$ can still be interpreted as probabilities, since

$|\alpha_1\alpha_2|^2+|\alpha_1\beta_2|^2+|\beta_1\alpha_2|^2+|\beta_1\beta_2|^2=1.$

The same reasoning extends to an $n$ -qubit system, where $n$ is any positive integer.

The operations (quantum gates) through which qubits can be manipulated are largely extensions of the logical gates used in classical computation, with the constraint that the transformation of a qubit must preserve the relation among its coefficients (such transformations are called unitary).

Formally, a transformation acting on a $1$ -qubit

$T: \alpha|0\rangle+\beta|1\rangle \longmapsto \alpha'|0\rangle+\beta'|1\rangle,$

must satisfy $|\alpha'|^2+|\beta'|^2=1$ . Analogously, this relation is preserved in the case of $n$ -qubit systems.

Below we list the most common gates used in the construction of quantum circuits. Their action is shown on $|0\rangle$ , $|1\rangle$ in the $1$ -qubit case, and on $|00\rangle,\dots,|11\rangle$ in the $2$ -qubit case; this action extends by linearity to generic qubit states.

The gate $X$ or $\bigoplus$ describes the NOT operation on $1$ -qubit systems.

The gate $\bullet\!\!-\!\!\!\bigoplus$ describes the CNOT operation and acts on the state of a $2$ -qubit system as a NOT on the second input if and only if the value of the first is $1$ .

The gate $\times\!\!\!\!-\!\!\!-\!\!\! \times$ describes the SWAP operation and acts by exchanging the state of a $2$ -qubit system.

Note that the quantum gates described above correspond to operations that admit an equivalent construction in the classical case. The differences between the classical and quantum computational models become evident with quantum gates that, by construction, cannot have a classical counterpart.

For example, the Hadamard gate $H$ is used to generate (uniform) superposition. Indeed, when applied to $|0\rangle$ or $|1\rangle$ , it produces a qubit that can assume both values with equal probability.

The gate $R_{\theta}$ acts exclusively on the coefficient of $|1\rangle$ .

It is worth noting that the set of gates presented is sufficient to describe any quantum gate acting on a generic $n$ -qubit system. A set of gates with this property is called universal.

Finally, given a function $f:\{0,1\}^n\rightarrow\{0,1\}^m$ , the gate $U_f$ is defined for its evaluation,

where in this case the operation $\oplus$ denotes the usual XOR.

Deutsch–Jozsa Algorithm

We now provide an example that offers an initial intuition into the potential of quantum computation by exhibiting a speed-up with respect to the classical model. Consider the functions

$\begin{aligned}b_1:\{0,1\} & \longrightarrow\{0,1\} & c_1:\{0,1\} & \longrightarrow\{0,1\} \\0&\longmapsto 0&0&\longmapsto 0\\1&\longmapsto 1&1 &\longmapsto 0\\[5pt] b_2:\{0,1\} & \longrightarrow\{0,1\} &c_2:\{0,1\} &\longrightarrow\{0,1\} \\0 &\longmapsto 1 & 0 &\longmapsto 1\\ 1 & \longmapsto 0 & 1& \longmapsto 1\end{aligned}$

$b_1$ , $b_2$ are said to be balanced, since over all possible inputs they return as many 0s as 1s; formally, $|b_i^{-1}(0)|=|b_i^{-1}(1)|$ . Conversely, $c_1$ and $c_2$ are said to be constant, since they return the same output independently of the input.

Consider the following problem: let $f$ be a function known only to belong to the set $\{b_1,b_2,c_1,c_2\}$ . Is $f$ balanced or constant?

In the classical computational model, given an oracle $O_f$ for evaluating $f$ , the problem is solved by applying the oracle to half of all possible inputs plus $1$ . This corresponds to $2$ evaluations in the $1$ -dimensional case and to $2^{n-1}+1$ evaluations in the $n$ -dimensional case.

The quantum Deutsch–Jozsa algorithm solves the problem by means of the following circuit, combining the quantum gates $U_f$ and $H$ introduced previously.

Using this algorithm, the solution requires a single execution of $U_f$ in the $1$ -dimensional case, and the same result extends straightforwardly to the $n$ -dimensional case. Therefore, $1$ application of $U_f$ versus $2^{n-1}+1$ calls to $O_f$ (in the $n$ -dimensional case) demonstrates an exponential speed-up compared to the classical approach.

The proof follows.

1. The gate $H$ applied to both qubits acts as follows.

$|01\rangle\longmapsto\frac{1}{2}\sum_{x\in \{0,1\}}|x\rangle\left(|0\rangle-|1\rangle\right)$

2. As anticipated, the gate $U_f$ corresponds to the evaluation of $f$ .

$\begin{aligned} \frac{1}{2}\sum_{x\in \{0,1\}}|x\rangle\left(|0\rangle-|1\rangle\right)\longmapsto & \frac{1}{2}\sum_{x\in \{0,1\}}|x\rangle\left(|f(x)\rangle-|1\oplus f(x)\rangle\right) \\ & = \frac{1}{2}\sum_{x\in \{0,1\}}(-1)^{f(x)}|x\rangle(|0\rangle-|1\rangle) \end{aligned}$

3. The gate $H$ applied to both qubits computes

$\frac{1}{2}\sum_{x\in \{0,1\}}(-1)^{f(x)}|x\rangle(|0\rangle-|1\rangle) \longmapsto \frac{1}{2}\sum_{x,y\in\{0,1\}}(-1)^{f(x)+\langle x,y \rangle}|y\rangle|1\rangle.$

4. Measuring the first qubit returns $y\in\{0,1\}$ with probability

$\frac{1}{2^{2}}\left|\sum_{x\in\{0,1\}}(-1)^{f(x)+\langle x,y \rangle}\right|^2.$

In the case where $f$ is constant, one obtains $y=0$ with probability

$\frac{1}{2^{2}}\left|\sum_{x\in\{0,1\}}(-1)^{f(x)+\langle x,y \rangle}\right|^2=\frac{1}{2^{2}}\left|\sum_{x\in\{0,1\}}(-1)^{\text{const}+0}\right|^2=1,$

whereas in the case where $f$ is balanced, the probability of obtaining $y=1$ is

$\frac{1}{2^{2}}\left|\sum_{x\in\{0,1\}}(-1)^{f(x)+\langle x,y \rangle}\right|^2=\frac{1}{2^{2}}\left|\sum_{x\in\{0,1\}}(-1)^{f(x)+x}\right|^2=1.$

Consequently, the outcome of the measurement of the first qubit discriminates the nature of the function $f$ : if it is constant, the result is certainly $0$ , whereas if it is balanced, the certain outcome is $1$ . An entirely analogous discussion applies in the $n$ -dimensional case, that is, for $f:\{0,1\}^n\to\{0,1\}$ , still requiring only a single application of the gate $U_f$ .

Sources:

^[1] From a mathematical point of view, these symbols represent vectors in the Hilbert space $\mathbb{C}^2$ . This theoretical background is beyond the scope of the present article.
^[2] Entity that allows the evaluation of the function $f$ without knowing it explicitly

This article is part of a series of contributions by the Telsy Cryptography Research Group dedicated to quantum computing and its implications for cryptography. For other articles, please refer to the index of the section.

For other articles related to quantum and cryptography, please refer to the relevant categories in the blog.

The authors

Veronica Cristiano, a bachelor’s degree in Mathematics from the University of Pisa and a master’s degree in Mathematics with a specialization in Cryptography at the University of Trento, joined the Telsy Cryptography research group in mid-2021.

Francesco Stocco, a master’s degree in Mathematics at the University of Padua and the Université de Bordeaux attending the course of study “Algebra Geometry And Number Theory” (ALGANT), joined the Telsy research group in Cryptography at end of 2020 focusing in particular on issues related to quantum technologies.