Quantum Computing

In this section of my website, I have briefly presented the basic concepts of quantum computing and the underlying principles of  the future quantum computers operation. A detailed description of quantum computing can be found in my master’s thesis (sorry, in Polish only), “On The Evolutionary Design of Quantum Algorithms”, and some of my recent publications. The initial chapters of my master’s thesis are monograph of this area.

Quantum computing[11] is located in the intersection of two fields, computer science and quantum mechanics, and it concerns the use of unique quantum mechanical systems properties to solving computational problems. For some time, it became clear that there is a class of computational problems that can be solved much more efficiently by utilizing the computational capabilities of subatomic computational systems. By applying the unique effects of quantum mechanics (such as the interference of wave functions, quantum parallelism, superposition of states, quantum entanglement and coherence), certain computational problems could be solved extremely efficiently, more effeciently than it would be ever possible with any classical computing machine. Examples of such tasks include factorization of numbers[15] and searching an unsorted collection[7]. In addition to algorithmic problems, the unique quantum mechanics phenomena can be applied in information theory (quantum teleportation protocol[1,2,3], superdense coding[11]), which has a huge impact on cryptography and cryptoanalysis. Also, quantum computing principles can be applied in game theory and artificial intelligence[5,6,17]. According to some hypotheses (especially, due to Penrose[12,13] and Hameroff[8,9]), quantum effects may be necessary to explain the non-algorithmic mysteries of the human mind, human consciousness, imagination and intelligence. On the other hand, Artificial Intelligence provides methods for semi-automatic design of quantum algorithms[5,6], which by their nature are non-intuitive and difficult to handle for the human mind. Consequently, quantum computing and artificial intelligence mutually inspire and enrich each other.

