Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1703.00466 · Physical Review X

Architectures for Quantum Simulation Showing a Quantum Speedup

Juan Bermejo-Vega, Dominik Hangleiter, Martin Schwarz, Robert Raussendorf, Jens Eisert

Published Apr 9, 2018• 122 citations
arXivHTMLPDF

Abstract

One of the main aims in the field of quantum simulation is to achieve a quantum speedup, often referred to as "quantum computational supremacy," referring to the experimental realization of a quantum device that computationally outperforms classical computers.In this work, we show that one can devise versatile and feasible schemes of two-dimensional, dynamical, quantum simulators showing such a quantum speedup, building on intermediate problems involving nonadaptive, measurement-based, quantum computation.In each of the schemes, an initial product state is prepared, potentially involving an element of randomness as in disordered models, followed by a short-time evolution under a basic translationally invariant Hamiltonian with simple nearest-neighbor interactions and a mere sampling measurement in a fixed basis.The correctness of the final-state preparation in each scheme is fully efficiently certifiable.We discuss experimental necessities and possible physical architectures, inspired by platforms of cold atoms in optical lattices and a number of others, as well as specific assumptions that enter the complexity-theoretic arguments.This work shows that benchmark settings exhibiting a quantum speedup may require little control, in contrast to universal quantum computing.Thus, our proposal puts a convincing experimental demonstration of a quantum speedup within reach in the near term.

DOI
10.1103/physrevx.8.021010

Related papers

Quantum Computers as Universal Quantum Simulators: State‐of‐the‐Art and Perspectives

Francesco Tacchino, Alessandro Chiesa, Stefano Carretta +1 more

Abstract The past few years have witnessed the concrete and fast spreading of quantum technologies for practical computation and simulation. In particular, quantum computing platforms based on either trapped ions or superconducting qubits have become available for simulations and benchmarking, with up to few tens of qubits that can be reliably initialized, controlled, and measured. The present Review aims at giving a comprehensive outlook on the state‐of‐the‐art capabilities offered from these near‐term noisy devices as universal quantum simulators, that is, programmable quantum computers potentially able to calculate the time evolution of many physical models. First, a pedagogic overview on the basic theoretical background pertaining digital quantum simulations is given, with a focus on hardware‐dependent mapping of spin‐type Hamiltonians into the corresponding quantum circuit as a key initial step toward simulating more complex models. Then, the main experimental achievements obtained in the last decade are reviewed, focusing on the digital quantum simulation of such spin models by employing two leading quantum architectures. Their performances are compared, and future challenges are outlined, also in view of prospective hybrid technologies, towards the ultimate goal of reaching the long‐sought quantum advantage for the simulation of complex many‐body models in the physical sciences.

arXiv:1907.03505•Advanced Quantum Technologies•Dec 19, 2019•172 citations

Quantum speedup in stoquastic adiabatic quantum computation

Keisuke Fujii

Quantum computation provides exponential speedup for solving certain mathematical problems against classical computers. Motivated by current rapid experimental progress on quantum computing devices, various models of quantum computation have been investigated to show quantum computational supremacy. At a commercial side, quantum annealing machine realizes the quantum Ising model with a transverse field and heuristically solves combinatorial optimization problems. The computational power of this machine is closely related to adiabatic quantum computation (AQC) with a restricted type of Hamiltonians, namely stoquastic Hamiltonians, and has been thought to be relatively less powerful compared to universal quantum computers. Little is known about computational quantum speedup nor advantage in AQC with stoquastic Hamiltonians. Here we characterize computational capability of AQC with stoquastic Hamiltonians, which we call stoqAQC. We construct a concrete stoqAQC model, whose lowest energy gap is lower bounded polynomially, and hence the final state can be obtained in polynomial time. Then we show that it can simulate universal quantum computation if adaptive single-qubit measurements in non-standard bases are allowed on the final state. Even if the measurements are restricted to non-adaptive measurements to respect the robustness of AQC, the proposed model exhibits quantum computational supremacy; classical simulation is impossible under complexity theoretical conjectures. Moreover, it is found that such a stoqAQC model can simulate Shor's algorithm and solve the factoring problem in polynomial time. We also propose how to overcome the measurement imperfections via quantum error correction within the stoqAQC model and also an experimentally feasible verification scheme to test whether or not stoqAQC is done faithfully.

arXiv:1803.09954•Mar 27, 2018•14 citations

Exploring Quantum Computing: Potential Applications and Current Challenges in Algorithm Design

Amjed Abbas Ahmed, Mohammad Kamrul Hasan

