Mac OS lover, Docker fan, Go explorer, Python geek, Trello addicted.
What is the quantum theory? As said by quantumexperience official site by IBM, it’s an elegant mathematical theory able to explain the counterintuitive behavior of subatomic particles, most notably the phenomenon of entanglement. In the late twentieth century it was discovered that quantum theory applies not only to atoms and molecules, but to bits and logic operations in a computer. This realization has been bringing about a revolution in the science and technology of information processing: I decided to write some notes to better explain, from a physics-agnostic computer scientist’s point of view XD, what I understood - and it is certainly wrong - about Q until now and why I think it’s an amazing field for computer science. More on this story in my previous post.
So - back to the origins - why am I writing this post? Because I recently came over my quantum notes again and YES, I’M CONTINUING THEM (clap clap clap), even if, unfortunately, I don’t have a lot of time to dedicate to it - you know, the always-valid excuse of life I don’t have time. This post is about a specific algorithm - one of the basic reasoning to be done about quantum parallelism (more on this in a few lines): I’m gonna talk about the Deutsch Algorithm, the reason behind it, how it works and I will literally vomit what I collected (a sort of preview XD) in the last crazy Sunday of study as a mathematical demonstration of its component.
But… before going into details, let’s make some reasoning over classical computation first.
Unfortunately, the first three sections are needed to go throught the demonstration of the Deutsch algorithm. At least, I tried to give a little bit of context to better understand the reasons behind the algorithm. Let’s start this journey and sorry if it will take some time :/
EASTER EGG: And for the very first time, there’s an easter egg (kind of - at least) in the blog post!
A fundamental difference between classical and quantum circuits is that theclassical logic gates could be irreversible (for example
NAND), while the quantum logic gates are always unitary and therefore reversible. On the other hand, it would be desirable for an alternative computation model to beable to express at least all computations that can be expressed with the classical model. So the first objective to talk about quantum computation is therefore to represent the classical computationsas unitary transformations, i.e. as quantum computations.
Since unitary transformations are invertible (i.e. reversible), the first step is to transform any irreversible classical computation into a reversible one. In order to operate in a reversible way it is necessary that the function to be evaluated is a bjection (i.e. injective and surjective). In this case we can in fact unequivocally trace from each output to the value of the input that generated it, that is, operate in reverse. Any irreversible computation can be transformed into an equivalent reversible computation, making the corresponding function to be biunivocally evaluated.
For example, given any function
it is possible to construct
such that is biunivocal and calculates by acting on the input , where denotes bits initialized with value 0. Each biunivocal function:
can be actually seen as a permutation on the bits in input or, equivalently, on integers . Accordingly, it describes a classical reversible computation. Take a moment to reflect on this - mentalist trick n°1.
Any irreversible classical computation can be transformed into an equivalent but reversible computation using the Toffoli gate. This is a classic reversible operation, represented by the circuit shown below, which operates on three input bits: two are control bits and the third is the target bit that is exchanged if the control bits are both 1, as show in the truth table.
The reversibility of this operation is easily verified by observing that by applying the Toffoli gate twice in a row the same starting result is obtained (two value are ported as they are, the third one is a
XOR that is reversible by design thus is verified):
So the operation itself coincides with its inverse. It is equally easy to verify that the Toffoli gate represents the permutation on integers (exchanges the two sequences and ).
Toffoli’s gate is universal for the classic reversible computations, that is, every classical computation can be built in a reversible way through the Toffoli gate. This result follows from the universality of the operations of
FANOUT (the operation of copying a classic bit) for the classical computations and from the fact that both these operations can be expressed through the Toffoli circuit. In fact, by applying the operation with , we obtain , and , i.e. we obtained the simulation of
NAND and it is also a reversible operation because Toffoli port is. The reversible
FANOUT is instead obtained as shown in the picture above: by applying the Toffoli gate with and the result is the copy of bit (remember that this copy operation is not possible for a qubit!!!).
FANOUT the construction of a reversible circuit for any classical operation by means of the Toffoli port involves the use of some service bits in input (or ancilla bits) and in output (or garbage). After deleting these service bits, the resulting circuit performs the transformation:
(where is the input of and is the register intended to contain the output) and can be considered as the standard reversible circuit for the evaluation of .
As already observed, a classical reversible computation corresponds to a permutation on the sequences of the input bits. This guarantees the possibility of constructing a complex unitary matrix that represents it.
In particular, the Toffoli gate can be implemented as quantum circuit. In this case the input is given by three qubits and the transformation, analogous to the classical case, consists in the exchange of the third qubit if the first two are . For example the quantum Toffoli gate applied to the state produces the state . Thus…
The quantum Toffoli port can then be used to simulate all the classical computations on a quantum computer, ensuring that a quantum computer is able to perform any computable computation on a classic computer.
Let’s go ahead by exploring how a quantum Toffoli gate can be used.
Randomized algorithms are algorithms that are executed using a random number generator (the launch of a coin) to decide one of the possible branches of execution. The first randomized algorithm was introduced by Solovay and Strassen in the 1970s to determine whether a number is prime or not. The algorithm produces a correct answer only with a certain probability. This probability can be increased by repeating the execution for an appropriate number of times.
These algorithms can also be efficiently simulated by quantum circuits. In fact, to simulate a random bit it is sufficient to prepare a qubit in the state and then apply the Hadamard port. You will get the status that measured will give or each with probability . It should also be noted that in this way a really random number is obtained, something that a classic computer can not do… (yes, this should let you think).
On a quantum computer, a function can be evaluated on different values of at the same time. This is known as quantum parallelism and is a fundamental characteristic of quantum circuits. Consider a boolean function of the form:
To calculate by means of a quantum computation the transformation must be defined as a unit transformation . As seen previously, this can be done by applying on the input state , let’s say our data register1, an appropriate sequence of quantum logic gates (which we will indicate with a black box called ) that transform into the state , called the target register. If then the final state of the second qubit will accurately contain the value of , because of the ’s (
XOR) true table.
In the circuit in shown above, the input is
This state contains information both on the value and on the value .
We just evaluated simultaneously on = 0 and .
This type of parallelism is deeply different from the classical one where multiple circuits (each of which calculates for a single value of ) are executed simultaneously.
Please take some time to reflect on this if you are not convinced before going ahead - mentalist trick n°2.
This procedure can be generalized to calculate functions on an arbitrary number of bits using a generalization of the Hadamard gate known as the Walsh-Hadamard transform. This operation consists of Hadamard ports acting in parallel on qubits. For example, for , the Walsh-Hadamard transform is indicated with and applied to two qubits prepared in the state gives as a result:
In general, the result of applied to qubits in the state is:
where is the binary representation of the numbers from to . Thus…
The Walsh-Hadamard transform produces an equiprobable overlap of all the states of the qubits computational basis.
Note: to obtain an overlap of states only logical ports are needed. We are getting closer…
The parallel evaluation of a function , with input of bits and bit as output, can therefore be performed by a circuit similar to last one shown before, with qubit in input prepared in the . Then Hadamard applies to the first qubits and then the circuit is applied. The result will be:
Quantum parallelism is not directly usable in the sense that it is not possible to obtain all the values calculated with a single measurement: the measurement of the state above will give the value of for a single value of . To exploit the hidden information in this parallelism, we have to, somehow, make better use of the information contained in the overlap.
For example, by exploiting in an appropriate manner the interference between the states in the overlap. By combining quantum parallelism with this property that comes from quantum mechanics, results like the one exemplified by the Deutsch algorithm can be obtained. And FINALLY…
The Deutsch algorithm shows how, through the parallel evaluation of a function on all its inputs, global properties of the function can be determined, such as, for example, that of being a constant or balanced function4. Using a classical algorithm, in the worst case we need to evaluate the function on at least (am I wrong?) values in order to be able to establish with certainty whether is constant or balanced.
The implementation of the Deutsch algorithm is shown in the quantum circuite above. The input of the circuit that calculates the function is now the qubits resulting from the application of Hadamard to the and states. This input is therefore:
For simplicity, let’s mantain the two initial qbits separated. Let’s apply to the state where
We already know that doesn’t change and map the quantum system (our quantum register) to .
Thus, applying to means apply to
whatever will be. The result of this application will be
where - once we measure by collapsing to value or - is
Take a moment to understand this step before going ahead.
Now, remember that because of the nature , thus the result of applied to - always by keeping away for a while - is
Since doesn’t modify we only need to evaluate - or .
Realize that by replacing the value of with we obtain exactly that is our desiderata, thus
Take some moment to convince about this step.
Now, let’s keep a part : we can rewrite
Note: if someone is able to convince me about this, please comment it below or feel free to contact me at matteo.madeddu [at] gmail.com because I didn’t find a real good explanation to this. Anyway, let’s assume it’s true because of some trick (I have a theory, that is replacing with ) over signs, and go ahead because the rest it seems ok imho.
Thus, by applying to we obtain a result that varies over two possibilities
Note that in the second alternative, we have that . Note also that can be written as
Thus applied to can be written as
or, equally, as
(because in the second case or since ) or, even, as
Now we apply Hadamard to the first qubit and we obtain which results in
At this point we observe that if , otherwise . We can therefore write the result in a more concise way
Through a measurement of the first qubit we can then determine with certainty (the probability associated with the first qubit is 1) the value of and therefore if the function is constant or balanced. To do this we had to evaluate only once.
The Deutsch algorithm can be extended to Boolean functions on bits. Let us consider a function and suppose to know that can be either constant or balanced. The quantum algorithm of Deutsch-Jozsa allows us to establish it in one step. The quantum circuit that implements this algorithm is the same Deutsch algorithm described with input of the function of qubits prepared in the state, which we will call the data register. The qubit target, intended to contain the result of , is instead prepared in the state.
To be continue…
Thank you everybody for reading!