Quantum Computer = QUANTUM ALGORITHM + Quantum Hardware
Examples of quantum hardware
What is Quantum Computing and Its Promise?
Quantum computing employs quantum algorithms or quantum routines in hybrid algorithms to achieve computation results faster and with fewer computation steps than the conventional (classical) computers. This advantage is derived from harnessing unique properties of quantum mechanical systems, such as quantum superposition and/or entanglement.
The groundbreaking discovery of Shor’s algorithm for prime number factorization which operates exponentially faster than any known classical algorithm, holds promise that quantum computing can be much more efficient than computations performed on classical Turing machines. However, despite the large effort of the community, there are no ultimate proofs that indeed this will be the case. Thus, whether quantum computers can offer a completely new computational framework is an open question. Nevertheless, it also possible that quantum computers will offer alternative computational platforms where certain complex problems can be tackled more effectively than on traditional high-performance computing (HPC) systems.
What kind of quantum algorithms are there?
To date, three main classes of quantum algorithms have been developed. The first is Shor?s algorithm and its variants (e.g., Simon’s and Hallgren’s algorithms). These harness the Quantum Fourier Transform (QFT) to solve the period-finding problem, which allows them to e.g., factorize integers or solve number theory problems. They operate in polynomial time in contrast to the exponential number of operations required by the best-known classical algorithms. The second class is represented by Grover’s algorithm which can be applied in optimization and search problems and offers a quadratic reduction in time. The third group realizes Faymann’s idea of simulating quantum systems using quantum computers and builds on quantum walks. It includes e.g., Ambaini’s algorithm for solving the element distinctness problem in \(O(N^{2/3})\) steps, whereas classically this task requires \(O(N)\) iterations.
It is important to notice that the remarkable speedup achieved by the first class of algorithms stems from the lower computational complexity of the QFT compared to the Discrete Fourier Transform (DFT). The DFT, the foundation of e.g., digital signal processing, requires \(O(2^{2n})\) steps to process strings of \(2^n\) in length. It assumes the input to be one period of an infinite periodic signal. The DFT can be accelerated by an application of the Fast Fourier Transform (FFT) which applies a “divide and conquer” method to lower the computation time to \(O(n 2^n)\) but requires the length of the data to be an integer power of 2. In contrast, the QFT allows one to use only \(O(n \log n)\) quantum gates to process n qubits (which encode \(2^n\) amplitudes) and achieve the same result.
Recently, quantum computation found another profound application – quantum machine learning (QML). It holds promise of augmenting the machine learning process by employing quantum resources and speeding up computations. This quantum enhancement allows one to lower the number of training epochs or in some cases lower the number of training data and still achieve comparable results to classical machine learning algorithms. The use of quantum machine learning can lower training’s energy cost leaving the performance intact, which can be important in the current era of large parameters models.
What do we do?
As all quantum algorithms that bring exponential reduction in the number of computational steps rely on an efficient execution of the Quantum Fourier Transform, we recognize the importance of studying efficient implementations of other discrete mathematical transforms. In this way, using quantum resources, we hope to achieve the effect of “speed-up” w.r.t. the processing of classical sequences.
At our first attempt, we demonstrated that multi-photon quantum interference on a beam splitter examined in the photon-number basis amounts to a fractional Quantum Kravchuk Transform (QKT). Unlike the DFT, the classical Kravchuk Transform approximates the Fourier transform on finite discrete sets of arbitrary length. The great advantage of this approach is that this discrete finite transform can be employed to signals of arbitrary length, contrary to the DFT and QFT which apply only to signals of period \(2^n\). It has a whole range of applications, e.g., computer vision, but its software implementations feature prohibitive runtimes as high as \(O(n^2)\), where n is the length of input data. In contrast, the QKT has a computational complexity of \(O(1)\) and thus, can be computed in a single step regardless of the input data length. In this way, by harnessing a multi-level (qudit) information encoding, it facilitates constant-time information processing.
Quantum simulations are becoming an essential tool for studying complex phenomena, e.g., quantum topology, quantum information transfer and relativistic wave equations, beyond the limitations of analytical computations and experimental observations. In this area, we showed a quantum simulation performed using genuine higher-order Fock states, with two or more indistinguishable particles occupying the same bosonic mode. This was implemented by interfering pairs of Fock states with up to five photons on an interferometer and measuring the output states with photon-number-resolving detectors. Already this resource-efficient demonstration reveals topological matter, simulates non-linear systems, and elucidates a perfect quantum transfer mechanism which can be used to transport Majorana fermions.
Time series prediction is essential for human activities in diverse areas. A common approach to this task is to harness recurrent neural networks (RNNs). However, while their predictions are quite accurate, their learning process is complex and, thus, time and energy consuming. We proposed to extend the concept of RRNs by including continuous-variable quantum resources in it and to use a quantum-enhanced RNN to overcome these obstacles. The design of the continuous-variable quantum RNN (CV-QRNN) is rooted in the continuous-variable quantum computing paradigm. By performing extensive numerical simulations, we demonstrated that the quantum network is capable of learning-time dependence of several types of temporal data and that it converges to the optimal weights in fewer epochs than a classical network. Furthermore, for a small number of trainable parameters, it can achieve lower losses than its classical counterpart. CV-QRNN can be implemented using commercially available quantum-photonic hardware.
References
- M. Siemaszko, A. Buraczewski, B. Le Saux, M. Stobińska, Rapid training of quantum recurrent neural network, Quantum Mach. Intell. 5, 31 (2023).
- T. Sturges, T. McDermott, A. Buraczewski, W. R. Clements, J. J. Renema, S. W. Nam, T. Gerrits, A. Lita, W. S. Kolthammer, A. Eckstein, I. A. Walmsley, M. Stobińska, Quantum simulations with multiphoton Fock states, npj Quantum Inf. 7, 91 (2021).
- M. Stobińska, A. Buraczewski, M. Moore, W. R. Clements, J. J. Renema, S. W. Nam, T. Gerrits, A. Lita, W. S. Kolthammer, A. Eckstein, I. A. Walmsley, Quantum interference enables constant-time quantum information processing, Sci. Adv. 5, eaau9674 (2019).
