Polynomial-Time Classical Simulation of Hidden Shift Circuits via Confluent Rewriting of Symbolic Sums

Matthew Amy; Lucas Shigeru Stinchcombe

doi:10.22331/q-2025-12-02-1926

Polynomial-Time Classical Simulation of Hidden Shift Circuits via Confluent Rewriting of Symbolic Sums

Matthew Amy and Lucas Shigeru Stinchcombe

School of Computing Science, Simon Fraser University, Canada

Published:	2025-12-02, volume 9, page 1926
Editor:	Miriam Backens
Eprint:	arXiv:2408.02778v2
Doi:	https://doi.org/10.22331/q-2025-12-02-1926
Citation:	Quantum 9, 1926 (2025).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

Implementations of Roetteler's shifted bent function algorithm have in recent years been used to test and benchmark both classical simulation algorithms and quantum hardware. These circuits have many favorable properties, including a tunable amount of non-Clifford resources and a deterministic output, and moreover do not belong to any class of quantum circuits that is known to be efficiently simulable. We show that this family of circuits can in fact be simulated in polynomial time via symbolic path integrals. We do so by endowing symbolic sums with a confluent rewriting system and show that this rewriting system suffices to reduce the circuit's path integral to the hidden shift in polynomial time. We hence resolve an open conjecture about the efficient simulability of this class of circuits.

Featured image: Confluent rewriting of path sum interpretations ensures that all simplifications of a circuit yield the same final expression, modulo simple equivalence.

Popular summary

Classical simulators of quantum circuits are algorithms that run on traditional computers to mimic the behavior of quantum computers. Efficient classical simulators exist for circuits over certain non-universal gate sets, or with other restrictions such as depth, but general-purpose simulation methods remain exponential-time on universal gate sets. In this work, we show that a family of deterministic circuits arising as instances of Roetteler's hidden shift algorithm, which have been used to benchmark general-purpose simulators, is in fact polynomial-time simulable using general-purpose simulation methods. This family of circuits notably does not belong to any previously known class of efficiently simulable quantum circuits, though its efficient simulability has been previously conjectured. Hence, we answer this conjecture in the affirmative. We demonstrate this by giving a confluent rewriting system for simplifying a circuit's path integral inside a general path integral-based simulation, and proving that this simulates the hidden shift algorithm in polynomial time.

► BibTeX data

