{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T01:21:32Z","timestamp":1760059292706,"version":"build-2065373602"},"reference-count":19,"publisher":"MDPI AG","issue":"6","license":[{"start":{"date-parts":[[2025,6,2]],"date-time":"2025-06-02T00:00:00Z","timestamp":1748822400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Swedish Research Council","award":["2023-05031"],"award-info":[{"award-number":["2023-05031"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>Recursive Fourier Sampling (RFS) was one of the earliest problems to demonstrate a quantum advantage, and is known to lie outside the Merlin\u2013Arthur complexity class. This work contains a new description of quantum algorithms in phase space terminology, demonstrating its use in RFS, and how and why this gives a better understanding of the quantum advantage in RFS. Most importantly, describing the computational process of quantum computation in phase space terminology gives a much better understanding of why uncomputation is necessary when solving RFS: the advantage is present only when phase coordinate garbage is uncomputed. This is the underlying reason for the limitations of the quantum advantage.<\/jats:p>","DOI":"10.3390\/e27060596","type":"journal-article","created":{"date-parts":[[2025,6,2]],"date-time":"2025-06-02T11:40:32Z","timestamp":1748864432000},"page":"596","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Phase Coordinate Uncomputation in Quantum Recursive Fourier Sampling"],"prefix":"10.3390","volume":"27","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7312-8158","authenticated-orcid":false,"given":"Christoffer","family":"Hindlycke","sequence":"first","affiliation":[{"name":"Department of Electrical Engineering, Link\u00f6ping University, 581 83 Link\u00f6ping, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5888-1291","authenticated-orcid":false,"given":"Niklas","family":"Johansson","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering, Link\u00f6ping University, 581 83 Link\u00f6ping, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1082-8325","authenticated-orcid":false,"given":"Jan-\u00c5ke","family":"Larsson","sequence":"additional","affiliation":[{"name":"Department of Electrical Engineering, Link\u00f6ping University, 581 83 Link\u00f6ping, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2025,6,2]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Bernstein, E., and Vazirani, U. (1993, January 16\u201318). Quantum complexity theory. Proceedings of the 25th Annual ACM Symposium on Theory of Computing (STOC \u201993), San Diego, CA, USA.","DOI":"10.1145\/167088.167097"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1411","DOI":"10.1137\/S0097539796300921","article-title":"Quantum Complexity Theory","volume":"26","author":"Bernstein","year":"1997","journal-title":"SIAM J. Comput."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1090\/psapm\/058\/1922899","article-title":"A Survey of Quantum Complexity Theory","volume":"Volume 58","author":"Vazirani","year":"2002","journal-title":"Proceedings of Symposia in Applied Mathematics"},{"key":"ref_4","unstructured":"Johnson, B.E. (2008). Upper and Lower Bounds for Recursive Fourier Sampling. [Ph.D. Thesis, University California Berkeley]."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1098\/rspa.1998.0164","article-title":"Quantum algorithms revisited","volume":"454","author":"Cleve","year":"1998","journal-title":"Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci."},{"key":"ref_6","unstructured":"Nielsen, M.A., and Chuang, I.L. (2010). Quantum Computation and Quantum Information, Cambridge University Press. Volume 10th Anniversary Edition."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Johansson, N., and Larsson, J.\u00c5. (2019). Quantum Simulation Logic, Oracles, and the Quantum Advantage. Entropy, 21.","DOI":"10.3390\/e21080800"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Wootters, W.K. (2003). Picturing Qubits in Phase Space. arXiv.","DOI":"10.1147\/rd.481.0099"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"052328","DOI":"10.1103\/PhysRevA.70.052328","article-title":"Improved Simulation of Stabilizer Circuits","volume":"70","author":"Aaronson","year":"2004","journal-title":"Phys. Rev. A"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"130401","DOI":"10.1103\/PhysRevLett.129.130401","article-title":"Efficient Contextual Ontological Model of n-Qubit Stabilizer Quantum Mechanics","volume":"129","author":"Hindlycke","year":"2022","journal-title":"Phys. Rev. Lett."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"032110","DOI":"10.1103\/PhysRevA.75.032110","article-title":"Evidence for the Epistemic View of Quantum States: A Toy Theory","volume":"75","author":"Spekkens","year":"2007","journal-title":"Phys. Rev. A"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1103\/PhysRevA.57.127","article-title":"Theory of Fault-Tolerant Quantum Computation","volume":"57","author":"Gottesman","year":"1998","journal-title":"Phys. Rev. A"},{"key":"ref_13","unstructured":"Shor, P. (1996, January 14\u201316). Fault-Tolerant Quantum Computation. Proceedings of the 37th Annual Symposium on Foundations of Computer Science, Burlington, VT, USA."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1103\/PhysRevLett.78.405","article-title":"Quantum Error Correction and Orthogonal Geometry","volume":"78","author":"Calderbank","year":"1997","journal-title":"Phys. Rev. Lett."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1126\/science.aar3106","article-title":"Quantum Advantage with Shallow Circuits","volume":"362","author":"Bravyi","year":"2018","journal-title":"Science"},{"key":"ref_16","first-page":"165","article-title":"Quantum Lower Bound for Recursive Fourier Sampling","volume":"3","author":"Aaronson","year":"2003","journal-title":"Quantum Inf. Comput."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.4086\/cjtcs.2012.006","article-title":"Interactive proofs with efficient quantum prover for recursive Fourier sampling","volume":"18","author":"McKague","year":"2012","journal-title":"Chic. J. Theor. Comput. Sci."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Grover, L.K. (1996, January 22\u201324). A Fast Quantum Mechanical Algorithm for Database Search. Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, Philadelphia, PA, USA. STOC \u201996.","DOI":"10.1145\/237814.237866"},{"key":"ref_19","unstructured":"Shor, P. (1994, January 20\u201322). Algorithms for Quantum Computation: Discrete Logarithms and Factoring. Proceedings of the 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM, USA."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/27\/6\/596\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T17:46:17Z","timestamp":1760031977000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/27\/6\/596"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,2]]},"references-count":19,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2025,6]]}},"alternative-id":["e27060596"],"URL":"https:\/\/doi.org\/10.3390\/e27060596","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2025,6,2]]}}}