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

Hardness of classically sampling quantum chemistry circuits

Ayoub Hafid, Hokuto Iwakiri, Kento Tsubouchi, Nobuyuki Yoshioka, Masaya Kohda

Published Apr 17, 2025• 6 citations
arXivHTMLPDF

Abstract

Significant advances have been made in the study of quantum advantage both in theory and experiment, although these have mostly been limited to artificial setups. In this work, we extend the scope to address quantum advantage in tasks relevant to chemistry and physics. Specifically, we consider the unitary cluster Jastrow (UCJ) ansatz-a variant of the unitary coupled cluster ansatz, which is widely used to solve the electronic structure problem on quantum computers-to show that sampling from the output distributions of quantum circuits implementing the UCJ ansatz is likely to be classically hard. More specifically, we show that there exist UCJ circuits for which classical simulation of sampling cannot be performed in polynomial time, under a reasonable complexity-theoretical assumption that the polynomial hierarchy does not collapse. Our main contribution is to show that a class of UCJ circuits can be used to perform arbitrary instantaneous quantum polynomial-time (IQP) computations, which are already known to be classically hard to simulate under the same complexity assumption. As a side result, we also show that UCJ equipped with post-selection can generate the class post-BQP. Our demonstration, worst-case nonsimulatability of UCJ, would potentially imply quantum advantage in quantum algorithms for chemistry and physics using unitary coupled cluster type ansatzes, such as the variational quantum eigensolver and quantum-selected configuration interaction.

DOI
10.48550/arxiv.2504.12893

Related papers

Efficient classical simulation of large-scale unitary cluster Jastrow circuits

Hrishikesh Belagali, Thomas Van Camp, R. Pradeep +3 more

Recent experiments on quantum computers have challenged the limits of classical computation in chemistry, simulating ground states of strongly correlated molecules. Many of these experiments have utilized the unitary cluster Jastrow ansatz, a quantum circuit inspired by the unitary coupled cluster ansatz that can be tailored to current quantum hardware. Notably, the largest experiment in Sci. Adv. 11, 25 (2025) executed a quantum circuit with 77 qubits and 10,570 gates on an IBM quantum computer and performed classical post-processing with up to 6400 nodes on Fugaku to compute ground state energies better than Hartree-Fock. In this work, we present a polynomial time classical algorithm to compute the energy of any single-layer unitary cluster Jastrow circuit, independent of locality constraints for quantum hardware. Our algorithm can reproduce the largest experiment from Sci. Adv. 11, 25 (2025) in less than a minute on a laptop, and through circuit optimization enabled by fast simulation we achieve a lower ground state energy than the experiment.

quant-pharXiv:2607.21337•Jul 24, 2026•6 citations

Improved parameter initialization for the (local) unitary cluster Jastrow ansatz

Wan-Hsuan Lin, Fangchun Liang, Mario Motta +3 more

The unitary cluster Jastrow (UCJ) ansatz and its variant known as local UCJ (LUCJ) are promising choices for variational quantum algorithms for chemistry due to their combination of physical motivation and hardware efficiency. The parameters of these ansatzes can be initialized from the output of a coupled cluster, singles and doubles (CCSD) calculation performed on a classical computer. However, truncating the number of repetitions of the ansatz, as well as discarding interactions to accommodate the connectivity constraints of near-term quantum processors, degrade the approximation to CCSD and the resulting energy accuracy. In this work, we propose two methods to improve the parameter initialization. The first method, which is applicable to both expectation value- and sample-based algorithms, uses compressed double factorization of the CCSD amplitudes to improve or recover the CCSD approximation. The second method, which is applicable to sample-based algorithms, uses approximate tensor network simulation to improve the quality of samples produced by the ansatz circuit. We validate our methods using exact state vector simulation on systems of up to 52 qubits, as well as experiments on superconducting quantum processors using up to 65 qubits. Our results indicate that our methods can significantly improve the output of both expectation value- and sample-based quantum algorithms.

quant-pharXiv:2511.22476•Nov 28, 2025•13 citations

Classically simulating intermediate-scale instantaneous quantum polynomial circuits through a random graph approach

Julien Codsi, John van de Wetering