Quantum supremacy refers to the experimental demonstration that a quantum computing device performs a calculation that no classical computer can match in a reasonable time. Such machines would not be useful for solving problems of practical interest, but they would provide a proof of principle that larger and more useful machines could be built. The gap between classical and quantum computing is potentially enormous, and the apparent ease with which quantum states can be prepared, manipulated, and measured has led many to believe that quantum devices might one day outperform classical hardware at solving a broad range of computational tasks. The most immediate goal of progress in quantum engineering is the construction of a device that passes the proofs of principle of quantum supremacy experiments. They would transform a state that can be initialized neutrally, evolve it under a controlled Hamiltonian, then sample from the output distribution. Such devices must possess sufficient connectivity and low noise but can be cared for by classical software. Their demonstration would mark a historic milestone in the development of quantum technology, providing intrigue and awe but little societal benefit. However, if they can be produced with sufficient fidelity and scale, there is hope that more generally applicable quantum engines might be constructed that could exploit the exponential speedup to outperform classical computers for problems of deep societal importance.

CyberSystem journal.•Jun 30, 2024•5 citations

Quantum Simulations

Antti Regelin

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 $\hat{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.

•Sep 9, 2026•0 citations

Algorithms and Platforms for Quantum Science and Technology

Dominik S. Wild

The field of quantum science and technology has seen tremendous recent progress. Despite this, building large-scale quantum devices remains daunting as fault tolerance is a distant goal in all current experimental platforms. This dissertation discusses two complementary avenues towards practically relevant quantum technologies. In the first part, we explore physically inspired quantum algorithms that run on near-term devices without quantum error correction. We investigate the robustness of adiabatic quantum algorithms, placing stringent requirements on noise induced by the environment. In addition, we construct quantum algorithms that sample from classical Gibbs distributions. These algorithms elucidate connections between computational complexity and phase transitions and provide physical insight into the origin of quantum speedup. The second part focuses on novel platforms and optical interfaces for quantum applications. We demonstrate that optical resonances in ordered arrays of atoms and atomically thin semiconductors offer a powerful tool to control and manipulate light at both the classical and single-photon level. We further study interactions between optical excitations and charge carriers in two-dimensional semiconductors, which give rise to complex quantum many-body dynamics in a largely unexplored regime.

•May 12, 2020•1 citation

Quantum Simulators: Architectures and Opportunities

Ehud Altman, Kenneth R. Brown, Giuseppe Carleo +34 more

Quantum simulators are a promising technology on the spectrum of quantum devices from specialized quantum experiments to universal quantum computers. These quantum devices utilize entanglement and many-particle behaviors to explore and solve hard scientific, engineering, and computational problems. Rapid development over the last two decades has produced more than 300 quantum simulators in operation worldwide using a wide variety of experimental platforms. Recent advances in several physical architectures promise a golden age of quantum simulators ranging from highly optimized special purpose simulators to flexible programmable devices. These developments have enabled a convergence of ideas drawn from fundamental physics, computer science, and device engineering. They have strong potential to address problems of societal importance, ranging from understanding vital chemical processes, to enabling the design of new materials with enhanced performance, to solving complex computational problems. It is the position of the community, as represented by participants of the NSF workshop on "Programmable Quantum Simulators," that investment in a national quantum simulator program is a high priority in order to accelerate the progress in this field and to result in the first practical applications of quantum machines. Such a program should address two areas of emphasis: (1) support for creating quantum simulator prototypes usable by the broader scientific community, complementary to the present universal quantum computer effort in industry; and (2) support for fundamental research carried out by a blend of multi-investigator, multi-disciplinary collaborations with resources for quantum simulator software, hardware, and education.

arXiv:1912.06938•PRX Quantum•Feb 24, 2021•673 citations
One of the main aims in the field of quantum simulation is to achieve a quantum speedup, often referred to as "quantum computational supremacy," referring to the experimental realization of a quantum device that computationally outperforms classical computers.In this work, we show that one can devise versatile and feasible schemes of two-dimensional, dynamical, quantum simulators showing such a quantum speedup, building on intermediate problems involving nonadaptive, measurement-based, quantum computation.In each of the schemes, an initial product state is prepared, potentially involving an element of randomness as in disordered models, followed by a short-time evolution under a basic translationally invariant Hamiltonian with simple nearest-neighbor interactions and a mere sampling measurement in a fixed basis.The correctness of the final-state preparation in each scheme is fully efficiently certifiable.We discuss experimental necessities and possible physical architectures, inspired by platforms of cold atoms in optical lattices and a number of others, as well as specific assumptions that enter the complexity-theoretic arguments.This work shows that benchmark settings exhibiting a quantum speedup may require little control, in contrast to universal quantum computing.Thus, our proposal puts a convincing experimental demonstration of a quantum speedup within reach in the near term.
Abstract The past few years have witnessed the concrete and fast spreading of quantum technologies for practical computation and simulation. In particular, quantum computing platforms based on either trapped ions or superconducting qubits have become available for simulations and benchmarking, with up to few tens of qubits that can be reliably initialized, controlled, and measured. The present Review aims at giving a comprehensive outlook on the state‐of‐the‐art capabilities offered from these near‐term noisy devices as universal quantum simulators, that is, programmable quantum computers potentially able to calculate the time evolution of many physical models. First, a pedagogic overview on the basic theoretical background pertaining digital quantum simulations is given, with a focus on hardware‐dependent mapping of spin‐type Hamiltonians into the corresponding quantum circuit as a key initial step toward simulating more complex models. Then, the main experimental achievements obtained in the last decade are reviewed, focusing on the digital quantum simulation of such spin models by employing two leading quantum architectures. Their performances are compared, and future challenges are outlined, also in view of prospective hybrid technologies, towards the ultimate goal of reaching the long‐sought quantum advantage for the simulation of complex many‐body models in the physical sciences.
Quantum computation provides exponential speedup for solving certain mathematical problems against classical computers. Motivated by current rapid experimental progress on quantum computing devices, various models of quantum computation have been investigated to show quantum computational supremacy. At a commercial side, quantum annealing machine realizes the quantum Ising model with a transverse field and heuristically solves combinatorial optimization problems. The computational power of this machine is closely related to adiabatic quantum computation (AQC) with a restricted type of Hamiltonians, namely stoquastic Hamiltonians, and has been thought to be relatively less powerful compared to universal quantum computers. Little is known about computational quantum speedup nor advantage in AQC with stoquastic Hamiltonians. Here we characterize computational capability of AQC with stoquastic Hamiltonians, which we call stoqAQC. We construct a concrete stoqAQC model, whose lowest energy gap is lower bounded polynomially, and hence the final state can be obtained in polynomial time. Then we show that it can simulate universal quantum computation if adaptive single-qubit measurements in non-standard bases are allowed on the final state. Even if the measurements are restricted to non-adaptive measurements to respect the robustness of AQC, the proposed model exhibits quantum computational supremacy; classical simulation is impossible under complexity theoretical conjectures. Moreover, it is found that such a stoqAQC model can simulate Shor's algorithm and solve the factoring problem in polynomial time. We also propose how to overcome the measurement imperfections via quantum error correction within the stoqAQC model and also an experimentally feasible verification scheme to test whether or not stoqAQC is done faithfully.
Quantum supremacy refers to the experimental demonstration that a quantum computing device performs a calculation that no classical computer can match in a reasonable time. Such machines would not be useful for solving problems of practical interest, but they would provide a proof of principle that larger and more useful machines could be built. The gap between classical and quantum computing is potentially enormous, and the apparent ease with which quantum states can be prepared, manipulated, and measured has led many to believe that quantum devices might one day outperform classical hardware at solving a broad range of computational tasks. The most immediate goal of progress in quantum engineering is the construction of a device that passes the proofs of principle of quantum supremacy experiments. They would transform a state that can be initialized neutrally, evolve it under a controlled Hamiltonian, then sample from the output distribution. Such devices must possess sufficient connectivity and low noise but can be cared for by classical software. Their demonstration would mark a historic milestone in the development of quantum technology, providing intrigue and awe but little societal benefit. However, if they can be produced with sufficient fidelity and scale, there is hope that more generally applicable quantum engines might be constructed that could exploit the exponential speedup to outperform classical computers for problems of deep societal importance.
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^\hat{H}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.
The field of quantum science and technology has seen tremendous recent progress. Despite this, building large-scale quantum devices remains daunting as fault tolerance is a distant goal in all current experimental platforms. This dissertation discusses two complementary avenues towards practically relevant quantum technologies. In the first part, we explore physically inspired quantum algorithms that run on near-term devices without quantum error correction. We investigate the robustness of adiabatic quantum algorithms, placing stringent requirements on noise induced by the environment. In addition, we construct quantum algorithms that sample from classical Gibbs distributions. These algorithms elucidate connections between computational complexity and phase transitions and provide physical insight into the origin of quantum speedup. The second part focuses on novel platforms and optical interfaces for quantum applications. We demonstrate that optical resonances in ordered arrays of atoms and atomically thin semiconductors offer a powerful tool to control and manipulate light at both the classical and single-photon level. We further study interactions between optical excitations and charge carriers in two-dimensional semiconductors, which give rise to complex quantum many-body dynamics in a largely unexplored regime.
Quantum simulators are a promising technology on the spectrum of quantum devices from specialized quantum experiments to universal quantum computers. These quantum devices utilize entanglement and many-particle behaviors to explore and solve hard scientific, engineering, and computational problems. Rapid development over the last two decades has produced more than 300 quantum simulators in operation worldwide using a wide variety of experimental platforms. Recent advances in several physical architectures promise a golden age of quantum simulators ranging from highly optimized special purpose simulators to flexible programmable devices. These developments have enabled a convergence of ideas drawn from fundamental physics, computer science, and device engineering. They have strong potential to address problems of societal importance, ranging from understanding vital chemical processes, to enabling the design of new materials with enhanced performance, to solving complex computational problems. It is the position of the community, as represented by participants of the NSF workshop on "Programmable Quantum Simulators," that investment in a national quantum simulator program is a high priority in order to accelerate the progress in this field and to result in the first practical applications of quantum machines. Such a program should address two areas of emphasis: (1) support for creating quantum simulator prototypes usable by the broader scientific community, complementary to the present universal quantum computer effort in industry; and (2) support for fundamental research carried out by a blend of multi-investigator, multi-disciplinary collaborations with resources for quantum simulator software, hardware, and education.