Martin Lukac, Associate Professor from School of Engineering and Digital Sciences, Nazarbayev University, discusses the fundamentals of quantum computing
Quantum computing harnesses the power of atomic and subatomic particles to perform high speed parallel computing. Conceptually introduced by Feynman in the eighties as a method for solving instances of the many-body problem [1], it was not until recently that quantum computing became widely known to the public.
When compared to other technologies designed to tackle heat dissipation and Moore’s limit of the current transistor-based computers such as DNA computing, 3D transistor or carbon nanotube, quantum computing boasts several advantages over its counterparts which can be described by the basic postulates defining the possibilities of quantum computing.
The first regards information representation. Classical information in digital computers is represented by logical binary digits (bits). A logical bit can take the value of 1 or 0 depending on whether the voltage in the wire is High or Low in a logic circuit.
In contrast, a quantum bit (a qubit) represents the information by a quantum state described by a wave equation such as |ф›= α|0›+ β|1›with α = cos(θ) and β = eiфsin(θ) being complex numbers subject to|α|2 + |β|2 = 1 which can be represented on a Bloch sphere.
The |0 = [10] and |0 = [10] represents the basis ›› states (as column vectors) corresponding roughly to logic 0 and logic 1 respectively. Therefore, the quantum state |ф›represents either a logical state such as |ф› = |0›when α = 1 or a superposition of its basis states such as |ф›= _1 |0 + _1 |1.
The superposition indicates that the quantum states contain, at the same time, both basis states |0›and |1›. The second postulate expands the idea of quantum states: when multiple qubits are used together, the space of their states expands exponentially. This means that a set of qubits can represent in the superposition all the combinations of the basis states. For instance, two qubits |ψ›and |ф› = y|0›+ δ|1›can represent all four possible states as follows |ψф› = αy|00› + αδ|01› + βy|10› + βδ|11›.
The third postulate specifies that qubits and their states are manipulated using a set of unitary matrix operators: square matrices that are self-inverse. These matrix operators turn the qubit state along the three axes of the Bloch sphere.
The final postulate indicates that quantum information exists until it is not observed. This means that a quantum state can contain both basis states at the same time, but when one wants to read the quantum state, the result will be either |0›or |1›determined in a probabilistic manner according to the |α|2 and |β|2 .
The specific advantage of quantum computing was demonstrated by a David Deutsch algorithm (followed by the Deutsch-Jozsa algorithm [2]) that showed an exponential acceleration of computing. The Deutsch- Jozsa algorithm demonstrated that quantum computers can answer in a single computational step the question of whether a given function is balanced or constant. A balanced function has half of its outputs 0(1) and a constant function has all outputs 0(1).
To answer such a question in classical computing, one would require examining at least half of the outputs of a given function. If more than half of the outputs are the same, the function is constant; if not, it is balanced.
Developments in the 1990s further popularised quantum computing. Peter Shor’s algorithm for exponentially accelerating integer factorisation, Lov Grover’s quadratically accelerating search in an unordered database [2], and recently the achievement of quantum supremacy [3], made quantum computing very attractive to the wider research and investor community.
While Shor’s algorithm is one of the main motivations behind the large government funding of quantum computing (think exponentially accelerating decryption of current encryption standards), Grover’s algorithm’s wider application spurred a large number of search acceleration optimisation. Finally, the demonstration of quantum supremacy showed that it is practically possible to construct quantum computers that perform much faster than any classical computer.
“Quantum computing has the potential to solve many of the current big data problems by accelerating the processing and storing it on an even denser space. Quantum supercomputers will be the first ones to appear within the next 10 years.”
The difficulty of quantum computers to break into the mainstream is twofold. Firstly, quantum computing computes in the quantum space. This implies that classical inputs have to be prepared (made quantum before processing) and quantum outputs of the computation have to be measured to be made classical and, therefore, available for further processing. The measurement, in addition, severely limits the amount of information that can be extracted from the quantum states which, in turn, limits the possible acceleration of computing using quantum computers.
Secondly, quantum states require an almost perfect vacuum, near-absolute zero temperature, and they do not like to remain in the desired quantum state due to decoherence which means qubits interacting with the environment lose information. These issues are being incrementally solved by progress in material science and by improving control protocols of quantum operations.
While quantum computing is advancing at a relatively slow pace, there is light at the end of the tunnel. Near- future applications can already be seen in the form of quantum security, quantum communication, quantum cryptography and large-scale quantum computation. Quantum computing has the potential to solve many of the current big data problems by accelerating the processing and storing it on an even denser space. Quantum supercomputers will be the first ones to appear within the next 10 years.
References
(1)Richard P. Feynman. Simulating physics with computers. International Journal of Theoretical Physics, 21(6):467–488, Jun 1982.
(2) Nielsen, Michael A., and Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. 10 ed., Cambridge University Press, 2011.
(3)Philip Ball. Physicists in China challenge Google’s ‘quantum advantage’. Nature, 588(7838):380–380, December 2020.
