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:2205.09203

Exponential challenges in unbiasing quantum Monte Carlo algorithms with quantum computers

Guglielmo Mazzola, Giuseppe Carleo

Published May 18, 2022• 8 citations
arXivHTMLPDF

Abstract

Recently, Huggins et. al. [Nature, 603, 416-420 (2022)] devised a general projective Quantum Monte Carlo method suitable for implementation on quantum computers. This hybrid approach, however, relies on a subroutine -the computation of the local energy estimator on the quantum computer -that is intrinsically affected by an exponential scaling of the computational time with the number of qubits. By means of numerical experiments, we show that this exponential scaling manifests prominently already on systems below the point of "quantum advantage". For the prototypical transverse-field Ising model, we show that the required time resources to compete with classical simulations on around 40 qubits are already of the order of $10^{13}$ projective measurements, with an estimated running time of a few thousand years on superconducting hardware. These observations strongly suggest that the proposed hybrid method, in its present form, is unlikely to offer a sizeable advantage over conventional quantum Monte Carlo approaches.

DOI
10.48550/arxiv.2205.09203

Related papers

Response to "Exponential challenges in unbiasing quantum Monte Carlo algorithms with quantum computers"

Joonho Lee, David R. Reichman, Ryan Babbush +4 more

A recent preprint by Mazzola and Carleo numerically investigates exponential challenges that can arise for the QC-QMC algorithm introduced in our work, "Unbiasing fermionic quantum Monte Carlo with a quantum computer." As discussed in our original paper, we agree with this general concern. However, here we provide further details and numerics to emphasize that the prospects for practical quantum advantage in QC-QMC remain open. The exponential challenges in QC-QMC are dependent on (1) the choice of QMC methods, (2) the underlying system, and (3) the form of trial and walker wavefunctions. While one can find difficult examples with a specific method, a specific system, and a specific walker/trial form, for some combinations of these choices, the approach is potentially more scalable than other near-term quantum algorithms. Future research should aim to identify examples for which QC-QMC enables practical quantum advantage.

arXiv:2207.13776•Jul 27, 2022•3 citations

Evaluating a quantum-classical quantum Monte Carlo algorithm with Matchgate shadows

Benchen Huang, Yi-Ting Chen, Brajesh Gupt +4 more

Solving the electronic structure problem of molecules and solids to high accuracy is a major challenge in quantum chemistry and condensed matter physics. The rapid emergence and development of quantum computers offer a promising route to systematically tackle this problem. Recent work by [Huggins , ] proposed a hybrid quantum-classical quantum Monte Carlo (QC-QMC) algorithm using Clifford shadows to determine the ground state of a Fermionic Hamiltonian. This approach displayed inherent noise resilience and the potential for improved accuracy compared to its purely classical counterpart. Nevertheless, the use of Clifford shadows introduces an exponentially scaling postprocessing cost. In this work, we investigate an improved QC-QMC scheme utilizing the recently developed Matchgate shadows technique [], which removes the aforementioned exponential bottleneck. We observe from experiments on quantum hardware that the use of Matchgate shadows in QC-QMC is inherently noise robust. We show that this noise resilience has a more subtle origin than in the case of Clifford shadows. Nevertheless, we find that classical postprocessing, while asymptotically efficient, requires hours of runtime on thousands of classical CPUs for even the smallest chemical systems, presenting a major challenge to the scalability of the algorithm. Published by the American Physical Society 2024

arXiv:2404.18303•Physical Review Research•Oct 24, 2024•19 citations

Hybrid Quantum-Classical Algorithms for Quantum Computing Applications in Computational Physics

Julian Schuhmacher

