WHAT QUANTUM COMPUTERS (QC) CAN DO AND WHAT HAS BEEN DONE SO FAR
Relative to classical information processing, quantum computation holds the promise of highly efficient algorithms, providing exponential speedups for some technologically important problems [1]. While only small quantum processors are currently available, there are tremendous expectations for this technology, mainly due to the widespread belief that quantum computing will experience an enormous growth rate in the near future.
Illustration: Christian Gralingen
Quantum computer is in general better to be viewed as GPU coprocessor, because of its ability to calculate some very hard problems, that can take days and weeks on classical computer, but not every program will have this boost, or even can run on quantum computer. In latter we will discuss these sorts of problems. In addition, QCs are usually taking a lot of space, because it is big and it needs a special clean room with no magnet fields. Usually QCs cost a lot of money, for example D-Wave’s quantum computer costs +$10 mil. In case of gate quantum computer, QC’s of IBM, Google and Rigetti additionally will have problems with decoherence and can’t be cheap at maintenance as was explained by Rigetti’s specialist Robert Smith in [2]. But quantum computers do not need to be made with gates. Adiabatic and cluster-state quantum computers are equivalent in power to gate-based quantum computers [3], but their implementation may be simpler for some technologies. [4,5]
Early applications of Quantum annealing can be found in [6] and [7], there are examples when using quantum annealing, optimal solutions to traffic optimizations, asset management, x10 speed up machine learning methods [8] and use cases in quantum chemistry were found [9].
In the market, best QC for production are continuously announced by the largest providers as IBM, Rigetti, AWS, Google,... . Expanded list of existing quantum computers can be found in [10]. Information about qubits’ quality can be found in [11]. When we look at QC simulators, we have Quiskit – free Python library made by IBM and can be used as a simulator or an interactive shell to send program to a QC in the cloud. Other option is Google simulator “Quantum Playground”, that uses GPU and can simulate up to 22 qubits with 3D quantum state visualization.
APPLIED RESEARCH AROUND QC. MAIN ISSUES AND CHALLENGES
Constructing a quantum computer which is capable of outperforming classical computers is a truly formidable task, and potentially one of the great challenges of the century. Before we reach this level, a number of critical issues will have to be dealt with. One of the most important problems is decoherence, i.e: uncontrolled interactions between the system and its environment. This leads to a loss of quantum behavior in the quantum processor, killing any advantage that a quantum algorithm could provide. The decoherence time therefore sets a hard limit on the number of operations we can perform in our quantum algorithm.
It is possible to correct for decoherence using error-correction algorithms. This can be done by encoding the quantum state, with redundancy, over many qubits, and is only possible when the error rate of individual quantum gates is sufficiently small. With these, we can fully build quantum algorithms which run for longer than the decoherence time. A huge obstacle we are facing is that operating a single fault-tolerant qubit can require many thousands of physical qubits. In a recent study, it was estimated that quantum computing could achieve a significant speedup (in absolute time), but this advantage vanished when the classical processing required to implement error-correction schemes was taken into account [12]. Another important challenge is therefore the development of new error-correction schemes with more reasonable requirements. In view of these obstacles, many researchers have turned to algorithms for so called Noisy Intermediate-Scale Quantum (NISQ) processors. These are built to run on faulty quantum computers and produce good results despite decoherence. It is an extremely exciting branch of quantum computing, both highly versatile and a prime candidate to be the first to achieve quantum supremacy [13-17]. Being an extremely new direction of study, we lack an important algorithm library for NISQ machines. This is another great software challenge: to develop new algorithms to make near term quantum computers applicable to real world problems. Quantum computing has been suggested as a solution to many computationally demanding problems, especially in machine learning, which require processing vast amounts of data. At present, we do not have a quantum RAM (qRAM) capable of efficiently encoding this information as a quantum state, and reliably storing it for extended periods of time. This is among the largest hardware challenges for quantum computing
Challenges in development of main types of quantum computers can be found explained with better precision in review paper by Ladd and Jelezko [4]. In their work authors also write about Superconductor QC, that unlike other types of QC they can be readily fabricated using existing technologies and therefore can be more ready for commercial use. Challenges around superconducting QC are about machine learning [18], noise cancellation [19], [20].
One cannot talk about the great breakthroughs that started the field of quantum computing without mentioning Grover’s algorithm, which finds a particular register in an unordered database in (N) steps. By contrast, the best classical algorithm requires (N/2) steps. This algorithm can be adapted to solve optimization problems, such as finding a Minimum Spanning Tree, maximizing flow-like variables, and implementing Monte Carlo methods, which requires exponential time on a classical computer. Optimization techniques are also applicable to machine learning algorithms. Indeed, training can be considered as a special case of optimization for neural networks. Machine learning makes frequent use of Fourier transforms where quantum computers can result in a substantial speedup [21]. And there is a problem for Grover’s and Shor’s algorithms. In theory they can speedup processes of finding a particular register in unordered database, but these algorithms implement a quantum oracle [22,23]. Quantum oracle is a theoretical operator, a black-box operation, that being used on set of unordered database, will find needed particular register in one step. This is not an obvious task to find such physical device, that will know correct answer for every database request. And until now there is no such oracle device for every case, but for some simpler cases such device can be implemented and experimental work is in progress [24]
Other implementations in quantum communications include practical quantum secure direct communication [26], quantum key distribution [27] and use in blockchain communication [28]
Quantum annealing is a scheme of quantum computation that is predicted to be more robust against decoherence, and hence is able to establish well-defined eigenstates. As was discussed in first chapter, many real-world applications have been done. Therefore, main challenges in this field is more of engineering type - to create quantum annealer with more qubits and find optimization problems that can be solved with better speedup, such as quantum chemistry [9,29].
HOW QCS CAN BE USED IN BUSINESS
We have entered an exciting stage in the development of quantum computers. Small-scale, prototype quantum devices with a limited number of qubits are beginning to appear, and companies such as IBM and Rigetti are making such devices available in the cloud. Although current quantum devices tend to be too small, have limited interconnectivity between qubits, and are too noisy to allow meaningful quantum computation, they are an important step forward in the aim to build a large-scale universal quantum computer. [19]
As it was discussed in first chapter, quantum annealers, having less problems with decoherence, were successfully used for different optimization problems, like bus scheduling, election predictions (using machine learning dependent), plant optimization, quantum chemistry evacuation and other optimization problems. Optimization problems are also at the core of many financial problems. This is the case, for instance, of portfolio optimization. In the problem of dynamic portfolio optimization, the aim is to find the optimal trajectory in the portfolio space, while taking into account transaction costs and market impact.
Such a problem was solved on two D-Wave chips with 512 and 1152 qubits [29]. While only small instances were implemented, the performance of the quantum annealers was similar to that of classical hardware. These experiments proved that this problem can be solved on the D-Wave machine with a high success rate. It was also observed that a proper fine-tuning of the D-Wave machines allowed for important improvements in success rates
This and other optimization problems in finance are described in [30]. Besides pure optimization problems, author explains about quantum machine learning and Quantum Monte-Carlo implementations for finance.
LIST OF SOURCES
P.W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Sci. Stat. Comput. 26 (1997) 1484, https://arxiv.org/pdf/quant-ph/9508027.pdf
Mizel, A., Lidar, D. A. & Mitchell, M. Simple proof of equivalence between adiabatic quantum computation and the circuit model. Phys.Rev.Lett. 99,070502 (2007), https://arxiv.org/pdf/quant-ph/0609067.pdf
Ladd, T., Jelezko, F., Laflamme, R. et al. Quantum computing. Nature 464, 45–53 (2010), https://arxiv.org/pdf/1009.2267.pdf
Johnson, M. W., Amin, M. H., Gildert, S., Lanting, T., Hamze, F., Dickson, N., ... & Chapple, E. M. (2011). Quantum annealing with manufactured spins. Nature, 473(7346), 194-198.
Ohzeki, M., Okada, S., Terabe, M., & Taguchi, S. (2018). Optimization of neural networks via finite-value quantum fluctuations. Scientific reports, 8(1), 9950.
Streif, M., Neukart, F., & Leib, M. (2019, March). Solving Quantum Chemistry Problems with a D-Wave Quantum Annealer. In International Workshop on Quantum Technology and Optimization Problems (pp. 111-122). Springer, Cham. https://arxiv.org/pdf/1901.04715.pdf
E. Campbell, A. Khurana, A. Montanaro, Applying quantum algorithms to constraint satisfaction problems, Technical Report, (2019), https://arxiv.org/pdf/1810.05582.pdf
H.G. Katzgraber, Viewing vanilla quantum annealing through spin glasses, Quantum Sci. Technol. 3 (3) (2018) 030505, https://arxiv.org/pdf/1708.08885.pdf
P. Iyer, D. Poulin, A small quantum computer is needed to optimize fault-tolerant protocols, Quantum Sci. Technol. 3 (3) (2018) 030504, https://arxiv.org/pdf/1711.04736.pdf
Perdomo-Ortiz, M. Benedetti, J. Realpe-Gómez, R. Biswas, Opportunities and challenges for quantum-assisted machine learning in near-term quantum computers, Quantum Sci. Technol. 3 (3) (2018) 030502, https://doi.org/10.1088/2058-9565/aab859.
J. Job, D. Lidar, Test-driving 1000 qubits, Quantum Sci. Technol. 3 (3) (2018) 030501, https://doi.org/10.1088/2058-9565/aabd9b.
N. Moll, P. Barkoutsos, L.S. Bishop, J.M. Chow, A. Cross, D.J. Egger, S. Filipp, A. Fuhrer, J.M. Gambetta, M. Ganzhorn, A. Kandala, A. Mezzacapo, P. Müller,
Supervised learning with quantum-enhanced feature spaces V Havlíček, AD Córcoles, K Temme, AW Harrow… - Nature, 2019 - nature.com https://arxiv.org/pdf/1804.11326.pdf
Fault-tolerant logical gates in the ibm quantum experience R Harper, ST Flammia - Physical review letters, 2019 – APS
Harper, R., Flammia, S. T., & Wallman, J. J. (2019). Efficient learning of quantum noise. arXiv preprint arXiv:1907.13022.
P. Rebentrost, M. Mohseni, S. Lloyd, Quantum support vector machine for big data classification, Phys. Rev. Lett. 113 (3) (2014) 1–5, https://doi.org/10.1103/ PhysRevLett.113.130503
Kashefi, E., Kent, A., Vedral, V., & Banaszek, K. (2002). Comparison of quantum oracles. Physical Review A, 65(5), 050304.
Broda, B. (2016). Quantum search of a real unstructured database. The European Physical Journal Plus, 131(2), 38.
Mohammadbagherpoor, H., Oh, Y. H., Singh, A., Yu, X., & Rindos, A. J. (2019). Experimental Challenges of Implementing Quantum Phase Estimation Algorithms on IBM Quantum Computer. arXiv preprint arXiv:1903.07605.
Qi, R., Sun, Z., Lin, Z., Niu, P., Hao, W., Song, L., ... & Long, G. L. (2019). Implementation and security analysis of practical quantum secure direct communication. Light: Science & Applications, 8(1), 22.
Tittel, W. (2019). Quantum key distribution breaking limits. Nature Photonics, 13(5), 310.
Rajan, D., & Visser, M. (2019). Quantum Blockchain using entanglement in time. Quantum Reports, 1(1), 3-11.
Muthukrishnan, S., Albash, T., & Lidar, D. A. (2019). Sensitivity of quantum speedup by quantum annealing to a noisy oracle. Physical Review A, 99(3), 032324.
G. Rosenberg, P. Haghnegahdar, P. Goddard, P. Carr, K. Wu, M.L. de Prado, Solving the optimal trading trajectory problem using a quantum annealer, IEEE J. Sel. Top. Signal Process. 10 (6) (2016) 1053–1060, https://doi.org/10.1109/JSTSP.2016.2574703.
Orús R., Mugel S., Lizaso E. Quantum computing for finance: overview and prospects //Reviews in Physics. – 2019. – С. 100028.
Illustration of Christian Gralingen From Quantum Computing / IEEE Magazine