Basics of Quantum Computing

Martin Lukac, Associate Professor from Nazarbayev University School of Engineering and Digital Sciences

 

A quantum computer is a device that performs quantum computations, harnessing the power of atomic and subatomic particles to perform high speed parallel computing.

Conceptually introduced by Richard Feynman in the 1980s as a method for solving instances of the many-body problem, it was not until recently that quantum computing became widely known to the public. The many-body problem is a general name for a large category of physical problems represented by systems of microscopic interacting particles.

Martin Lukac

When compared to other technology candidates designed to tackle the heat dissipation and the Moore’s limit of the current transistor-based computers, such as DNA computing, 3D transistor or carbon nano-tube, quantum computing has several advantages not available to these “more classical” technologies.

These advantages can be described by four basic postulates defining the principles and possibilities of quantum computing.

The first postulate 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 of a logic circuit is High or Low; think of the classic binary coding of 1s and 0s. In contrast, a quantum bit (qubit) is represented by a quantum state described by a wave equation:   with  and  being complex numbers subject to . The quantum state specified by this wave equation is a point on the surface of something called a Bloch sphere.

The second postulate expands on 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.

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 of a qubit can contain both of the basis states   or  at the same time but when one wants to read the quantum state, the result will be either  or .

The advantages of quantum computing were first demonstrated by David Deutsch’s algorithm, followed by the Deutsch-Jozsa algorithm, which 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). For a classical computer to determine the answer to this question, it would need to examine 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.

Further developments in the nineties, and leading up to today, popularized quantum computing further. Peter Shor’s algorithm for exponentially accelerating integer factorization, Lov Grover’s quadratically accelerating search in un-ordered database, and recently the demonstration of quantum supremacy has made quantum computing very attractive for wider research and the investor community.

While Shor’s algorithm is one of the main motivations behind large governmental funding to quantum computing (think exponentially accelerating decryption of current encryption standards), Grover’s algorithm’s wider application spurred a large number of search acceleration optimization. Finally, the demonstration of quantum supremacy showed that it is indeed possible to construct quantum computers that perform much faster than any classical computer.

There are two main reasons behind the difficulty for quantum computers to break into the mainstream. 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. This 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 gradually solved by progress in material science and by improving control protocols of quantum operations.

Near-future applications are already visible 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 even a denser space. Quantum supercomputers will be the first to appear within the next 10 years.

 

spot_img

Explore more