Computational methods are central to modern physics, yet many problems, especially those involving Quantum Many-Body Systems (QMBSs), remain challenging at scale. The core difficulty of simulating QMBSs is the exponential growth of the solution space with system size. This renders exact treatments intractable and pushes approximate methods to their limits when tackling two- and higher-dimensional systems and long-time dynamics. Quantum computers offer a quantum-native platform for representing and manipulating such systems. Recent algorithmic and technological advancements have enabled experiments on quantum processors in the quantum utility regime, a scale at which exact classical reproduction is no longer feasible. This represents the first step towards realizing quantum advantage, where quantum computers solve specific, practically relevant problems more efficiently than any classical approach. While advancing towards the goal of quantum advantage, useful computations on quantum processors are expected to be realised through hybrid quantum-classical algorithms, which combine quantum experiments and classical computational resources. A prominent example are variational quantum algorithms, where a Parametrized Quantum Circuit (PQC) prepares a trial quantum state whose parameters are iteratively updated by a classical optimisation routine to minimize a target cost function (e.g., the energy of a target Hamiltonian). However, the optimisation of such PQCs is affected by trainability issues, such as barren plateaus in the parameter landscape, which can render the optimisation increasingly difficult for larger system sizes. This motivates the development of novel hybrid approaches overcoming the limits of PQCs. In this thesis, we introduce a new class of approaches based on hybrid Tensor Networks (TNs). A hybrid TN is obtained by integrating quantum states prepared on a quantum processor within TNs -- one of the state-of-the-art approaches for simulating quantum systems. We first show how hybrid TNs can be used for ground-state searches within a variational setting. Then, we further extend the framework to non-variational hybrid TN ansätze for which the quantum tensors are prepared via quantum annealing and subsequently post-processed by classical TNs. In the context of quantum machine learning, which also relies on PQCs, we further investigate heuristic best practices that mitigate the same exponential concentration effects in kernel-based models for anomaly detection. Another class of hybrid algorithms are quantum error-mitigation workflows, where classical post-processing is used to reconstruct expectation values from noise-affected circuit executions. Such methods generally feature a trade-off between the bias and the variance: the price to pay for mitigating noise in a bias-free fashion is that the number of measurements usually grows exponentially with the depth of the circuit in order to achieve a fixed accuracy. In this thesis, we develop a low-resource error-mitigation strategy that reduces the measurement overhead in practical digital Hamiltonian-simulation workflows. We apply this method to Trotterized dynamics in a lattice-gauge-theory model, enabling the extraction of expectation values with improved accuracy at time-scales that allow the observation of post-collision scattering dynamics.

•Jan 1, 2026•0 citations

Quantum-assisted Monte Carlo algorithms for fermions

Xiaosi Xu, Ying Li

Quantum computing is a promising way to systematically solve the longstanding computational problem, the ground state of a many-body fermion system. Many efforts have been made to realise certain forms of quantum advantage in this problem, for instance, the development of variational quantum algorithms. A recent work by Huggins et al. [1] reports a novel candidate, i.e. a quantum-classical hybrid Monte Carlo algorithm with a reduced bias in comparison to its fully-classical counterpart. In this paper, we propose a family of scalable quantum-assisted Monte Carlo algorithms where the quantum computer is used at its minimal cost and still can reduce the bias. By incorporating a Bayesian inference approach, we can achieve this quantum-facilitated bias reduction with a much smaller quantum-computing cost than taking empirical mean in amplitude estimation. Besides, we show that the hybrid Monte Carlo framework is a general way to suppress errors in the ground state obtained from classical algorithms. Our work provides a Monte Carlo toolkit for achieving quantum-enhanced calculation of fermion systems on near-term quantum devices.

arXiv:2205.14903•Quantum•Aug 3, 2023•16 citations

Resource-efficient quantum-classical hybrid algorithm for energy gap evaluation

Yongdan Yang, Ying Li, Xiaosi Xu +1 more

Estimating the eigenvalue or energy gap of a Hamiltonian $H$ is vital for studying quantum many-body systems. Particularly, many of the problems in quantum chemistry, condensed-matter physics, and nuclear physics investigate the energy gap between two eigenstates. Hence, how to efficiently solve the energy gap becomes an important motive for researching new quantum algorithms. In this work, we propose a hybrid nonvariational quantum algorithm that uses the Monte Carlo method and real-time Hamiltonian simulation to evaluate the energy gap of a general quantum many-body system. Compared to conventional approaches, our algorithm does not require controlled real-time evolution, thus making its implementation much more experimental friendly for near-term quantum devices and early fault-tolerant quantum computers. To verify the efficiency of our algorithm, we conduct numerical simulations for the Heisenberg model and molecule systems on a classical emulator.

Physical Review A•May 10, 2024•6 citations

Perils of embedding for quantum sampling

Jeffrey Marshall, Gianni Mossi, Eleanor Gilbert Rieffel

Given quantum hardware that enables sampling from a family of natively implemented Hamiltonians, how well can one use that hardware to sample from a Hamiltonian outside that family? A common approach is to minor embed the desired Hamiltonian in a native Hamiltonian. In Phys. Rev. Research 2, 023020 (2020) it was shown that minor embedding can be detrimental for classical thermal sampling. Here we generalize these results by considering quantum thermal sampling in the transverse-field Ising model, i.e., sampling a Hamiltonian with nonzero off diagonal terms. In the quantum case, loosely speaking, it is even harder to preserve the correct distribution properties, since the local transverse fields affect the physical qubits in the embedding in a manner that cannot be lifted by setting an appropriate energy scale, as in the classical case. To study these systems numerically we introduce a modification to standard cluster update quantum Monte Carlo (QMC) techniques, which allows us to much more efficiently obtain thermal samples of an embedded Hamiltonian, enabling us to simulate systems of much larger sizes and larger transverse-field strengths than would otherwise be possible. Our numerics focus on models that can be implemented on current quantum devices using planar two-dimensional lattices, which exhibit a phase transition driven by the transverse-field strength. Our results include the following: (1) We give an estimate on the probability to sample the logical subspace directly as a function of transverse-field, temperature, and total system size, which agrees with QMC simulations. (2) We show that typically measured observables (diagonal energy and magnetization) are biased by the embedding process, in the regime of intermediate transverse-field strength, meaning that the extracted values are not the same as in the native model. (3) By considering individual embedding realizations akin to ``realizations of disorder,'' we provide numerical evidence suggesting that as the embedding size is increased, the critical point shifts to increasingly large values of the transverse field.

