All the data stored and processed by our computers is encoded as sequences of zeros and ones, called bits. Quantum computers offer an alternative to this traditional way of encoding and manipulating information. The information in a collection of qubits can be a combination, also called a superposition, over many possible sequences of zeros and ones. Where classical computation consists of flipping zeros and ones, quantum computation consists of manipulating high-dimensional vectors called quantum states. Researchers have found ways to use this to engineer quantum algorithms that solve some tasks much faster than any classical computer would. These are called quantum advantages, and are proven for specific tasks, such as breaking some encryption schemes and solving certain large linear systems. The goal of this thesis was to find new tasks for which quantum computers provably have an advantage over classical computers. In this thesis, I present two such advantages and associated results. The first one revolves around a physically relevant learning task. In other words, I explore how quantum computers can be used to help solve specialized machine learning tasks. The second one addresses the simulation of classical systems. One of the first high-potential and natural uses of quantum computers was the simulation of quantum systems. A lot of real-world problems, however, are ruled by classical physics. It turns out that quantum computers are well suited for the simulation of some exponentially large classical systems. In this thesis, I add a new problem to this list.
All the data stored and processed by our computers is encoded as sequences of zeros and ones, called bits. Quantum computers offer an alternative to this traditional way of encoding and manipulating information. The information in a collection of qubits can be a combination, also called a superposition, over many possible sequences of zeros and ones. Where classical computation consists of flipping zeros and ones, quantum computation consists of manipulating high-dimensional vectors called quantum states. Researchers have found ways to use this to engineer quantum algorithms that solve some tasks much faster than any classical computer would. These are called quantum advantages, and are proven for specific tasks, such as breaking some encryption schemes and solving certain large linear systems. The goal of this thesis was to find new tasks for which quantum computers provably have an advantage over classical computers. In this thesis, I present two such advantages and associated results. The first one revolves around a physically relevant learning task. In other words, I explore how quantum computers can be used to help solve specialized machine learning tasks. The second one addresses the simulation of classical systems. One of the first high-potential and natural uses of quantum computers was the simulation of quantum systems. A lot of real-world problems, however, are ruled by classical physics. It turns out that quantum computers are well suited for the simulation of some exponentially large classical systems. In this thesis, I add a new problem to this list.
Quantum computers acting as ML accelerators have attracted considerable interest as a promising avenue for addressing the limitations of classical computing confronted with solving complex, high-dimensional problems and handling large data sets. The most exciting aspect of quantum computing lies in its quantum advantage via techniques such as quantum parallelism, superposition, and entanglement which allows not only for rapid data processing, but also a means to resolve complex optimization problems beyond the capacity of classical algorithms. Nevertheless, the usage of quantum computing in machine learning is still a fledgling domain, with challenges concerning quantum noise, hardware restrictions, and algorithmic development. In particular, this research is concerned with the development of and study on hybrid quantum-classical algorithms that target to improve ML models in terms of computational capabilities by making use of the best of both worlds. To address this, researchers are developing hybrid algorithms that leverage the strengths of quantum computing for specific tasks, like optimization and pattern recognition, while still relying on classical computing for more flexible and larger-scale processing, ultimately achieving more efficient machine learning systems that can handle large datasets and complex problem-solving more effectively. It includes potential hybrid approaches like quantum-enhanced optimization algorithms, quantum neural networks, and quantum support vector machines, and examines how such algorithms can be used for practical ML problems including data classification, regression and clustering. Furthermore, the paper proposes that hybrid quantum algorithms offer several advantages over their classical counterparts, such as faster convergence rates, higher accuracy in high-dimensional spaces, and improved handling of non-linear and complex problem landscapes. Key advancements in the area of data processing speed and efficiency in problem-solving with and without quantum in the machine learning workflow are also highlighted in the research through comparative analysis and simulation studies. Lastly, the paper concludes by outlining the obstacles yet to be surmounted and the opportunities that lie ahead for hybrid quantum-classical algorithms, such as further improvement of quantum hardware and error mitigation methods, as well as the design of new algorithmic paradigms that seamlessly integrates the classical and quantum computing spaces.
Classical computers have been present for a long time and they have played a significant role in scientific advancements. Quantum computing has shown good results in solving complex problems. Quantum computers use phenomena of quantum superposition and quantum entanglement to form states that scale exponentially with the number of qubits or quantum bits [1]. Classical computers use individual bits, 0 and 1 to store information as binary data & quantum computers use the probability of state before it is measured [2]. Therefore, it gives them a potential to process exponentially more data as compared to classical computers. Unlike classical computers that use binary bits, quantum computers use qubits that are produced by quantum state of object to perform operations. Since, these qubits are quantum, they follow phenomena like quantum superposition and entanglement. Superposition is ability of a quantum system to be in multiple states at the same time. Entanglement is the strong correlation among quantum particles. These phenomena help quantum computers work with 0, 1 and superposition of 0 and 1, giving it advantage of doing complex calculations that classical systems cannot do or take a significant amount of time to get desired results [3]. Quantum computing is used because of its potential for changing time and space complexity of many algorithms we have been using as a solution to linear system of equations [4]. Quantum simulation is one of the most prominent areas of quantum computers, it has the potential to solve the complexities of molecular and chemical interactions which can lead to the discovery of new medicines and materials. Various applications of quantum computing in several significant areas of computer science, such as cryptography, machine learning, deep learning and quantum simulations. They also use various real-life scenarios such as risk analysis, logistics and satellite communication [6].
Over the past several decades, computing has undergone revolutionary changes, moving beyond classical systems that manipulate ones and zeroes to solve complex problems. One key area where quantum computing power is particularly promising is machine learning. While conventional machine learning algorithms have successfully addressed a diverse set of challenges, they are often computationally intensive and slow, while working on today's massive datasets. Quantum machine learning aims to solve these challenges by enhancing classical methods with quantum algorithms, offering faster processing and more efficient data analysis. In recent years, research has focused on applying quantum techniques to classic machine learning tasks. This paper reviews key contributions from researchers in quantum machine learning and explores its potential to revolutionize real-world problem-solving by integrating both traditional and quantum methods.
Quantum simulation involves using a quantum system to study another quantum system. The proposal to simulate quantum physics using quantum mechanical devices, as outlined by Richard Feynman in 1982, stems from classical computers' challenges in simulating quantum systems. The pursuit of simulating complex quantum systems has led to the intersection of quantum mechanics and quantum computing. This offers new opportunities to understand and manipulate the quantum world. Central to describing quantum dynamics is the Hamiltonian operator H^, which governs the time evolution of physical systems and serves as the mathematical foundation for quantum simulations. This thesis explores the methodologies and advancements in simulating Hamiltonian operators on quantum computers, focusing on decomposing these operators into quantum gates and the efficiency gains over classical computational approaches. Initially, the thesis explains the fundamental theory and basics of quantum computing. Further it dives into the foundations of the Hamiltonian operator within quantum mechanics, highlighting its role in describing the dynamics of quantum systems. The complexity and high-dimensional nature of Hamiltonian matrices necessitate using quantum computers to simulate quantum phenomena accurately and efficiently. The process of simulating the Hamiltonian operator on a quantum computer involves a detailed examination of the strategies for decomposing the operator into a sequence of quantum gates. This decomposition is crucial for translating the abstract mathematical description of quantum systems into the physical operations of a quantum computer. By utilizing the principles of quantum mechanics, such as superposition and entanglement, quantum gates manipulate qubits to mimic the evolution of quantum states as the Hamiltonian operator dictates. Latter portions of the thesis are dedicated to comparing the efficiency of quantum simulations against traditional classical simulations and inspecting efficient quantum simulations. Quantum computers offer a polynomial or an exponential speedup for certain classes of problems, such as those involving highly entangled quantum states or requiring the simulation of complex quantum dynamics. This advantage is due to the quantum computer's ability to naturally represent and process quantum information - a task for which classical computers require exponential resources as the system size increases. The efficiency of simulating the Hamiltonian operator on a quantum computer is further enhanced through optimization techniques and algorithmic improvements. These include error mitigation strategies and the development of quantum algorithms tailored to specific types of Hamiltonian operators. The thesis presents a comprehensive analysis of these methods, demonstrating how they make quantum simulations more practical and accessible for scientific research and technological development. In conclusion this thesis is a literature review that examines the transformative potential of quantum simulations. By efficiently simulating the Hamiltonian operator on quantum computers researchers can explore quantum phenomena with precision, paving the way for breakthroughs in quantum physics, materials science, and beyond. The advancements in quantum computing technology and algorithmic approaches discussed here highlight the current capabilities and future explorations in the quantum realm.
Quantum computation is a form of computation utilizing quantum mechanical phenomena.A formal formulation of quantum computer was proposed in 1985, leading to novel quantum algorithms whose computation time scales better, with respect to the problem size, than the classical counterparts.However, running these quantum algorithms requires fault-tolerant implementations, and hence, such engineering in quantum systems can be an overhead in utilizing quantum systems for information processing.This suggests, in addition to seeking faster quantum algorithms, the necessity of exploring how to harness quantum systems more naturally without extensive engineering, leading to another form of quantum information processing.Quantum machine learning (QML) is expected to be a promising approach for harnessing quantum systems for information processing.This is motivated by the fact that the success of neural networks has led to the possibility of solving ML tasks more efficiently with non-digital computer designs.Several QML algorithms that resemble neural networks utilize quantum systems in a manner distinct from digital quantum algorithms.However, training quantum systems is fundamentally challenging, suggesting that it still remains necessary to explore an alternative way of harnessing quantum systems for ML.Along with this direction, the quantum reservoir model harnesses quantum systems in a unique way: nontrivial outputs from an untrained quantum system are leveraged by a linear classical machine learning model to solve various tasks.Hence, the quantum part does not need to be programmable and can be analog quantum dynamics.Without extensive engineering in the quantum part, a quantum reservoir model was shown to be capable of performing nontrivial ML tasks using physical dynamics, which had already been realized experimentally.Therefore, the quantum reservoir model should be one of the promising directions for pursuing another form of quantum information processing.In this thesis, I will investigate the computational capability of natural quantum dynamics in the quantum reservoir model.I will tackle the following critical open questions in this context: (i) how well natural dynamics perform nontrivial ML tasks compared to engineered systems, and (ii) what kind of engineering in quantum dynamics is essential and appropriate for a given task.To tackle the first question (i), I will benchmark the learning performance of various natural quantum dynamics against random circuits that require complicated engineering, thereby revealing the computational power of natural dynamics.For the second question (ii), I will present a characterization method of quantum dynamics that has the potential to bridge quantum properties and their machine learning roles, providing concrete insights into essential and appropriate engineering to design quantum systems for ML.v
Abstract Quantum computers are believed to bring computational advantages in simulating quantum many-body systems. However, recent works have shown that classical machine learning algorithms are able to predict numerous properties of quantum systems with classical data. Despite examples of learning tasks with provable quantum advantages being proposed, they all involve cryptographic functions and do not represent any physical scenarios encountered in laboratory settings. In this paper, we prove quantum advantages for the physically relevant task of learning quantum observables from classical (measured-out) data. We consider two types of observables: first, we prove a learning advantage for linear combinations of Pauli strings, then we extend our results to a broader case of unitarily parametrized observables. For each case, we delineate sharp boundaries separating physically relevant tasks that admit efficient classical learning from those for which a quantum computer remains necessary for data analysis. Unlike previous works, our classical hardness results rely only on the weaker assumption that BQP B Q P hard processes cannot be simulated by polynomial-size classical circuits, and we also provide a nontrivial quantum learning algorithm. Our results clarify when quantum resources are useful for learning problems in quantum many-body physics, and suggest practical directions in which quantum learning improvements may emerge.