@article{Amy2025polynomialtime,
  doi = {10.22331/q-2025-12-02-1926},
  url = {https://doi.org/10.22331/q-2025-12-02-1926},
  title = {Polynomial-{T}ime {C}lassical {S}imulation of {H}idden {S}hift {C}ircuits via {C}onfluent {R}ewriting of {S}ymbolic {S}ums},
  author = {Amy, Matthew and Stinchcombe, Lucas Shigeru},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {9},
  pages = {1926},
  month = dec,
  year = {2025}
}

► References

[1] S. Aaronson and D. Gottesman. Improved simulation of stabilizer circuits. Physical Review A, 70(5), Nov. 2004. Publisher: American Physical Society (APS). https://doi.org/10.1103/PhysRevA.70.052328.
https://doi.org/10.1103/PhysRevA.70.052328

[2] D. Aharonov. A Simple Proof that Toffoli and Hadamard are Quantum Universal, 2003. _eprint: quant-ph/0301040. https://doi.org/10.48550/arXiv.quant-ph/0301040.
https://doi.org/10.48550/arXiv.quant-ph/0301040
arXiv:quant-ph/0301040

[3] P. Aluffi. Algebra: Chapter 0. Graduate studies in mathematics ; 104. American Mathematical Society, Providence, R.I, 2009. Publication Title: Algebra: Chapter 0.

[4] M. Amy. Towards Large-scale Functional Verification of Universal Quantum Circuits. In P. Selinger and G. Chiribella, editors, Proceedings 15th International Conference on Quantum Physics and Logic, QPL 2018, Halifax, Canada, 3-7th June 2018, volume 287 of EPTCS, pages 1–21, 2018. https://doi.org/10.4204/EPTCS.287.1.
https://doi.org/10.4204/EPTCS.287.1

[5] M. Amy. Complete Equational Theories for the Sum-Over-Paths with Unbalanced Amplitudes. In S. Mansfield, B. Valiron, and V. Zamdzhiev, editors, Proceedings of the Twentieth International Conference on Quantum Physics and Logic, QPL 2023, Paris, France, 17-21st July 2023, volume 384 of EPTCS, pages 127–141, 2023. https://doi.org/10.4204/EPTCS.384.8.
https://doi.org/10.4204/EPTCS.384.8

[6] M. Amy, O. Bennett-Gibbs, and N. J. Ross. Symbolic Synthesis of Clifford Circuits and Beyond. In S. Gogioso and M. Hoban, editors, Proceedings 19th International Conference on Quantum Physics and Logic, QPL 2022, Wolfson College, Oxford, UK, 27 June - 1 July 2022, volume 394 of EPTCS, pages 343–362, 2022. https://doi.org/10.4204/EPTCS.394.17.
https://doi.org/10.4204/EPTCS.394.17

[7] S. Bravyi, D. Browne, P. Calpin, E. Campbell, D. Gosset, and M. Howard. Simulation of quantum circuits by low-rank stabilizer decompositions. Quantum, 3:181, Sept. 2019. Publisher: Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften. https://doi.org/10.22331/q-2019-09-02-181.
https://doi.org/10.22331/q-2019-09-02-181

[8] S. Bravyi and D. Gosset. Improved Classical Simulation of Quantum Circuits Dominated by Clifford Gates. Physical Review Letters, 116(25), June 2016. Publisher: American Physical Society (APS). https://doi.org/10.1103/PhysRevLett.116.250501.
https://doi.org/10.1103/PhysRevLett.116.250501

[9] S. Bravyi, G. Smith, and J. A. Smolin. Trading Classical and Quantum Computational Resources. Phys. Rev. X, 6(2):021043, June 2016. Publisher: American Physical Society. https://doi.org/10.1103/PhysRevX.6.021043.
https://doi.org/10.1103/PhysRevX.6.021043

[10] C. Chareton, S. Bardin, F. Bobot, V. Perrelle, and B. Valiron. An Automated Deductive Verification Framework for Circuit-building Quantum Programs. In N. Yoshida, editor, Programming Languages and Systems, pages 148–177, Cham, 2021. Springer International Publishing. https://doi.org/10.1007/978-3-030-72019-3_6.
https://doi.org/10.1007/978-3-030-72019-3_6

[11] J. Codsi. Cutting Edge Graphical Stabilizer Decompositions for Classical Simulation of Quantum Circuits. Master's thesis, University of Oxford, 2022.

[12] B. Coecke and R. Duncan. Interacting Quantum Observables. In L. Aceto, I. Damgård, L. A. Goldberg, M. M. Halldórsson, A. Ingólfsdóttir, and I. Walukiewicz, editors, Automata, Languages and Programming, pages 298–310, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-540-70583-3_25.
https://doi.org/10.1007/978-3-540-70583-3_25

[13] A. W. Cross, E. Magesan, L. S. Bishop, J. A. Smolin, and J. M. Gambetta. Scalable randomised benchmarking of non-Clifford gates. npj Quantum Information, 2(1), Apr. 2016. Publisher: Springer Science and Business Media LLC. https://doi.org/10.1038/npjqi.2016.12.
https://doi.org/10.1038/npjqi.2016.12

[14] C. M. Dawson, H. L. Haselgrove, A. P. Hines, D. Mortimer, M. A. Nielsen, and T. J. Osborne. Quantum computing and polynomial equations over the finite field Z_2, 2004. _eprint: quant-ph/0408129. https://doi.org/10.26421/QIC5.2-2.
https://doi.org/10.26421/QIC5.2-2
arXiv:quant-ph/0408129

[15] J.-C. Faugère and L. Perret. Polynomial Equivalence Problems: Algorithmic and Theoretical Aspects. In S. Vaudenay, editor, Advances in Cryptology - EUROCRYPT 2006, pages 30–47, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg. https://doi.org/10.1007/11761679_3.
https://doi.org/10.1007/11761679_3

[16] K. Geddes, S. Czapor, and G. Labahn. Algorithms for computer algebra. Springer Science+Business Media New York, 1992. https://doi.org/10.1007/b102438.
https://doi.org/10.1007/b102438

[17] S. Hallgren and A. W. Harrow. Superpolynomial Speedups Based on Almost Any Quantum Circuit. In Lecture Notes in Computer Science, pages 782–795. Springer Berlin Heidelberg, 2008. ISSN: 1611-3349. https://doi.org/10.1007/978-3-540-70575-8_64.
https://doi.org/10.1007/978-3-540-70575-8_64

[18] G. Huet. Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems: Abstract Properties and Applications to Term Rewriting Systems. Journal of the ACM, 27(4):797–821, Oct. 1980. Place: New York, NY, USA Publisher: Association for Computing Machinery. https://doi.org/10.1145/322217.322230.
https://doi.org/10.1145/322217.322230

[19] C. Jones. Low-overhead constructions for the fault-tolerant Toffoli gate. Physical Review A, 87(2):022328, Feb. 2013. Publisher: American Physical Society. https://doi.org/10.1103/PhysRevA.87.022328.
https://doi.org/10.1103/PhysRevA.87.022328

[20] A. Kissinger and J. van de Wetering. Simulating quantum circuits with ZX-calculus reduced stabiliser decompositions. Quantum Science and Technology, 7(4):044001, July 2022. Publisher: IOP Publishing. https://doi.org/10.1088/2058-9565/ac5d20.
https://doi.org/10.1088/2058-9565/ac5d20

[21] A. Kissinger, J. van de Wetering, and R. Vilmart. Classical Simulation of Quantum Circuits with Partial and Graphical Stabiliser Decompositions. In F. Le Gall and T. Morimae, editors, 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022), volume 232 of Leibniz International Proceedings in Informatics (LIPIcs), pages 5:1–5:13, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.TQC.2022.5.
https://doi.org/10.4230/LIPIcs.TQC.2022.5