Quantum advantage is a demonstration of a computation by a quantum computer that cannot be performed by the best classical computer in a reasonable time. A well-studied approach to demonstrating this on near-term quantum computers is to use random circuit sampling. It has been suggested that a good candidate for demonstrating quantum advantage with random circuit sampling is to use instantaneous quantum polynomial (IQP) circuits. These are quantum circuits where the unitary it implements is diagonal. In this paper, we introduce improved techniques for exactly classically simulating random IQP circuits. We find a simple algorithm to calculate an amplitude of an $n$-qubit IQP circuit with dense random two-qubit interactions in time $O(\frac{{log}^{2}n}{n}{2}^{n})$, which for sparse circuits (where each qubit interacts with $O(logn)$ other qubits) runs in $o({2}^{n}/\mathrm{poly}(n))$ for any given polynomial. Using a more complicated stabilizer decomposition approach we improve the algorithm for dense circuits to $O(\frac{{(logn)}^{4\ensuremath{-}\ensuremath{\beta}}}{{n}^{2\ensuremath{-}\ensuremath{\beta}}}{2}^{n})$ where $\ensuremath{\beta}\ensuremath{\approx}0.396$. We further discuss how our techniques also lead to improved simulation times for IQP circuits on restricted architectures. We benchmarked our main algorithm and found that we can simulate up to 50-qubit circuits in a couple of minutes on a laptop, with 68-qubit sparse circuits taking a couple of hours. We estimate dense 70-qubit circuits are in range for large computing clusters.

arXiv:2212.08609•Physical Review A•Jan 14, 2025•21 citations

Circuit-Depth Reduction of Unitary-Coupled-Cluster Ansatz by Energy Sorting

Yi Fan, Changsu Cao, Xusheng Xu +3 more

Quantum computation represents a revolutionary approach to solving problems in quantum chemistry. However, due to the limited quantum resources in the current noisy intermediate-scale quantum (NISQ) devices, quantum algorithms for large chemical systems remain a major task. In this work, we demonstrate that the circuit depth of the unitary coupled cluster (UCC) and UCC-based ansatzes in the algorithm of the variational quantum eigensolver can be significantly reduced by an energy-sorting strategy. Specifically, subsets of excitation operators are first prescreened from the operator pool according to its contribution to the total energy. The quantum circuit ansatz is then iteratively constructed until convergence of the final energy to a typical accuracy. For demonstration, this method has been successfully applied to molecular and periodic systems. Particularly, a reduction of 50%-98% in the number of operators is observed while retaining the accuracy of the original UCCSD operator pools. This method can be straightforwardly extended to general parametric variational ansatzes.

arXiv:2106.15210•The Journal of Physical Chemistry Letters•Oct 20, 2023•38 citations

Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth

Joel Rajakumar, James D. Watson, Yi-Kai Liu

Sampling from the output distributions of quantum computations comprising only commuting gates, known as instantaneous quantum polynomial (IQP) computations, is believed to be intractable for classical computers, and hence this task has become a leading candidate for testing the capabilities of quantum devices. Here we demonstrate that for an arbitrary IQP circuit undergoing dephasing or depolarizing noise, whose depth is greater than a critical O (1) threshold, the output distribution can be efficiently sampled by a classical computer. Unlike other simulation algorithms for quantum supremacy tasks, we do not require assumptions on the circuit’s architecture, on anti-concentration properties, nor do we require Ω(log (n )) circuit depth. We take advantage of the fact that IQP circuits have deep sections of diagonal gates, which allows the noise to build up predictably and induce a large-scale breakdown of entanglement within the circuit. Our results suggest that quantum supremacy experiments based on IQP circuits may be more susceptible to classical simulation than previously thought. Furthermore, we show that the critical depth threshold of our algorithm is tight, and below this threshold there are noisy IQP circuits which are hard to sample from. Thus we demonstrate that noisy IQP circuits exhibit a phase transition in the computational complexity of sampling, as circuit depth is increased.

arXiv:2403.14607•Society for Industrial and Applied Mathematics eBooks•Jan 1, 2025•27 citations

Barriers to dequantization of near-term molecular electronic structure methods

Oskar Leimkuhler, K. Birgitta Whaley