The basic units of information in quantum computing are qubits and quantum registers. Qubit is a normalized vector in the two-dimensional, complex Hilbert state space of two-level quantum system. The coordinates of the vector define the probability of observing the qubit base states. Therefore, the qubit |\Phi\rangle holds the superposition of two basic states (|0\rangle and |1\rangle, simultaneously:

|\Phi\rangle = \alpha |0\rangle + \beta |1\rangle

where \alpha, \beta \in \mathbb{C} and |\alpha|^2 + |\beta|^2 = 1. The complex numbers \alpha and \beta are probability amplitudes, and the probability of observing the base states |0\rangle and |1\rangle are |\alpha|^2 and |\beta|^2, respectively. The vectors |0\rangle and |1\rangle form the canonical basis of the two-dimensional, complex space of possible qubit states. Using Dirac notation, the qubit state can be also rewritten as a column vector |\Phi\rangle = \left[\alpha\atop\beta\right]. In Figure 1 (on the left), the geometric illustration of a qubit state has been presented.

Fig. 1. Geometric illustration of Qubit and Quantum Register

A system of many interconnected qubits constitutes a quantum register, which — according to one of the quantum mechanics postulates — can be considered as an isolated system composed of many components (i.e. qubits belonging to the register). The state space of quantum register is the tensor product of the individual qubits state spaces. Therefore, the state of n-qubit quantum register |\Psi\rangle is represented as a normalized vector in 2n-dimensional complex Hilbert space. Consequently, this allows to encode a superposition of 2n different base states |0\rangle \ldots |2^n-1\rangle:

|\Psi\rangle = \sum_{i=0}^{2^n-1} \omega_i|i\rangle

where \omega_i \in \mathbb{C} is the probability amplitude of observing the quantum register base state |i\rangle. The probability of observing the base state |i\rangle is |\omega_i |^2, and obviously |\omega_0|^2 + |\omega_1|^2 + \ldots + | \omega_ {2^n-1} |^2 = 1. The geometric illustration of a quantum register consisting of three qubits has been presented in Figure 1 (on the right). One of the unique properties of quantum computing is that with a linear increase in the number of qubits in a register, the dimension of quantum register state space grows exponentially.

Quantum logic gates and quantum circuits

One of the formal models of quantum computing, which allows to describe and simulate any quantum computation, is quantum circuits model consisting of quantum logic gates. Equivalent, but usually far less useful, theoretical device of quantum computation capabilities is Quantum Turing Machine. Quantum logic gate, acting on a quantum register of n qubits, is a mapping of 2n-dimensional complex Hilbert space into the same 2n-dimensional space given by a 2^n \times 2^n unitary matrix of complex elements. The basic quantum gates set includes: Not gate, Controlled-Not gate (CNot), phase shift gate, Hadamard gate (H) and identity gate. The matrices of the gates are as follows:

In Figure 2, examples of two quantum circuits have been presented.

Fig 2. Examples of quantum circuits

In an object-oriented programming language (such as Python or Java), the fundamental notions of quantum computing (qubits, quantum registers and gates and others) and their relations can be illustrated by a UML class diagram. I have proposed an object model for quantum computing, and the UML class diagram of the model has been presented in Figure 3. It allows simulating quantum algorithms (i.e. creating virtual quantum computers), and I have implemented this object model in my qclib library for Python.

Quantum Computer UML Class Diagram

Fig 3. Quantum Computer simulator UML Class Diagram

Quantum algorithms

Only few quantum algorithms which have practical application have been found so far. The most important of them have been listed below:

  1. Grover’s algorithm[7] — allows searching an unsorted collection with the computational complexity O(\sqrt{N}), while any classical algorithm for this trivial problem requires the complexity O(N).
  2. Shor’s algorithm[15] — provides a factorization of numbers with the less-than-exponential computational complexity, namely O(log^3 N). So far, there hasn’t been discovered any classical algorithm of such complexity, and it is believed that no such algorithm exists. Efficient factorization of big numbers is highly significant for cryptoanalysis. Possibility to factorize big numbers easily would have a serious impact on the security of many contemporary cryptosystems.
  3. Quantum teleportation protocol[3] — allows sending an exact state of qubit, represented as two complex numbers, in only two bits of classical information and quantum communication channel (i.e. spatially separated pair of entangled qubits). The teleportation protocol exploits unique properties of entangled quantum states in EPR configuration[4] (see also Einstein-Podolsky-Rosen paradox).
  4. Superdense coding[11] — allows sending two classical bits in the single unit of quantum information (qubit). Therefore, it is a complementary operation to quantum teleporation protocol.

For several reasons, designing a quantum algorithm is a difficult task. There is a very poor analogy to classical algorithms, due to the use of non-intuitive phenomena of quantum mechanics, such as the superposition of states, the interference of probability amplitudes, quantum entanglement and parallelism. Quantum algorithms are probabilistic algorithms, which means that they are based on the probability and its evolution in time. Instead of basic complexity classes, like P, NP, BPP, quantum algorithms have an additional set of complexities, EQP, BQP, and NQP. Fortunately, elements of quantum algorithms can be designed semi-automatically with modern artificial intelligence techniques. For example, unitary matrices representing quantum logic gates can be optimized efficiently with evolutionary algorithms[5,6], and complete quantum circuits can be designed automatically with genetic programming techniques[14,17].

Towards a real quantum computer…

Fig. 4. Nuclear Magnetic Resonance spectroscopy

Building a real, functional and scalable quantum computer is still far from being achieved. Although, there are multiple promising approaches, giving hope to accomplish this objective in the future. Major difficulties appear after exceeding some, currently small, number of qubits in quantum registers. Building a quantum computer requires a physical system which allows to keep a very “fragile” state of quantum coherence. Physical phenomena offering such property include: nuclear magnetic resonance (NMR)[10,16], electron energy in atomic orbitals, the polarization of light, quantum dots, ion traps, Bose-Einstein condensate, and many other phenomena. Especially, much research effort has been already devoted to the use of nuclear magnetic resonance. In Figure 4, NMR spectrometer and a molecule consisting of atoms having an internal magnetic moment (magnetic spin), have been presented. The magnetic spins of the particles can be considered as the base vectors of quantum register state space. The spins, corresponding to states of seven qubits, can be set with an external electromagnetic field. Observation of such quantum register state is achieved through examination of the spectrum with the NMR spectrometer.

Despite the difficulties in building a functional quantum computer, quantum computing is still an ongoing challenge and a valuable source of inspiration for modern computer science. Morover, the operation  of quantum computer can be simulated, but such simulations are very inefficient due to their exponential computational complexity and memory consumption. The simulations can be performed in numerical computation environments, such as Matlab or Python with Numerical Python library. In my master’s thesis, I have created a quantum computer simulator in Python. I have created qclib (quantum computing library), and I have implemented simulations of several quantum algorithms.

All these issues presented briefly above have been exhaustively described in my master’s thesis, “On The Evolutionary Design of Quantum Algorithms” (in Polish), and I invite all the interested persons to read more in my thesis.

References

  1. C. Bennett, G. Brassard, C. Crepeau, R. Jozsa, A. Peres, and W. Wootters. Teleporting an unknown quantum state via dual classical and EPR channels. Phys Rev Lett, pages 1895-1899, 1993.
  2. D. Bouwmeester, J. Pan, K. Mattle, M. Daniell, M. Eibl, H. Weinfurter, and Anton Zeilinger. Experimental quantum teleportation. Nature, 390:575-579, 1997.
  3. Gilles Brassard. Teleportation as a quantum computation, May 1996.
  4. A. Einstein, B. Podolsky, and N. Rosen. Can quantum mechanical description of physical reality be considered complete? Phys. Rev., 47(10):777-780, May 1935.
  5. J. Faber, R.N. Thess, and G. Giraldi. Learning linear operators by genetic algorithms, 2003.
  6. Gilson A. Giraldi, Renato Portugal, and Ricardo N. Thess. Genetic algorithms and quantum computation, Mar 2004.
  7. Lov K. Grover. A fast quantum mechanical algorithm for database search. In STOC ’96: Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 212-219, New York, NY, USA, 1996. ACM Press.
  8. Stuart Hameroff, Consciousness, neurobiology and quantum mechanics, In: The Emerging Physics of Consciousness, (Ed.) Tuszynski, J. 2006
  9. Stuart Hameroff with Conrad Schneiker, Ultimate Computing: Biomolecular Consciousness and Nanotechnology, Elsevier-North Holland, 1987.
  10. M.A. Nielsen, E. Knill, and R. Laflamme. Complete quantum teleportation using nuclear magnetic resonance. NATURE: Nature, 396, 1998.
  11. Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000.
  12. Roger Penrose, Shadows of the Mind. Oxford University Press, 1994
  13. Roger Penrose, The emperor’s new mind. Oxford, 1989.
  14. Ben I. P. Rubinstein. Evolving quantum circuits using genetic programming. In John R. Koza, editor, Genetic Algorithms and Genetic Programming at Stanford 2000, pages 325-334. Stanford Bookstore, Stanford, California, 94305-3079 USA, 2000.
  15. Peter W. Shor. Algorithms for quantum computation: Discrete log and factoring. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science, pages 124-134. Institute of Electrical and Electronic Engineers Computer Society Press, 1994.
  16. Lieven M.K. Vandersypen, Costantino S. Yannoni, and Isaac L. Chuang. Liquid state nmr quantum computing, 2000.
  17. Taro Yabuki and Hitoshi Iba. Genetic algorithms for quantum circuit design – evolving a simpler teleportation circuit. In Darrell Whitley, editor, Late Breaking Papers at the 2000 Genetic and Evolutionary Computation Conference, pages 425-430, Las Vegas, Nevada, USA, 8 2000.