REVIEW 4 minor 2 cited by
Hardness of classically sampling quantum chemistry circuits
T0 review · 0 major / 4 minor · reviewed 2026-08-16 · deepseek-v4-flash
Pith's one-line read Single-layer unitary cluster Jastrow circuits can emulate quadratic-Ising IQP circuits, so sampling from some quantum chemistry ansaetze is worst-case classically hard unless the polynomial hierarchy collapses.
desk verdict A clean worst-case hardness reduction from quadratic-Ising IQP to single-layer UCJ; the stress-test's missing-gadget concern does not survive a check of the BJS gate set. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
The authors build an explicit mapping. In the UCJ ansatz, electrons occupy orbitals, and the circuit applies an orbital rotation, a diagonal phase depending on electron occupancies, and another orbital rotation. By pairing the highest occupied orbital with the lowest unoccupied orbital, each pair becomes one effective qubit. Choosing the rotation angles carefully makes each pair implement the Hadamard gate of an IQP circuit. The diagonal phase gates of UCJ then implement the Z-rotations and controlled-phase gates that the IQP diagonal part needs. The result is that every IQP circuit with a quadratic phase can be reproduced exactly as a single-layer UCJ circuit, using twice as many orbitals.
Because IQP sampling is known to be classically hard under the assumption that the polynomial hierarchy does not collapse, the same hardness transfers to UCJ. The proof is worst case: it shows that some circuits are hard, not that every physical instance is hard. The authors also show that UCJ with post-selection can perform the powerful class post-BQP. Average-case hardness and noisy-device behavior remain open, and the paper says so explicitly.
Extended reading notes
Core claim
Theorem III.1: 1-UCJ_JW contains IQP, meaning for every n-qubit IQP circuit H^⊗n e^{iD} H^⊗n with D a quadratic polynomial in Pauli Z operators, there is a single-layer UCJ circuit on 4n spin orbitals whose output distribution is identical. If correct, weak classical simulation of 1-UCJ circuits with multiplicative error 1 <= c < sqrt(2) would collapse the polynomial hierarchy to the third level.
Load-bearing premise
The reduced input class is hard: IQP circuits with diagonal part restricted to the quadratic form D (Eq. 1) must inherit the post-IQP = post-BQP hardness of Ref [31]. The paper justifies this in one paragraph by noting e^{iD} can implement the diagonal gates in Ref [31]'s universal gate set, but it does not fully spell out the Hadamard-gadget argument for this restricted class. If this restricted family were classically simulable, the reduction from IQP to 1-UCJ would not imply hardness.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper proves worst-case classical hardness of sampling from the output distribution of single-layer unitary cluster Jastrow (1-UCJ) circuits, a chemistry-motivated ansatz. The main theorem (Theorem III.1) states that the class of Jordan-Wigner-transformed 1-UCJ circuits contains IQP circuits whose diagonal part is e^{iD}, where D is quadratic in Pauli Z operators. The proof explicitly constructs each IQP Hadamard gate from a restricted Givens rotation V_alpha, and each diagonal gate from products of D_pq operators, with a clear identification of IQP qubits with particle-number-conserving two-orbital subspaces. Combined with the Bremner-Jozsa-Shepherd result that IQP circuits are hard to weakly simulate under the assumption that the polynomial hierarchy does not collapse, the paper concludes that efficient classical sampling of 1-UCJ circuits with multiplicative error 1 <= c < sqrt(2) would collapse the polynomial hierarchy to the third level. A side result shows post-1-UCJ_JW = post-BQP.
Significance. If correct, this is a meaningful step toward quantum advantage in practical quantum chemistry, as it targets a circuit family used in VQE-type and QSCI algorithms rather than an artificial sampling problem. The reduction is explicit and checkable, and the paper honestly frames the result as worst-case hardness. The technical core—the emulation of IQP by 1-UCJ—is sound; I specifically verified that the Hadamard gadget in Ref. [31] requires only a controlled-Z gate and postselection (together with the boundary Hadamard gates), so the restriction to quadratic D does not weaken the hardness argument. This addresses the main potential concern about the hardness transfer.
minor comments (4)
- [II.B] The justification that the complexity argument is unaffected by restricting IQP's diagonal part to the quadratic form of Eq. (1) is compressed; since this step is load-bearing for the hardness transfer, I recommend adding a brief explanation that the Hadamard gadget in Ref. [31] requires only a controlled-Z gate and postselected measurement (together with the boundary Hadamard gates), all of which are available in the e^{iD} family.
- [Theorem III.1] The statement '1-UCJ_JW ⊇ IQP' might be misread as referring to the unrestricted IQP class; because the paper adopts the quadratic-D restriction in Eq. (1), please define the notation explicitly (e.g., 'IQP with quadratic diagonal') to avoid ambiguity.
- [Appendix A, Eq. (A7)] In Eq. (A7), the subscript 'n−α−0' should read 'n−α−1'; this is a typographical error in an otherwise clear derivation.
- [Abstract and Section III.B] The abstract refers to a 'single-layer UCJ circuit on 4n spin orbitals', while the proof constructs a 2n-qubit circuit after ignoring the spin-down sector; please clarify that the spin-down sector is a passive product state that is traced out, so the effective hard circuit has 2n qubits.
Assumptions & free parameters
assumptions (4)
- domain assumption The polynomial hierarchy does not collapse to the third level.
- standard math post-IQP = post-BQP and weak simulation of post-IQP circuits with multiplicative error implies collapse of the polynomial hierarchy (Ref [31]).
- ad hoc to paper IQP circuits whose diagonal part is a quadratic polynomial in Z operators retain the hardness of general IQP circuits.
- standard math Any real anti-symmetric orbital rotation e^K can be decomposed into Givens rotations R_pq(T_pq).
Cite this review
Pith. "Pith review of Hardness of classically sampling quantum chemistry circuits." pith.science (2026). https://pith.science/paper/W2RUYM3A
@misc{pith2026250412893,
author = {Pith},
title = {Pith review of: Hardness of classically sampling quantum chemistry circuits},
year = {2026},
howpublished = {\url{https://pith.science/paper/W2RUYM3A}},
note = {Machine review of arXiv:2504.12893}
}
read the original 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.
Figures
Figures from the paper (3 more)
Forward citations
Cited by 2 Pith papers
-
Machine learning for sample-based quantum diagonalization: generative configuration recovery and the classical-simulability frontier
A critical review plus small exact-FCI experiments concludes that sample-based quantum diagonalization has not beaten classical selected CI and maps where, if anywhere, a quantum or generative advantage could survive.
-
Coupled cluster method tailored by quantum selected configuration interaction
QSCI-TCC combines quantum-selected CI with tailored coupled-cluster to achieve accurate bond-breaking energies while using far fewer measurement shots.
Reference graph
Works this paper leans on
-
[43]
Van Den Nest, Simulating quantum computers with probabilistic methods, Quantum Info
M. Van Den Nest, Simulating quantum computers with probabilistic methods, Quantum Info. Comput. 11, 784–812 (2011)
2011
- [31]
-
[1]
F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, et al. , Quantum supremacy using a pro- 10 grammable superconducting processor, Nature 574, 505 (2019)
work page 2019
-
[2]
Therefore, given the collapse of the polyno- mial hierarchy is unlikely, it is implausible that 1-UCJ circuits are classically tractable to sample. As a side result, we note that the following can also be shown by repeating essentially the same proof as in Ref. [31]: post-1-UCJJW = post-IQP = post-BQP. IV. SUMMAR Y AND DISCUSSION In this work, we have sho...
work page 2025
- [3]
-
[4]
L. S. Madsen, F. Laudenbach, M. F. Askarani, F. Ror- tais, T. Vincent, J. F. F. Bulmer, F. M. Miatto, L. Neuhaus, L. G. Helt, M. J. Collins, A. E. Lita, T. Gerrits, S. W. Nam, V. D. Vaidya, M. Menotti, et al. , Quantum computational advantage with a pro- grammable photonic processor, Nature 606, 75 (2022)
work page 2022
-
[5]
Q. Zhu, S. Cao, F. Chen, M.-C. Chen, X. Chen, T.-H. Chung, H. Deng, Y. Du, D. Fan, M. Gong, C. Guo, C. Guo, S. Guo, L. Han, L. Hong, et al., Quantum com- putational advantage via 60-qubit 24-cycle random cir- cuit sampling, Sci. Bull. 67, 240 (2022)
work page 2022
-
[6]
S. Aaronson and S.-H. Hung, Certified randomness from quantum supremacy, Proceedings of the 55th Annual ACM Symposium on Theory of Computing , 933 (2023)
work page 2023
Show all 45 references
-
[7]
M. Liu, R. Shaydulin, P. Niroula, M. DeCross, S.-H. Hung, W. Y. Kon, E. Cervero-Mart´ ın, K. Chakraborty, O. Amer, S. Aaronson, et al. , Certified randomness us- ing a trapped-ion quantum processor, Nature 640, 343 (2025)
2025
-
[8]
A. Y. Kitaev, Quantum measurements and the abelian stabilizer problem (1995), arXiv:quant-ph/9511026
1995 arXiv
-
[9]
Preskill, Quantum Computing in the NISQ era and beyond, Quantum 2, 79 (2018)
J. Preskill, Quantum Computing in the NISQ era and beyond, Quantum 2, 79 (2018)
2018
-
[10]
Y. Kim, A. Eddins, S. Anand, K. X. Wei, E. Van Den Berg, S. Rosenblatt, H. Nayfeh, Y. Wu, M. Za- letel, K. Temme, et al., Evidence for the utility of quan- tum computing before fault tolerance, Nature 618, 500 (2023)
2023
-
[11]
Kanno, M
K. Kanno, M. Kohda, R. Imai, S. Koh, K. Mitarai, W. Mizukami, and Y. O. Nakagawa, Quantum-selected configuration interaction: Classical diagonalization of hamiltonians in subspaces selected by quantum com- puters (2023), arXiv:2302.11320
2023 arXiv
-
[12]
Robledo-Moreno, M
J. Robledo-Moreno, M. Motta, H. Haas, A. Javadi- Abhari, P. Jurcevic, W. Kirby, S. Martiel, K. Sharma, S. Sharma, T. Shirakawa, I. Sitdikov, R.-Y. Sun, K. J. Sung, M. Takita, M. C. Tran, et al. , Chemistry Beyond Exact Solutions on a Quantum-Centric Supercomputer (2024), arXiv...
2024 arXiv
-
[13]
Y. O. Nakagawa, M. Kamoshita, W. Mizukami, S. Sudo, and Y.-y. Ohnishi, ADAPT-QSCI: Adaptive Construc- tion of an Input State for Quantum-Selected Configura- tion Interaction, J. Chem. Theory Comput. 20, 10817 (2024)
2024
-
[14]
Kaliakin, A
D. Kaliakin, A. Shajan, J. R. Moreno, Z. Li, A. Mi- tra, M. Motta, C. Johnson, A. A. Saki, S. Das, I. Sit- dikov, et al. , Accurate quantum-centric simulations of supramolecular interactions (2024), arXiv:2410.09209
2024 arXiv
-
[15]
Barison, J
S. Barison, J. Robledo Moreno, and M. Motta, Quantum-centric computation of molecular excited states with extended sample-based quantum diagonal- ization, Quantum Sci. Technol. 10, 025034 (2025)
2025
-
[16]
Liepuoniute, K
I. Liepuoniute, K. D. Doney, J. Robledo-Moreno, J. A. Job, W. S. Friend, and G. O. Jones, Quantum- Centric Study of Methylene Singlet and Triplet States, arXiv:2411.04827
-
[17]
Shajan, D
A. Shajan, D. Kaliakin, A. Mitra, J. R. Moreno, Z. Li, M. Motta, C. Johnson, A. A. Saki, S. Das, I. Sit- dikov, et al. , Towards quantum-centric simulations of extended molecules: sample-based quantum diagonal- ization enhanced with density matrix embedding theory, arXiv:2411.09861
-
[18]
Sugisaki, S
K. Sugisaki, S. Kanno, T. Itoko, R. Sakuma, and N. Yamamoto, Hamiltonian simulation-based quantum- selected configuration interaction for large-scale elec- tronic structure calculations with a quantum computer, arXiv:2412.07218
-
[19]
Mikkelsen and Y
M. Mikkelsen and Y. O. Nakagawa, Quantum-selected configuration interaction with time-evolved state, arXiv:2412.13839
-
[20]
Reinholdt, K
P. Reinholdt, K. M. Ziems, E. R. Kjellgren, S. Cori- ani, S. Sauer, and J. Kongsted, Exposing a Fatal Flaw in Sample-based Quantum Diagonalization Methods, arXiv:2501.07231
-
[21]
J. Yu, J. R. Moreno, J. T. Iosue, L. Bertels, D. Claudino, B. Fuller, P. Groszkowski, T. S. Hum- ble, P. Jurcevic, W. Kirby, et al. , Quantum-Centric Algorithm for Sample-Based Krylov Diagonalization, arXiv:2501.09702
-
[22]
Kaliakin, A
D. Kaliakin, A. Shajan, F. Liang, and K. M. Merz Jr, Implicit solvent sample-based quantum diagonalization, arXiv:2502.10189
-
[23]
Yoshida, L
Y. Yoshida, L. Erhart, T. Murokoshi, R. Nak- agawa, C. Mori, T. Miyanaga, T. Mori, and W. Mizukami, Auxiliary-field quantum Monte Carlo method with quantum selected configuration interactio, arXiv:2502.21081
-
[24]
Danilov, J
D. Danilov, J. Robledo-Moreno, K. J. Sung, M. Motta, and J. Shee, Enhancing the accuracy and efficiency of sample-based quantum diagonalization with phaseless auxiliary-field quantum Monte Carlo, arXiv:2503.05967
-
[25]
M. A. Barroca, T. Gujarati, V. Sharma, R. N. B. Fer- reira, Y.-H. Na, M. Giammona, A. Mezzacapo, B. Wun- sch, and M. Steiner, Surface reaction simulations for battery materials through sample-based quantum diag- onalization and local embedding, arXiv:2503.10923
-
[26]
Shirai, S.-Y
S. Shirai, S.-Y. Tseng, H. Iwakiri, T. Horiba, H. Hirai, and S. Koh, Enhancing accuracy of quantum-selected configuration interaction calculations using multiref- erence perturbation theory: Application to aromatic molecufles, arXiv:2503.22221
-
[27]
Ohgoe, H
T. Ohgoe, H. Iwakiri, K. Ichikawa, S. Koh, and M. Ko- hda, Quantum computation of a quasiparticle band structure with the quantum-selected configuration in- teraction, arXiv:2504.00309
-
[28]
Peruzzo, J
A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O’Brien, A variational eigenvalue solver on a photonic quantum processor, Nat. Commun. 5, 4213 (2014)
2014
-
[29]
Matsuzawa and Y
Y. Matsuzawa and Y. Kurashige, Jastrow-type decom- position in quantum chemistry for low-depth quantum circuits, J. Chem. Theory Comput. 16, 944 (2020)
2020
-
[30]
Anand, P
A. Anand, P. Schleich, S. Alperin-Lea, P. W. K. Jensen, S. Sim, M. D´ ıaz-Tinoco, J. S. Kottmann, M. Degroote, A. F. Izmaylov, and A. Aspuru-Guzik, A quantum com- puting view on unitary coupled cluster theory, Chem. Soc. Rev. 51, 1659 (2022)
2022
-
[32]
M. J. Bremner, R. Jozsa, and D. J. Shepherd, Clas- sical simulation of commuting quantum computations implies collapse of the polynomial hierarchy, Proc. R. Soc. A 467, 459–472 (2010)
2010
-
[33]
Farhi and A
E. Farhi and A. W. Harrow, Quantum supremacy through the quantum approximate optimization algo- rithm (2016), arXiv:1602.07674
2016 arXiv
-
[34]
L. G. Valiant, Quantum circuits that can be simulated classically in polynomial time, SIAM J. Comput. 31, 1229 (2002)
2002
-
[35]
Jozsa and A
R. Jozsa and A. Miyake, Matchgates and classical sim- ulation of quantum circuits, Proc. R. Soc. A 464, 3089–3106 (2008)
2008
-
[36]
Oszmaniec, N
M. Oszmaniec, N. Dangniam, M. E. Morales, and Z. Zimbor´ as, Fermion sampling: A robust quantum computational advantage scheme using fermionic linear optics and magic input states, PRX Quantum 3, 020328 (2022)
2022
-
[37]
J. M. Arrazola, O. Di Matteo, N. Quesada, S. Jahangiri, A. Delgado, and N. Killoran, Universal quantum circuits for quantum chemistry, Quantum 6, 742 (2022)
2022
-
[38]
Arora and B
S. Arora and B. Barak, Computational complexity: a modern approach (Cambridge University Press, 2009)
2009
-
[39]
Neuscamman, Communication: A jastrow factor cou- pled cluster theory for weak and strong electron corre- lation, J
E. Neuscamman, Communication: A jastrow factor cou- pled cluster theory for weak and strong electron corre- lation, J. Chem. Phys. 139, 181101 (2013)
2013
-
[40]
J. Lee, W. J. Huggins, M. Head-Gordon, and K. B. Whaley, Generalized unitary coupled cluster wave func- tions for quantum computation, J. Chem. Theory Com- put. 15, 311 (2018)
2018
-
[41]
Wecker, M
D. Wecker, M. B. Hastings, N. Wiebe, B. K. Clark, C. Nayak, and M. Troyer, Solving strongly correlated electron models on a quantum computer, Phys. Rev. A 92, 062318 (2015)
2015
-
[42]
I. D. Kivlichan, J. McClean, N. Wiebe, C. Gidney, A. Aspuru-Guzik, G. K.-L. Chan, and R. Babbush, Quantum simulation of electronic structure with linear depth and connectivity, Phys. Rev. Lett. 120, 110501 (2018)
2018
-
[44]
Leimkuhler and K
O. Leimkuhler and K. B. Whaley, Exponential quan- tum speedups in quantum chemistry with linear depth, arXiv:2503.21041
-
[45]
Hafid, M
A. Hafid, M. Kohda, K. Tsubouchi, N. Yoshioka, and H. Iwakiri, Hardness of classically sampling quantum chemistry circuits, Poster presentation at 28th An- nual Quantum Information Processing Conference (QIP 2025), Raleigh, North Carolina, 2025
2025
Reviewed August 16, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.