Algorithms and computational complexity in quantum simulation and quantum machine learning

Leonard Wossnig

In this dissertation, we study the intersection of quantum computing and supervised machine learning algorithms, which means that we investigate quantum algorithms for supervised machine learning that operate on classical data. This area of research falls under the umbrella of quantum machine learning, a research area of computer science which has recently received wide attention. In particular, we investigate to what extent quantum computers can be used to accelerate supervised machine learning algorithms. The aim of this is to develop a clear understanding of the promises and limitations of the current state of the art of quantum algorithms for supervised machine learning, but also to define directions for future research in this exciting field. We start by looking at supervised quantum machine learning (QML) algorithms through the lens of statistical learning theory. In this framework, we derive novel bounds on the computational complexities of a large set of supervised QML algorithms under the requirement of optimal learning rates. Next, we give a new bound for Hamiltonian simulation of dense Hamiltonians, a major subroutine of most known supervised QML algorithms, and then derive a classical algorithm with nearly the same complexity. We then draw the parallels to recent "quantum-inspired" results, and will explain the implications of these results for quantum machine learning applications. Looking for areas which might bear larger advantages for QML algorithms, we finally propose a novel algorithm for Quantum Boltzmann machines, and argue that quantum algorithms for quantum data are one of the most promising applications for QML with potentially exponential advantage over classical approaches.

Roger G. Melko

Rongji Li, Juan Xu, Jiabin Yuan +1 more

Muhammad Adnan

Quantum computing has emerged as a revolutionary technology with the potential to solve complex problems that are difficult for classical computing. Quantum Machine Learning (QML) is a particularly promising field that combines quantum computing with machine learning techniques, aiming to enhance the performance and efficiency of algorithms. This paper explores the competitive performance of quantum algorithms, particularly those leveraging QML, PennyLane, and Fujitsu's Qulacs simulator against the classical counterparts. This research demonstrates that quantum algorithms, when appropriately optimized and executed on powerful simulators like Qulacs can outperform classical algorithms in specific tasks, particularly those involving high-dimensional data and complex optimization landscapes. However, the study also highlights the current limitations of quantum algorithms including the noise and decoherence inherent in quantum systems, which can impact the reliability of results. Continued research and development in quantum algorithms and their integration with machine learning will be crucial for realizing the full potential of quantum computing in solving real-world problems.

Amani Lamine, Ameni Mejri, Bilel Charfi

Haocheng Xiong, Xinyuan Duan, Yue Yu +2 more

Nowadays, using machine learning for image classification is very common. However, due to the increasing demand for data processing and fast computing, the idea of enhancing machine learning with quantum computing has been proposed, known as quantum machine learning (QML). Quantum machine learning has the advantages of higher efficiency and accuracy. Quantum computing uses quantum bits (qubits) for data storage and computing, where a qubit can represent quantum states |0〉and |1〉simultaneously, enabling the processing of information for two states simultaneously, which is unparalleled in classical computing. Moreover, quantum machine learning can handle more complex data and process data faster. In classical machine learning, the processing of large-scale data and complex problems often faces problems of high computational complexity and low algorithm efficiency. Quantum computing can handle multiple computing tasks simultaneously, achieving faster computing. Therefore, in some scenarios that require efficient computing, quantum machine learning may be the best choice. In this study, we simulated quantum circuits using Qiskit and built a hybrid quantum-classical neural network model using VQNet to classify MNIST handwritten digits and CIFAR-10 datasets. The experiments showed that quantum machine learning has the advantages of efficiency, accuracy, and security over classical machine learning, which may be an improvement over classical machine learning. This research proposes a machine learning algorithm based on quantum computing, which promotes the development of quantum computing and quantum technology. At the same time, it provides a new solution and idea for image classification, enabling people to pursue faster and more accurate quantum machine learning instead of being limited to classical machine learning.[1]