We prove classical simulation hardness, under the generalized $\mathsf{P}\neq\mathsf{NP}$ conjecture, for quantum circuit families with applications in near-term molecular electronic ground and excited state estimation. The proof exploits a connection to particle number conserving matchgate circuits with fermionic magic state inputs, which are shown to be universal for quantum computation under postselection, and are therefore not classically simulable in the worst case, in either the strong (multiplicative) or weak (sampling) sense. We apply these results to non-orthogonal quantum eigensolvers designed for near-term hardware by ruling out sample-based dequantization strategies to additively approximate the off-diagonal matrix elements between orbital-rotated correlated reference states that satisfy an irreducible fermionic magic property, which combines anticoncentration in any orbital basis with an average-case multiplicative approximation hardness conjecture for the associated matrix polynomials. We apply this complexity analysis to two choices of ansatz that incorporate both static and dynamic correlations to model the electronic eigenstates of molecular systems. These are linear combinations of orbital-rotated matrix product states, which are preparable in linear depth, and linear combinations of states prepared by generalized unitary coupled cluster with singles and doubles or unitary cluster Jastrow circuits of polynomial depth, for which computing the expectation values of local fermionic observables up to a constant additive error is $\mathsf{BQP}$-complete. We discuss the implications for achieving practical quantum advantage in resolving the electronic structure of catalytic systems composed from multivalent transition metal atoms using near-term quantum hardware.

