Zero, one, quantum
Four ways to compute the square root of two: by measuring time, by measuring length, using pen and paper, and using a calculator.
Anything we can name, write down, or draw can be expressed in bits of information. Anything we do or that happens can also be represented as bits of information. Information is everywhere, and capturing and processing all its bits is a constant challenge. A computer is a device that helps us process and evaluate information. Based on input data, it provides the desired output – whether it’s calculating a square root, devising a winning strategy for a game of chess, or determining what a program actually does. The value of a computer lies in the fact that it performs these tasks faster than we can.
Algorithms
Speed depends on the method of computation – the algorithm. If we want to calculate the square root of two, we could draw a right isosceles triangle with legs of length 1 dm and measure the hypotenuse in decimeters. Or we could measure the time it takes for a stone to fall from a height of 9.81 m. Or we could start squaring numbers on paper and gradually approach the result. Or we could open a calculator on a phone, tap three times, and get the answer.
An algorithm is essentially a sequence of simpler steps that need to be carried out. At the lowest level, these are simple logical operations on bits. The complexity of an algorithm is expressed by the number of required basic operations. The larger this number, the longer the algorithm takes.
A calculator does nothing we couldn’t do ourselves – it just does it much faster. Unlike a computer, it has limited functionality and cannot directly compute any arbitrary function. A computer can be programmed, and its functionality is limited only by the number of bits it can process. Will anything change in the functionality of a computer if it becomes quantum?
Deutsch’s Problem
In 1985, David Deutsch formulated a problem we can describe as follows: imagine a box with a light bulb and a switch that can be set to position zero or one. Depending on the electronics inside the box, the bulb either lights up or stays off for each switch position. How many times do we need to use the box to determine exactly what it does? Twice. How many times do we need to use it to find out whether the switch actually controls the light? Also twice. Clearly, we need to check both switch positions.
From an information perspective, the input bit (the switch position) is transformed into an output bit (light on = 1 / light off = 0). At the level of zeros and ones, the box computes a function. There are four possible functions. The identity leaves the bit unchanged – position one turns the light on, and position zero leaves it off. Negation (the NOT operation) flips the bit. In both of these cases, the switch truly controls the light. The other two functions erase the input bit in the sense that the output is constant – the bulb is either always on or always off, regardless of the switch position.
The task is to decide, by repeatedly using the programmed function, whether it produces a constant result or not. The key question is how many times we need to evaluate the function. Classically, the answer is twice. However, Deutsch showed that if these four functions are implemented on a quantum computer, it is enough to evaluate the function just once. We do not learn how zero or one is transformed individually, but we can determine whether the function as a whole is constant or not – in other words, whether the switch…
Deutsch’s problem – does a two-position switch control a light bulb, or not?
The trick called superposition
The trick lies in the properties of quantum bits – qubits – which can take more than just the values zero or one. This is called superposition, which expresses the fact that qubit states are not numbers in the usual mathematical sense, but directions of vectors. Superposition is therefore the combination of vectors. Through this combination, every possible direction (every qubit state) can be expressed as a weighted sum (a superposition) of the directions corresponding to the logical values zero and one.
If we are guaranteed that a given qubit has one of two mutually orthogonal states, then we can determine its value. If we do not have such a guarantee about the possible states of the qubit, then its value cannot be determined with certainty. This is why the logical values zero and one correspond to mutually orthogonal vectors. By choosing these vectors, we define the so-called computational basis, and by measuring in this basis we distinguish between the logical values zero and one. Qubits in a superposition of logical states produce random outcomes when measured in the computational basis. The probabilities are related to the weighting in the vector decomposition of the computational basis.
Deutsch–Jozsa algorithm
The quantum solution to Deutsch’s problem is based on the fact that the input qubit used to test the device is in a superposition of zero and one. The output qubit is also in a superposition, but its value depends only on whether the function is constant or not. Moreover, these two different outcomes correspond to mutually orthogonal directions, which means we can distinguish them unambiguously and thereby decide whether the function is constant or not. And we only need to use the function once.
Quantum circuit for the Deutsch–Jozsa algorithm. A sequence of quantum logic gates that tests whether an unknown N-bit function is constant using only a single evaluation.
In 1992, David Deutsch and Richard Jozsa extended the original problem to N switches and one light bulb. The function is either constant or so-called balanced, meaning it is turned on for exactly half of all possible inputs. The task is to determine which type of function it is. Classically, in the worst case, one must test half of all inputs, which means applying the function 2^(N-1) times. In a quantum implementation, however, a single evaluation of the function is sufficient – a truly dramatic difference. The trick remains the same: the quantum input is a superposition of all possible inputs.
It is fair to admit that the problem itself has no direct practical application, but it demonstrates that qubits open new possibilities and surpass the computational power of classical algorithms. Why is that the case? We mentioned superposition, which is not a vague value between zero and one, but a genuine quantum state of a qubit, fully equivalent in status to zero and one. But how do we actually prepare such a superposition?
Quantum logic
Quantum computers bring quantum gates into play – logical operations on individual qubits that simply do not exist in classical computers. In other words, within an algorithm we gain access to new fundamental steps. One of these is the Hadamard gate, which transforms vectors representing logical values into their superpositions. Specifically, it turns the value zero into a sum of the zero and one states, and the value one into a difference of the zero and one states. These gates appear in almost all known quantum algorithms.
There also exists a qubit gate Q which, when applied twice in a row, results in the logical NOT operation. The relation Q² = NOT naturally implies that Q itself represents a square root of logical negation. Can you imagine such a logical operation? You are not alone. The square root of NOT transforms logical qubit inputs into superpositions which, when measured in the computational basis, yield both outcomes with equal probability. Applying Q again converts these superpositions back into logical qubit values, resulting in the standard logical operation.
Bit vs qubit
Both bits and qubits share the property that they encode at most one bit of information. Anything we can do with bits, we can do just as well with qubits, but not the other way around. It is precisely the possibility of quantum logical intermediate steps that represents the potential source of the advantage of qubits.
Quantum logic gate. The image shows a physical implementation of a photonic quantum gate, whose core is a specially prepared crystal (the cube) in the center of the image.
The number of quantum logical operations is incomparably larger than the logical operations used in today’s computers. This does not automatically guarantee usefulness – however, we know that in some cases this capability truly brings a dramatic change by turning computationally difficult problems into simple ones. If we succeed in implementing qubits and quantum gates, we will not only be able to solve certain currently hard problems, but also efficiently model the quantum world.
Author of the article: Mário Ziman, Institute of Physics, Slovak Academy of Sciences, Bratislava
Illustrations: Diana Cencer Garafová, QUTE.sk – Slovak National Center for Quantum Technologies
Image source: wikipedia public domain, Institute of Physic, Slovak Academy of Science