arXiv:2103.07036•Physical Review A•Feb 22, 2022•8 citations
Recently, Huggins et. al. [Nature, 603, 416-420 (2022)] devised a general projective Quantum Monte Carlo method suitable for implementation on quantum computers. This hybrid approach, however, relies on a subroutine -the computation of the local energy estimator on the quantum computer -that is intrinsically affected by an exponential scaling of the computational time with the number of qubits. By means of numerical experiments, we show that this exponential scaling manifests prominently already on systems below the point of "quantum advantage". For the prototypical transverse-field Ising model, we show that the required time resources to compete with classical simulations on around 40 qubits are already of the order of 101310^{13}1013 projective measurements, with an estimated running time of a few thousand years on superconducting hardware. These observations strongly suggest that the proposed hybrid method, in its present form, is unlikely to offer a sizeable advantage over conventional quantum Monte Carlo approaches.
A recent preprint by Mazzola and Carleo numerically investigates exponential challenges that can arise for the QC-QMC algorithm introduced in our work, "Unbiasing fermionic quantum Monte Carlo with a quantum computer." As discussed in our original paper, we agree with this general concern. However, here we provide further details and numerics to emphasize that the prospects for practical quantum advantage in QC-QMC remain open. The exponential challenges in QC-QMC are dependent on (1) the choice of QMC methods, (2) the underlying system, and (3) the form of trial and walker wavefunctions. While one can find difficult examples with a specific method, a specific system, and a specific walker/trial form, for some combinations of these choices, the approach is potentially more scalable than other near-term quantum algorithms. Future research should aim to identify examples for which QC-QMC enables practical quantum advantage.
Solving the electronic structure problem of molecules and solids to high accuracy is a major challenge in quantum chemistry and condensed matter physics. The rapid emergence and development of quantum computers offer a promising route to systematically tackle this problem. Recent work by [Huggins , ] proposed a hybrid quantum-classical quantum Monte Carlo (QC-QMC) algorithm using Clifford shadows to determine the ground state of a Fermionic Hamiltonian. This approach displayed inherent noise resilience and the potential for improved accuracy compared to its purely classical counterpart. Nevertheless, the use of Clifford shadows introduces an exponentially scaling postprocessing cost. In this work, we investigate an improved QC-QMC scheme utilizing the recently developed Matchgate shadows technique [], which removes the aforementioned exponential bottleneck. We observe from experiments on quantum hardware that the use of Matchgate shadows in QC-QMC is inherently noise robust. We show that this noise resilience has a more subtle origin than in the case of Clifford shadows. Nevertheless, we find that classical postprocessing, while asymptotically efficient, requires hours of runtime on thousands of classical CPUs for even the smallest chemical systems, presenting a major challenge to the scalability of the algorithm. Published by the American Physical Society 2024
Computational methods are central to modern physics, yet many problems, especially those involving Quantum Many-Body Systems (QMBSs), remain challenging at scale. The core difficulty of simulating QMBSs is the exponential growth of the solution space with system size. This renders exact treatments intractable and pushes approximate methods to their limits when tackling two- and higher-dimensional systems and long-time dynamics. Quantum computers offer a quantum-native platform for representing and manipulating such systems. Recent algorithmic and technological advancements have enabled experiments on quantum processors in the quantum utility regime, a scale at which exact classical reproduction is no longer feasible. This represents the first step towards realizing quantum advantage, where quantum computers solve specific, practically relevant problems more efficiently than any classical approach. While advancing towards the goal of quantum advantage, useful computations on quantum processors are expected to be realised through hybrid quantum-classical algorithms, which combine quantum experiments and classical computational resources. A prominent example are variational quantum algorithms, where a Parametrized Quantum Circuit (PQC) prepares a trial quantum state whose parameters are iteratively updated by a classical optimisation routine to minimize a target cost function (e.g., the energy of a target Hamiltonian). However, the optimisation of such PQCs is affected by trainability issues, such as barren plateaus in the parameter landscape, which can render the optimisation increasingly difficult for larger system sizes. This motivates the development of novel hybrid approaches overcoming the limits of PQCs. In this thesis, we introduce a new class of approaches based on hybrid Tensor Networks (TNs). A hybrid TN is obtained by integrating quantum states prepared on a quantum processor within TNs -- one of the state-of-the-art approaches for simulating quantum systems. We first show how hybrid TNs can be used for ground-state searches within a variational setting. Then, we further extend the framework to non-variational hybrid TN ansätze for which the quantum tensors are prepared via quantum annealing and subsequently post-processed by classical TNs. In the context of quantum machine learning, which also relies on PQCs, we further investigate heuristic best practices that mitigate the same exponential concentration effects in kernel-based models for anomaly detection. Another class of hybrid algorithms are quantum error-mitigation workflows, where classical post-processing is used to reconstruct expectation values from noise-affected circuit executions. Such methods generally feature a trade-off between the bias and the variance: the price to pay for mitigating noise in a bias-free fashion is that the number of measurements usually grows exponentially with the depth of the circuit in order to achieve a fixed accuracy. In this thesis, we develop a low-resource error-mitigation strategy that reduces the measurement overhead in practical digital Hamiltonian-simulation workflows. We apply this method to Trotterized dynamics in a lattice-gauge-theory model, enabling the extraction of expectation values with improved accuracy at time-scales that allow the observation of post-collision scattering dynamics.
Quantum computing is a promising way to systematically solve the longstanding computational problem, the ground state of a many-body fermion system. Many efforts have been made to realise certain forms of quantum advantage in this problem, for instance, the development of variational quantum algorithms. A recent work by Huggins et al. [1] reports a novel candidate, i.e. a quantum-classical hybrid Monte Carlo algorithm with a reduced bias in comparison to its fully-classical counterpart. In this paper, we propose a family of scalable quantum-assisted Monte Carlo algorithms where the quantum computer is used at its minimal cost and still can reduce the bias. By incorporating a Bayesian inference approach, we can achieve this quantum-facilitated bias reduction with a much smaller quantum-computing cost than taking empirical mean in amplitude estimation. Besides, we show that the hybrid Monte Carlo framework is a general way to suppress errors in the ground state obtained from classical algorithms. Our work provides a Monte Carlo toolkit for achieving quantum-enhanced calculation of fermion systems on near-term quantum devices.
Estimating the eigenvalue or energy gap of a Hamiltonian HHH is vital for studying quantum many-body systems. Particularly, many of the problems in quantum chemistry, condensed-matter physics, and nuclear physics investigate the energy gap between two eigenstates. Hence, how to efficiently solve the energy gap becomes an important motive for researching new quantum algorithms. In this work, we propose a hybrid nonvariational quantum algorithm that uses the Monte Carlo method and real-time Hamiltonian simulation to evaluate the energy gap of a general quantum many-body system. Compared to conventional approaches, our algorithm does not require controlled real-time evolution, thus making its implementation much more experimental friendly for near-term quantum devices and early fault-tolerant quantum computers. To verify the efficiency of our algorithm, we conduct numerical simulations for the Heisenberg model and molecule systems on a classical emulator.
Given quantum hardware that enables sampling from a family of natively implemented Hamiltonians, how well can one use that hardware to sample from a Hamiltonian outside that family? A common approach is to minor embed the desired Hamiltonian in a native Hamiltonian. In Phys. Rev. Research 2, 023020 (2020) it was shown that minor embedding can be detrimental for classical thermal sampling. Here we generalize these results by considering quantum thermal sampling in the transverse-field Ising model, i.e., sampling a Hamiltonian with nonzero off diagonal terms. In the quantum case, loosely speaking, it is even harder to preserve the correct distribution properties, since the local transverse fields affect the physical qubits in the embedding in a manner that cannot be lifted by setting an appropriate energy scale, as in the classical case. To study these systems numerically we introduce a modification to standard cluster update quantum Monte Carlo (QMC) techniques, which allows us to much more efficiently obtain thermal samples of an embedded Hamiltonian, enabling us to simulate systems of much larger sizes and larger transverse-field strengths than would otherwise be possible. Our numerics focus on models that can be implemented on current quantum devices using planar two-dimensional lattices, which exhibit a phase transition driven by the transverse-field strength. Our results include the following: (1) We give an estimate on the probability to sample the logical subspace directly as a function of transverse-field, temperature, and total system size, which agrees with QMC simulations. (2) We show that typically measured observables (diagonal energy and magnetization) are biased by the embedding process, in the regime of intermediate transverse-field strength, meaning that the extracted values are not the same as in the native model. (3) By considering individual embedding realizations akin to ``realizations of disorder,'' we provide numerical evidence suggesting that as the embedding size is increased, the critical point shifts to increasingly large values of the transverse field.