arXiv:2503.21041•Mar 26, 2025•11 citations
Significant advances have been made in the study of quantum advantage both in theory and experiment, although these have mostly been limited to artificial setups. In this work, we extend the scope to address quantum advantage in tasks relevant to chemistry and physics. Specifically, we consider the unitary cluster Jastrow (UCJ) ansatz-a variant of the unitary coupled cluster ansatz, which is widely used to solve the electronic structure problem on quantum computers-to show that sampling from the output distributions of quantum circuits implementing the UCJ ansatz is likely to be classically hard. More specifically, we show that there exist UCJ circuits for which classical simulation of sampling cannot be performed in polynomial time, under a reasonable complexity-theoretical assumption that the polynomial hierarchy does not collapse. Our main contribution is to show that a class of UCJ circuits can be used to perform arbitrary instantaneous quantum polynomial-time (IQP) computations, which are already known to be classically hard to simulate under the same complexity assumption. As a side result, we also show that UCJ equipped with post-selection can generate the class post-BQP. Our demonstration, worst-case nonsimulatability of UCJ, would potentially imply quantum advantage in quantum algorithms for chemistry and physics using unitary coupled cluster type ansatzes, such as the variational quantum eigensolver and quantum-selected configuration interaction.
Recent experiments on quantum computers have challenged the limits of classical computation in chemistry, simulating ground states of strongly correlated molecules. Many of these experiments have utilized the unitary cluster Jastrow ansatz, a quantum circuit inspired by the unitary coupled cluster ansatz that can be tailored to current quantum hardware. Notably, the largest experiment in Sci. Adv. 11, 25 (2025) executed a quantum circuit with 77 qubits and 10,570 gates on an IBM quantum computer and performed classical post-processing with up to 6400 nodes on Fugaku to compute ground state energies better than Hartree-Fock. In this work, we present a polynomial time classical algorithm to compute the energy of any single-layer unitary cluster Jastrow circuit, independent of locality constraints for quantum hardware. Our algorithm can reproduce the largest experiment from Sci. Adv. 11, 25 (2025) in less than a minute on a laptop, and through circuit optimization enabled by fast simulation we achieve a lower ground state energy than the experiment.
The unitary cluster Jastrow (UCJ) ansatz and its variant known as local UCJ (LUCJ) are promising choices for variational quantum algorithms for chemistry due to their combination of physical motivation and hardware efficiency. The parameters of these ansatzes can be initialized from the output of a coupled cluster, singles and doubles (CCSD) calculation performed on a classical computer. However, truncating the number of repetitions of the ansatz, as well as discarding interactions to accommodate the connectivity constraints of near-term quantum processors, degrade the approximation to CCSD and the resulting energy accuracy. In this work, we propose two methods to improve the parameter initialization. The first method, which is applicable to both expectation value- and sample-based algorithms, uses compressed double factorization of the CCSD amplitudes to improve or recover the CCSD approximation. The second method, which is applicable to sample-based algorithms, uses approximate tensor network simulation to improve the quality of samples produced by the ansatz circuit. We validate our methods using exact state vector simulation on systems of up to 52 qubits, as well as experiments on superconducting quantum processors using up to 65 qubits. Our results indicate that our methods can significantly improve the output of both expectation value- and sample-based quantum algorithms.
Quantum advantage is a demonstration of a computation by a quantum computer that cannot be performed by the best classical computer in a reasonable time. A well-studied approach to demonstrating this on near-term quantum computers is to use random circuit sampling. It has been suggested that a good candidate for demonstrating quantum advantage with random circuit sampling is to use instantaneous quantum polynomial (IQP) circuits. These are quantum circuits where the unitary it implements is diagonal. In this paper, we introduce improved techniques for exactly classically simulating random IQP circuits. We find a simple algorithm to calculate an amplitude of an nnn-qubit IQP circuit with dense random two-qubit interactions in time O(log2nn2n)O(\frac{{log}^{2}n}{n}{2}^{n})O(nlog2n​2n), which for sparse circuits (where each qubit interacts with O(logn)O(logn)O(logn) other qubits) runs in o(2n/poly(n))o({2}^{n}/\mathrm{poly}(n))o(2n/poly(n)) for any given polynomial. Using a more complicated stabilizer decomposition approach we improve the algorithm for dense circuits to $O(\frac{{(logn)}^{4\ensuremath{-}\ensuremath{\beta}}}{{n}^{2\ensuremath{-}\ensuremath{\beta}}}{2}^{n})$ where $\ensuremath{\beta}\ensuremath{\approx}0.396$. We further discuss how our techniques also lead to improved simulation times for IQP circuits on restricted architectures. We benchmarked our main algorithm and found that we can simulate up to 50-qubit circuits in a couple of minutes on a laptop, with 68-qubit sparse circuits taking a couple of hours. We estimate dense 70-qubit circuits are in range for large computing clusters.
Quantum computation represents a revolutionary approach to solving problems in quantum chemistry. However, due to the limited quantum resources in the current noisy intermediate-scale quantum (NISQ) devices, quantum algorithms for large chemical systems remain a major task. In this work, we demonstrate that the circuit depth of the unitary coupled cluster (UCC) and UCC-based ansatzes in the algorithm of the variational quantum eigensolver can be significantly reduced by an energy-sorting strategy. Specifically, subsets of excitation operators are first prescreened from the operator pool according to its contribution to the total energy. The quantum circuit ansatz is then iteratively constructed until convergence of the final energy to a typical accuracy. For demonstration, this method has been successfully applied to molecular and periodic systems. Particularly, a reduction of 50%-98% in the number of operators is observed while retaining the accuracy of the original UCCSD operator pools. This method can be straightforwardly extended to general parametric variational ansatzes.
Sampling from the output distributions of quantum computations comprising only commuting gates, known as instantaneous quantum polynomial (IQP) computations, is believed to be intractable for classical computers, and hence this task has become a leading candidate for testing the capabilities of quantum devices. Here we demonstrate that for an arbitrary IQP circuit undergoing dephasing or depolarizing noise, whose depth is greater than a critical O (1) threshold, the output distribution can be efficiently sampled by a classical computer. Unlike other simulation algorithms for quantum supremacy tasks, we do not require assumptions on the circuit’s architecture, on anti-concentration properties, nor do we require Ω(log (n )) circuit depth. We take advantage of the fact that IQP circuits have deep sections of diagonal gates, which allows the noise to build up predictably and induce a large-scale breakdown of entanglement within the circuit. Our results suggest that quantum supremacy experiments based on IQP circuits may be more susceptible to classical simulation than previously thought. Furthermore, we show that the critical depth threshold of our algorithm is tight, and below this threshold there are noisy IQP circuits which are hard to sample from. Thus we demonstrate that noisy IQP circuits exhibit a phase transition in the computational complexity of sampling, as circuit depth is increased.
We prove classical simulation hardness, under the generalized P≠NP\mathsf{P}\neq\mathsf{NP}P=NP conjecture, for quantum circuit families with applications in near-term molecular electronic ground and excited state estimation. The proof exploits a connection to particle number conserving matchgate circuits with fermionic magic state inputs, which are shown to be universal for quantum computation under postselection, and are therefore not classically simulable in the worst case, in either the strong (multiplicative) or weak (sampling) sense. We apply these results to non-orthogonal quantum eigensolvers designed for near-term hardware by ruling out sample-based dequantization strategies to additively approximate the off-diagonal matrix elements between orbital-rotated correlated reference states that satisfy an irreducible fermionic magic property, which combines anticoncentration in any orbital basis with an average-case multiplicative approximation hardness conjecture for the associated matrix polynomials. We apply this complexity analysis to two choices of ansatz that incorporate both static and dynamic correlations to model the electronic eigenstates of molecular systems. These are linear combinations of orbital-rotated matrix product states, which are preparable in linear depth, and linear combinations of states prepared by generalized unitary coupled cluster with singles and doubles or unitary cluster Jastrow circuits of polynomial depth, for which computing the expectation values of local fermionic observables up to a constant additive error is BQP\mathsf{BQP}BQP-complete. We discuss the implications for achieving practical quantum advantage in resolving the electronic structure of catalytic systems composed from multivalent transition metal atoms using near-term quantum hardware.