[22] M. Koch, R. Yeung, and Q. Wang. Contraction of zx diagrams with triangles via stabiliser decompositions. Physica Scripta, 99(10):105122, Sept. 2024. https://doi.org/10.1088/1402-4896/ad6fd8.
https://doi.org/10.1088/1402-4896/ad6fd8

[23] L. Kocia and M. Sarovar. Classical simulation of quantum circuits using fewer Gaussian eliminations. Phys. Rev. A, 103(2):022603, Feb. 2021. Publisher: American Physical Society. https://doi.org/10.1103/PhysRevA.103.022603.
https://doi.org/10.1103/PhysRevA.103.022603

[24] B. Lovitz and V. Steffan. New techniques for bounding stabilizer rank. Quantum, 6:692, Apr. 2022. Publisher: Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften. https://doi.org/10.22331/q-2022-04-20-692.
https://doi.org/10.22331/q-2022-04-20-692

[25] T. Lubinski, S. Johri, P. Varosy, J. Coleman, L. Zhao, J. Necaise, C. H. Baldwin, K. Mayer, and T. Proctor. Application-oriented performance benchmarks for quantum computing. IEEE Transactions on Quantum Engineering, 4:1–32, 2023. https://doi.org/10.1109/TQE.2023.3253761.
https://doi.org/10.1109/TQE.2023.3253761

[26] A. Montanaro. Quantum circuits and low-degree polynomials over ${{\mathbb{F}}_\mathsf{2}}$. Journal of Physics A: Mathematical and Theoretical, 50(8):084002, Jan. 2017. Publisher: IOP Publishing. https://doi.org/10.1088/1751-8121/aa565f.
https://doi.org/10.1088/1751-8121/aa565f

[27] X. Ni and M. van den Nest. Commuting quantum circuits: efficiently classical simulations versus hardness results. Quant. Inf. Comput., 13(1-2):0054–0072, 2013. https://doi.org/10.26421/QIC13.1-2-5.
https://doi.org/10.26421/QIC13.1-2-5

[28] M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, 2011. https://doi.org/10.1017/CBO9780511976667.
https://doi.org/10.1017/CBO9780511976667

[29] H. Pashayan, O. Reardon-Smith, K. Korzekwa, and S. D. Bartlett. Fast Estimation of Outcome Probabilities for Quantum Circuits. PRX Quantum, 3(2), June 2022. Publisher: American Physical Society (APS). https://doi.org/10.1103/PRXQuantum.3.020361.
https://doi.org/10.1103/PRXQuantum.3.020361

[30] J. Patarin. Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): Two New Families of Asymmetric Algorithms. In U. Maurer, editor, Advances in Cryptology — EUROCRYPT '96, pages 33–48, Berlin, Heidelberg, 1996. Springer Berlin Heidelberg. https://doi.org/10.1007/3-540-68339-9_4.
https://doi.org/10.1007/3-540-68339-9_4

