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• 1 citation
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

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•0 citations

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•1 citation

Beyond real: Alternative unitary cluster Jastrow models for molecular electronic structure calculations on near-term quantum computers

Nikolay V. Tkachenko, Hang Ren, W.M. Billings +3 more

Near-term quantum devices require wavefunction ansätze that are expressive while also of shallow circuit depth in order to both accurately and efficiently simulate molecular electronic structure. While unitary coupled cluster (e.g., UCCSD) has become a standard, the high gate count associated with the implementation of this limits its feasibility on noisy intermediate-scale quantum (NISQ) hardware. K-fold unitary cluster Jastrow (uCJ) ansätze mitigate this challenge by providing $O(kN^2)$ circuit scaling and favorable linear depth circuit implementation. Previous work has focused on the real orbital-rotation (Re-uCJ) variant of uCJ, which allows an exact (Trotter-free) implementation. Here we extend and generalize the $k$-fold uCJ framework by introducing two new variants, Im-uCJ and g-uCJ, which incorporate imaginary and fully complex orbital rotation operators, respectively. Similar to Re-uCJ, both of the new variants achieve quadratic gate-count scaling. Our results focus on the simplest $k=1$ model, and show that the uCJ models frequently maintain energy errors within chemical accuracy. Both g-uCJ and Im-uCJ are more expressive in terms of capturing electron correlation and are also more accurate than the earlier Re-uCJ ansatz. We further show that Im-uCJ and g-uCJ circuits can also be implemented exactly, without any Trotter decomposition. Numerical tests using $k=1$ on $H_2$, $H_3^+$, $Be_2$, $C_2H_4$, $C_2H_6$ and $C_6H_6$ in various basis sets confirm the practical feasibility of these shallow Jastrow-based ansätze for applications on near-term quantum hardware.

arXiv:2505.10963•May 16, 2025•0 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•4 citations

Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy

Michael J. Bremner, Richard Jozsa, Dan J. Shepherd +1 more

We consider quantum computations comprising only commuting gates, known as IQP computations, and provide compelling evidence that the task of sampling their output probability distributions is unlikely to be achievable by any efficient classical means. More specifically, we introduce the class post-IQP of languages decided with bounded error by uniform families of IQP circuits with post-selection, and prove first that post-IQP equals the classical class PP. Using this result we show that if the output distributions of uniform IQP circuit families could be classically efficiently sampled, either exactly in total variation distance or even approximately up to 41 per cent multiplicative error in the probabilities, then the infinite tower of classical complexity classes known as the polynomial hierarchy would collapse to its third level. We mention some further results on the classical simulation properties of IQP circuit families, in particular showing that if the output distribution results from measurements on only O(log n) lines then it may, in fact, be classically efficiently sampled. This journal is © 2010 The Royal Society.

•Jan 1, 2010•216 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•25 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.
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.
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.
Near-term quantum devices require wavefunction ansätze that are expressive while also of shallow circuit depth in order to both accurately and efficiently simulate molecular electronic structure. While unitary coupled cluster (e.g., UCCSD) has become a standard, the high gate count associated with the implementation of this limits its feasibility on noisy intermediate-scale quantum (NISQ) hardware. K-fold unitary cluster Jastrow (uCJ) ansätze mitigate this challenge by providing O(kN2)O(kN^2)O(kN2) circuit scaling and favorable linear depth circuit implementation. Previous work has focused on the real orbital-rotation (Re-uCJ) variant of uCJ, which allows an exact (Trotter-free) implementation. Here we extend and generalize the kkk-fold uCJ framework by introducing two new variants, Im-uCJ and g-uCJ, which incorporate imaginary and fully complex orbital rotation operators, respectively. Similar to Re-uCJ, both of the new variants achieve quadratic gate-count scaling. Our results focus on the simplest k=1k=1k=1 model, and show that the uCJ models frequently maintain energy errors within chemical accuracy. Both g-uCJ and Im-uCJ are more expressive in terms of capturing electron correlation and are also more accurate than the earlier Re-uCJ ansatz. We further show that Im-uCJ and g-uCJ circuits can also be implemented exactly, without any Trotter decomposition. Numerical tests using k=1k=1k=1 on H2H_2H2​, H3+H_3^+H3+​, Be2Be_2Be2​, C2H4C_2H_4C2​H4​, C2H6C_2H_6C2​H6​ and C6H6C_6H_6C6​H6​ in various basis sets confirm the practical feasibility of these shallow Jastrow-based ansätze for applications on near-term quantum hardware.
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.
We consider quantum computations comprising only commuting gates, known as IQP computations, and provide compelling evidence that the task of sampling their output probability distributions is unlikely to be achievable by any efficient classical means. More specifically, we introduce the class post-IQP of languages decided with bounded error by uniform families of IQP circuits with post-selection, and prove first that post-IQP equals the classical class PP. Using this result we show that if the output distributions of uniform IQP circuit families could be classically efficiently sampled, either exactly in total variation distance or even approximately up to 41 per cent multiplicative error in the probabilities, then the infinite tower of classical complexity classes known as the polynomial hierarchy would collapse to its third level. We mention some further results on the classical simulation properties of IQP circuit families, in particular showing that if the output distribution results from measurements on only O(log n) lines then it may, in fact, be classically efficiently sampled. This journal is © 2010 The Royal Society.
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.