Tobias Winker
Sven Groppe
Jiaheng Lu
ABSTRACT
In the last few years, the field of quantum computing has experienced remarkable progress. The prototypes of quantum computers already exist and have been made available to users through cloud services (e.g., IBM Q experience, Google quantum AI, or Xanadu quantum cloud). While fault-tolerant and large-scale quantum computers are not available yet (and may not be for a long time, if ever), the potential of this new technology is undeniable. Quantum algorithms have the proven ability to either outperform classical approaches for several tasks, or are impossible to be efficiently simulated by classical means under reasonable complexity-theoretic assumptions. Even imperfect current-day technology is speculated to exhibit computational advantages over classical systems. Recent research is using quantum computers to solve machine learning tasks. Meanwhile, the database community has already successfully applied various machine learning algorithms for data management tasks, so combining the fields seems to be a promising endeavour. However, quantum machine learning is a new research field for most database researchers. In this tutorial, we provide a fundamental introduction to quantum computing and quantum machine learning and show the potential benefits and applications for database research. In addition, we demonstrate how to apply quantum machine learning to the join order optimization problem in databases.
Supplemental Material
- Scott Aaronson. 2013. Quantum Computing since Democritus. Cambridge University Press, USA.Google Scholar
- Zainab Abohashima, Mohamed Elhosen, Essam H. Houssein, and Waleed M. Mohamed. 2020. Classification with Quantum Machine Learning: A Survey. arXiv arXiv:2006.12270 (2020). https://doi.org/10.48550/ARXIV.2006.12270Google Scholar
- Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, and Oded Regev. 2007. Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation. SIAM J. Comput. 37, 1 (2007), 166--194. https://doi.org/10.1137/S0097539705447323 arXiv:https://doi.org/10.1137/S0097539705447323Google ScholarDigital Library
- T. Albash and D.A. Lidar. 2018. Adiabatic quantum computation. Reviews of Modern Physics 90, 1 (2018). https://doi.org/10.1103/RevModPhys.90.015002Google ScholarCross Ref
- Ryan Babbush, Alejandro Perdomo-Ortiz, Bryan O'Gorman, William Macready, and Alan Aspuru-Guzik. 2014. Construction of Energy Functions for Lattice Heteropolymer Models: Efficient Encodings for Constraint Satisfaction Programming and Quantum Annealing. John Wiley & Sons, Inc., Hoboken, New Jersey, 201--244. https://doi.org/10.1002/9781118755815.ch05Google Scholar
- Zhengbing Bian, Fabian Chudak, Robert Brian Israel, Brad Lackey, William G. Macready, and Aidan Roy. 2016. Mapping Constrained Optimization Problems to Quantum Annealing with Application to Fault Diagnosis. Frontiers in ICT 3 (Jul 2016). https://doi.org/10.3389/fict.2016.00014Google Scholar
- Tim Bittner and Sven Groppe. 2020. Avoiding blocking by scheduling transactions using quantum annealing. In Proceedings of the 24th Symposium on International Database Engineering & Applications. ACM. https://doi.org/10.1145/3410566.3410593Google ScholarDigital Library
- Tim Bittner and Sven Groppe. 2020. Hardware Accelerating the Optimization of Transaction Schedules via Quantum Annealing by Avoiding Blocking. Open Journal of Cloud Computing (OJCC) 7, 1 (2020), 1--21. http://nbn-resolving.de/urn:nbn:de:101:1--2020112218332015343957Google Scholar
- Fernando G. S. L. Brandao and Krysta Svore. 2016. Quantum Speed-ups for Semidefinite Programming. (2016). https://doi.org/10.48550/ARXIV.1609.05537Google Scholar
- Matthias C Caro, Hsin-Yuan Huang, M Cerezo, Kunal Sharma, Andrew Sornborger, Lukasz Cincio, and Patrick J Coles. 2022. Generalization in quantum machine learning from few training data. Nat. Commun. 13, 1 (2022).Google Scholar
- Samuel Yen-Chi Chen, Chih-Min Huang, Chia-Wei Hsing, Hsi-Sheng Goan, and Ying-Jer Kao. 2022. Variational quantum reinforcement learning via evolutionary optimization. Machine Learning: Science and Technology 3, 1 (2 2022), 015025. https://doi.org/10.1088/2632--2153/ac4559Google Scholar
- Carlo Ciliberto, Mark Herbster, Alessandro Davide Ialongo, Massimiliano Pontil, Andrea Rocchetto, Simone Severini, and Leonard Wossnig. 2018. Quantum machine learning: a classical perspective. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 474, 2209 (Jan. 2018), 20170551. https://doi.org/10.1098/rspa.2017.0551Google ScholarCross Ref
- Andrew W. Cross, Lev S. Bishop, Sarah Sheldon, Paul D. Nation, and Jay M. Gambetta. 2019. Validating quantum computers using randomized model circuits. Physical Review A 100, 3 (Sept. 2019). https://doi.org/10.1103/physreva.100.032328Google ScholarCross Ref
- David Deutsch and Richard Jozsa. 1992. Rapid solution of problems by quantum computation. Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences 439, 1907 (Dec 1992), 553--558. https://doi.org/10.1098/rspa.1992.0167Google Scholar
- Suguru Endo, Zhenyu Cai, Simon C. Benjamin, and Xiao Yuan. 2021. Hybrid Quantum-Classical Algorithms and Quantum Error Mitigation. Journal of the Physical Society of Japan 90, 3 (mar 2021), 032001. https://doi.org/10.7566/jpsj.90.032001Google ScholarCross Ref
- Tobias Fankhauser, Marc E Solèr, Rudolf M Füchslin, and Kurt Stockinger. 2021. Multiple query optimization using a hybrid approach of classical and quantum computing. arXiv preprint arXiv:2107.10508 (2021).Google Scholar
- Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. 2014. A Quantum Approximate Optimization Algorithm. (2014). https://doi.org/10.48550/ARXIV.1411.4028Google Scholar
- Marina Fernández-Campoamor, Corey O'Meara, Giorgio Cortiana, Vedran Peric, and Juan Bernabé-Moreno. 2021. Community Detection in Electrical Grids Using Quantum Annealing. arXiv:2112.08300 (Dec 2021). https://doi.org/10.48550/ arXiv.2112.08300 arXiv:2112.08300 [quant-ph].Google Scholar
- Maja Franz, Lucas Wolf, Maniraman Periyasamy, Christian Ufrecht, Daniel D. Scherer, Axel Plinge, Christopher Mutschler, and Wolfgang Mauerer. 2022. Un- covering instabilities in variational-quantum deep Q-networks. Journal of the Franklin Institute (2022). https://doi.org/10.1016/j.jfranklin.2022.08.021Google Scholar
- Erica Grant, Travis S. Humble, and Benjamin Stump. 2021. Benchmarking Quantum Annealing Controls with Portfolio Optimization. Physical Review Applied 15, 1 (Jan 2021), 014012. https://doi.org/10.1103/PhysRevApplied.15.014012Google ScholarCross Ref
- Sven Groppe. 2021. Semantic Hybrid Multi-Model Multi-Platform (SHM3P) Databases. In International Semantic Intelligence Conference (ISIC 2021), New Delhi (hybrid), India. CEUR, 16--26. http://ceur-ws.org/Vol-2786/Paper2.pdfGoogle Scholar
- Sven Groppe and Jinghua Groppe. 2020. Hybrid Multi-Model Multi-Platform (HM3P) Databases. In Proceedings of the 9th International Conference on Data Science, Technology and Applications (DATA). https://doi.org/10.5220/0009802401770184Google ScholarCross Ref
- Sven Groppe and Jinghua Groppe. 2021. Optimizing Transaction Schedules on Universal Quantum Computers via Code Generation for Grover's Search Algorithm. In 25th International Database Engineering & Applications Symposium. ACM. https://doi.org/10.1145/3472163.3472164Google ScholarDigital Library
- Sven Groppe, Jinghua Groppe, Umut Çalikyilmaz, Tobias Winker, and Le Gruenwald. 2022. Quantum Data Management and Quantum Machine Learning for Data Management: State-of-the-Art and Open Challenges. In Proceedings of the EAI ICISML conference.Google Scholar
- Lov K. Grover. 1996. A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96. ACM Press, Philadelphia, Pennsylvania, United States, 212--219. https://doi.org/10.1145/237814.237866Google ScholarDigital Library
- Julian Hans and Sven Groppe. 2022. Silq2Qiskit - Developing a quantum language source-to-source translator. In Proceedings of the 5th International Conference on Computer Science and Software Engineering (CSSE 2022) (Guilin, China). https://doi.org/10.1145/3569966.3570114Google ScholarDigital Library
- Vojtech Havlícek, Antonio D. Córcoles, Kristan Temme, Aram W. Harrow, Abhinav Kandala, Jerry M. Chow, and Jay M. Gambetta. 2019. Supervised learning with quantum-enhanced feature spaces. Nature 567, 7747 (2019), 209--212. https://doi.org/10.1038/s41586-019-0980--2Google Scholar
- Itay Hen and A. P. Young. 2012. Solving the graph-isomorphism problem with a quantum annealer. Physical Review A 86, 4 (Oct 2012), 042310. https://doi.org/10.1103/PhysRevA.86.042310Google ScholarCross Ref
- K. Hornik, M. Stinchcombe, and H. White. 1989. Multilayer feedforward networks are universal approximators. Neural Networks 2, 5 (1989), 359--366.Google ScholarCross Ref
- Hsin-Yuan Huang, Michael Broughton, Masoud Mohseni, Ryan Babbush, Sergio Boixo, Hartmut Neven, and Jarrod R McClean. 2021. Power of data in quantum machine learning. Nat. Commun. 12, 1 (2021).Google Scholar
- Sofiene Jerbi, Casper Gyurik, Simon C. Marshall, Hans J. Briegel, and Vedran Dunjko. 2021. Parametrized quantum policies for reinforcement learning. https://doi.org/10.48550/ARXIV.2103.05577Google Scholar
- Arun Kumar, Matthias Boehm, and Jun Yang. 2017. Data Management in Machine Learning: Challenges, Techniques, and Systems. In Proceedings of the 2017 ACM International Conference on Management of Data (Chicago, Illinois, USA) (SIGMOD '17). Association for Computing Machinery, New York, NY, USA, 1717--1722. https://doi.org/10.1145/3035918.3054775Google ScholarDigital Library
- Joseph M. Landsberg. 2019. A Very Brief Introduction to Quantum Computing and Quantum Information Theory for Mathematicians. Springer International Publishing, Cham, 5--41. https://doi.org/10.1007/978--3-030-06122--7_2Google Scholar
- Guoliang Li, Xuanhe Zhou, and Lei Cao. 2021. AI meets database: AI4DB and DB4AI. In Proceedings of the 2021 International Conference on Management of Data. 2859--2866.Google ScholarDigital Library
- Guoliang Li, Xuanhe Zhou, Shifu Li, and Bo Gao. 2019. QTune: A Query-Aware Database Tuning System with Deep Reinforcement Learning. Proc. VLDB Endow. 12, 12 (aug 2019), 2118--2130. https://doi.org/10.14778/3352063.3352129Google ScholarDigital Library
- Gabriel Paludo Licks and Felipe Meneguzzi. 2020. Automated Database Indexing using Model-free Reinforcement Learning. https://doi.org/10.48550/ARXIV.2007.14244Google Scholar
- Ryan Marcus and Olga Papaemmanouil. 2018. Deep Reinforcement Learning for Join Order Enumeration. In Proceedings of the First International Workshop on Exploiting Artificial Intelligence Techniques for Data Management (Houston, TX, USA) (aiDM'18). Association for Computing Machinery, New York, NY, USA, Article 3, 4 pages. https://doi.org/10.1145/3211954.3211957Google ScholarDigital Library
- Catherine C. McGeoch. 2020. Theory versus practice in annealing-based quantum computing. Theoretical Computer Science 816 (May 2020), 169--183. https://doi.org/10.1016/j.tcs.2020.01.024Google ScholarDigital Library
- K. Mitarai, M. Negoro, M. Kitagawa, and K. Fujii. 2018. Quantum circuit learning. Physical Review A 98, 3 (sep 2018). https://doi.org/10.1103/physreva.98.032309Google ScholarCross Ref
- Florian Neukart, Gabriele Compostella, Christian Seidel, David von Dollen, Sheir Yarkoni, and Bob Parney. 2017. Traffic Flow Optimization Using a Quantum Annealer. Frontiers in ICT 4 (Dec 2017), 29. https://doi.org/10.3389/fict.2017.00029Google Scholar
- Michael A. Nielsen and Isaac L. Chuang. 2010. Quantum computation and quantum information (10th anniversary ed ed.). Cambridge University Press, Cambridge, New York.Google ScholarDigital Library
- Masayuki Ohzeki, Akira Miki, Masamichi J. Miyama, and Masayoshi Terabe. 2019. Control of Automated Guided Vehicles Without Collision by Quantum Annealer and Digital Devices. Frontiers in Computer Science 1 (Nov 2019), 9. https://doi.org/10.3389/fcomp.2019.00009Google Scholar
- Daniel O'Malley, Velimir V. Vesselinov, Boian S. Alexandrov, and Ludmil B. Alexandrov. 2018. Nonnegative/Binary matrix factorization with a D-Wave quantum annealer. PLOS ONE 13, 12 (Dec 2018), e0206653. https://doi.org/10.1371/journal.pone.0206653Google Scholar
- Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. 2019. PyTorch: An Imperative Style, High-Performance Deep Learning Library. In Advances in Neural Information Processing Systems 32. Curran Associates, Inc., 8024--8035. http://papers.neurips.cc/paper/9015-pytorch-an-imperative-style-high-performance-deep-learning-library.pdfGoogle ScholarDigital Library
- WangChun Peng, BaoNan Wang, Feng Hu, YunJiang Wang, XianJin Fang, XingYuan Chen, and Chao Wang. 2019. Factoring larger integers with fewer qubits via quantum annealing with optimized parameters. Science China Physics, Mechanics & Astronomy 62, 6 (Jun 2019), 60311. https://doi.org/10.1007/s11433-018--9307--1Google ScholarCross Ref
- Alejandro Perdomo-Ortiz, Neil Dickson, Marshall Drew-Brook, Geordie Rose, and Alán Aspuru-Guzik. 2012. Finding low-energy conformations of lattice protein models by quantum annealing. Scientific Reports 2, 1 (Dec 2012), 571. https://doi.org/10.1038/srep00571Google ScholarCross Ref
- A. Perdomo-Ortiz, J. Fluegemann, S. Narasimhan, R. Biswas, and V.N. Smelyanskiy. 2015. A quantum annealing approach for fault detection and diagnosis of graph-based systems. The European Physical Journal Special Topics 224, 1 (Feb 2015), 131--148. https://doi.org/10.1140/epjst/e2015-02347-yGoogle ScholarCross Ref
- Adrián Pérez-Salinas, Alba Cervera-Lierta, Elies Gil-Fuster, and José I. Latorre. 2020. Data re-uploading for a universal quantum classifier. Quantum 4 (Feb. 2020), 226. https://doi.org/10.22331/q-2020-02-06--226Google Scholar
- Neoklis Polyzotis, Sudip Roy, Steven Euijong Whang, and Martin Zinkevich. 2017. Data Management Challenges in Production Machine Learning. In Proceedings of the 2017 ACM International Conference on Management of Data (Chicago, Illinois, USA) (SIGMOD '17). Association for Computing Machinery, New York, NY, USA, 1723--1726. https://doi.org/10.1145/3035918.3054782Google ScholarDigital Library
- Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd. 2014. Quantum Support Vector Machine for Big Data Classification. Phys. Rev. Lett. 113 (2014), 130503. Issue 13. https://doi.org/10.1103/PhysRevLett.113.130503Google ScholarCross Ref
- Eleanor G. Rieffel, Davide Venturelli, Bryan O'Gorman, Minh B. Do, Elicia M. Prystay, and Vadim N. Smelyanskiy. 2015. A case study in programming a quantum annealer for hard operational planning problems. Quantum Information Processing 14, 1 (Jan 2015), 1--36. https://doi.org/10.1007/s11128-014-0892-xGoogle ScholarDigital Library
- Maximilian Schlosshauer. 2005. Decoherence, the measurement problem, and interpretations of quantum mechanics. Rev. Mod. Phys. 76 (Feb 2005), 1267--1305. Issue 4. https://doi.org/10.1103/RevModPhys.76.1267Google ScholarCross Ref
- Manuel Schönberger. 2022. Applicability of Quantum Computing on Database Query Optimization. In Proceedings of the 2022 International Conference on Management of Data (SIGMOD), Philadelphia, PA, USA (SIGMOD '22). Association for Computing Machinery, New York, NY, USA, 2512--2514. https://doi.org/10.1145/3514221.3520257Google ScholarDigital Library
- Manuel Schönberger, Maja Franz, Stefanie Scherzinger, and Wolfgang Mauerer. 2022. Peel | Pile? Cross-Framework Portability of Quantum Software. QSA@IEEE International Conference on Software Architecture (ICSA) (2022). https://doi.org/10.1109/ICSA-C54293.2022.00039Google Scholar
- Manuel Schönberger, Stefanie Scherzinger, and Wolfgang Mauerer. 2023. Ready to Leap (by Co-Design)? Join Order Optimisation on Quantum Hardware. In Proceedings of ACM SIGMOD/PODS International Conference on Management of Data.Google ScholarDigital Library
- Peter W. Shor. 1997. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM J. Comput. 26, 5 (Oct 1997), 1484--1509. https://doi.org/10.1137/S0097539795293172Google ScholarDigital Library
- Sukin Sim, Peter D. Johnson, and Alá n Aspuru-Guzik. 2019. Expressibility and Entangling Capability of Parameterized Quantum Circuits for Hybrid Quantum- Classical Algorithms. Advanced Quantum Technologies 2, 12 (2019), 1900070. https://doi.org/10.1002/qute.201900070Google ScholarCross Ref
- Andrea Skolik, Sofiene Jerbi, and Vedran Dunjko. 2022. Quantum agents in the gym: a variational quantum algorithm for deep q-learning. Quantum 6 (2022), 720. https://doi.org/10.22331/q-2022-05--24--720Google ScholarCross Ref
- Matthew Treinish, Jay Gambetta, Paul Nation, Paul Kassebaum, Diego M. Rodríguez, Salvador de la Puente González, Jake Lishman, Shaohan Hu, Kevin Krsulich, Jim Garrison, Luciano Bello, Jessie Yu, Manoel Marques, Julien Gacon, David McKay, Juan Gomez, Lauren Capelluto, Travis-S-IBM, Abby Mitchell, Ashish Panigrahi, lerongil, Rafey Iqbal Rahman, Steve Wood, Toshinari Itoko, Alex Pozas-Kerstjens, Christopher J. Wood, Divyanshu Singh, Drew Risinger, and Eli Arbel. 2022. Qiskit. https://doi.org/10.5281/zenodo.7416349Google Scholar
- Immanuel Trummer and Christoph Koch. 2016. Multiple query optimization on the D-Wave 2X adiabatic quantum computer. Proceedings of the VLDB Endowment 9, 9 (May 2016), 648--659. https://doi.org/10.14778/2947618.2947621Google ScholarDigital Library
- Immanuel Trummer, Junxiong Wang, Ziyun Wei, Deepak Maram, Samuel Moseley, Saehan Jo, Joseph Antonakakis, and Ankush Rayabhari. 2021. SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning. ACM Trans. Database Syst. 46, 3, Article 9 (sep 2021), 45 pages. https://doi.org/10.1145/3464389Google ScholarDigital Library
- Fatma undefinedzcan, Abdul Quamar, Jaydeep Sen, Chuan Lei, and Vasilis Efthymiou. 2020. State of the Art and Open Challenges in Natural Language Interfaces to Data. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data (Portland, OR, USA) (SIGMOD '20). Association for Computing Machinery, New York, NY, USA, 2629--2636. https://doi.org/10.1145/3318464.3383128Google ScholarDigital Library
- Valter Uotila. 2022. Synergy between Quantum Computers and Databases. In Proceedings of the VLDB 2022 PhD Workshop co-located with the 48th International Conference on Very Large Databases (VLDB 2022), Sydney, Australia (CEUR Workshop Proceedings, Vol. 3186), Zhifeng Bao and Timos K. Sellis (Eds.). CEUR-WS.org. http://ceur-ws.org/Vol-3186/paper_1.pdfGoogle Scholar
- Valter Uotila and Jiaheng Lu. 2021. A Formal Category Theoretical Framework for Multi-model Data Transformations. In Heterogeneous Data Management, Polystores, and Analytics for Healthcare, El Kindi Rezig, Vijay Gadepally, Timothy Mattson, Michael Stonebraker, Tim Kraska, Fusheng Wang, Gang Luo, Jun Kong, and Alevtina Dubovitskaya (Eds.). Springer International Publishing, Cham, 14--28.Google Scholar
- Valter Uotila, Jiaheng Lu, Dieter Gawlick, Zhen Hua Liu, Souripriya Das, and Gregory Pogossiants. 2021. MultiCategory: Multi-Model Query Processing Meets Category Theory and Functional Programming. Proc. VLDB Endow. 14, 12 (jul 2021), 2663--2666. https://doi.org/10.14778/3476311.3476314Google ScholarDigital Library
- W. van Dam, M. Mosca, and U. Vazirani. 2001. How powerful is adiabatic quantum computation?. In Proceedings 42nd IEEE Symposium on Foundations of Computer Science. IEEE, Newport Beach, CA, USA, 279--287. https://doi.org/10.1109/SFCS.2001.959902Google ScholarCross Ref
- Manuela Weigold, Johanna Barzen, Frank Leymann, and Marie Salm. 2021. Encoding patterns for quantum algorithms. IET Quantum Communication 2, 4 (2021), 141--152. https://doi.org/10.1049/qtc2.12032Google ScholarDigital Library
- Sheir Yarkoni, Alex Alekseyenko, Michael Streif, David Von Dollen, Florian Neukart, and Thomas Back. 2021. Multi-car paint shop optimization with quantum annealing. In 2021 IEEE International Conference on Quantum Computing and Engineering (QCE). IEEE, Broomfield, CO, USA, 35--41. https://doi.org/10.1109/QCE52317.2021.00019Google ScholarCross Ref
- Renxin Zhao and Shi Wang. 2021. A review of Quantum Neural Networks: Methods, Models, Dilemma. arXiv 2109.01840 (2021). https://doi.org/10.48550/ARXIV.2109.01840Google Scholar
Index Terms
- Quantum Machine Learning: Foundation, New Techniques, and Opportunities for Database Research
Recommendations
Machine learning in the quantum realm: The state-of-the-art, challenges, and future vision
AbstractMachine learning has become a ubiquitous and effective technique for data processing and classification. Furthermore, due to the superiority and progress of quantum computing in many areas (e.g., cryptography, machine learning, ...
Highlights- Organize the most recent research works to pave the way for QML researchers.
- ...
Supercomputing leverages quantum machine learning and Grover’s algorithm
AbstractThe complexity of searching algorithms in classical computing is a classic problem and a research area. Quantum computers and quantum algorithms can efficiently compute some classically hard problems. In addition, quantum machine learning ...
Quantum Machine Learning Applications in High-Energy Physics
ICCAD '22: Proceedings of the 41st IEEE/ACM International Conference on Computer-Aided DesignSome of the most significant achievements of the modern era of particle physics, such as the discovery of the Higgs boson, have been made possible by the tremendous effort in building and operating large-scale experiments like the Large Hadron Collider ...
Comments