[31] J. Patarin, L. Goubin, and N. Courtois. Improved algorithms for isomorphisms of polynomials. In K. Nyberg, editor, Advances in Cryptology — EUROCRYPT'98, pages 184–200, Berlin, Heidelberg, 1998. Springer Berlin Heidelberg. https://doi.org/10.1007/BFb0054126.
https://doi.org/10.1007/BFb0054126

[32] S. Peleg, A. Shpilka, and B. L. Volk. Lower Bounds on Stabilizer Rank. Quantum, 6:652, Feb. 2022. Publisher: Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften. https://doi.org/10.22331/q-2022-02-15-652.
https://doi.org/10.22331/q-2022-02-15-652

[33] F. C. R. Peres and E. F. Galvão. Quantum circuit compilation and hybrid computation using Pauli-based computation. Quantum, 7:1126, Oct. 2023. Publisher: Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften. https://doi.org/10.22331/q-2023-10-03-1126.
https://doi.org/10.22331/q-2023-10-03-1126

[34] L. Perret. A Fast Cryptanalysis of the Isomorphism of Polynomials with One Secret Problem. In R. Cramer, editor, Advances in Cryptology – EUROCRYPT 2005, pages 354–370, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg. https://doi.org/10.1007/11426639_21.
https://doi.org/10.1007/11426639_21

[35] H. Qassim, H. Pashayan, and D. Gosset. Improved upper bounds on the stabilizer rank of magic states. Quantum, 5:606, Dec. 2021. Publisher: Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften. https://doi.org/10.22331/q-2021-12-20-606.
https://doi.org/10.22331/q-2021-12-20-606

[36] M. Rötteler. Quantum algorithms for highly non-linear Boolean functions. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '10, pages 448–457, USA, 2010. Society for Industrial and Applied Mathematics. event-place: Austin, Texas. https://doi.org/10.1137/1.9781611973075.37.
https://doi.org/10.1137/1.9781611973075.37

[37] R. Vilmart. The Structure of Sum-Over-Paths, its Consequences, and Completeness for Clifford. In S. Kiefer and C. Tasson, editors, Foundations of Software Science and Computation Structures, pages 531–550, Cham, 2021. Springer International Publishing. https://doi.org/10.1007/978-3-030-71995-1_27.
https://doi.org/10.1007/978-3-030-71995-1_27

[38] R. Vilmart. Completeness of Sum-Over-Paths for Toffoli-Hadamard and the Dyadic Fragments of Quantum Computation. In CSL 2023 - 31st EACSL Annual Conference on Computer Science Logic, volume 252, pages 36:1–36:17, Warsaw, Poland, Feb. 2023. https://doi.org/10.4230/LIPIcs.CSL.2023.36.
https://doi.org/10.4230/LIPIcs.CSL.2023.36

[39] K. Wright, K. M. Beck, S. Debnath, J. M. Amini, Y. Nam, N. Grzesiak, J.-S. Chen, N. C. Pisenti, M. Chmielewski, C. Collins, K. M. Hudek, J. Mizrahi, J. D. Wong-Campos, S. Allen, J. Apisdorf, P. Solomon, M. Williams, A. M. Ducore, A. Blinov, S. M. Kreikemeier, V. Chaplin, M. Keesan, C. Monroe, and J. Kim. Benchmarking an 11-qubit quantum computer. Nature Communications, 10(1):5464, Nov. 2019. Publisher: Nature Publishing Group. https://doi.org/10.1038/s41467-019-13534-2.
https://doi.org/10.1038/s41467-019-13534-2

Cited by

[1] Azar C. Nakhl, Ben Harper, Maxwell West, Neil Dowling, Martin Sevior, Thomas Quella, and Muhammad Usman, "Stabilizer Tensor Networks with Magic State Injection", Physical Review Letters 134 19, 190602 (2025).

[2] Vsevolod I. Yashin, Vladimir V. Yatsulevich, Aleksey K. Fedorov, and Evgeniy O. Kiktenko, "Further improvements to stabilizer simulation theory: classical rewriting of CSS-preserving stabilizer circuits, quadratic form expansions of stabilizer operations, and framed hidden variable models", arXiv:2511.05478, (2025).

The above citations are from SAO/NASA ADS (last updated successfully 2026-08-09 13:51:39). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2026-08-09 13:51:29).

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.