{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T00:42:36Z","timestamp":1762044156846,"version":"3.37.3"},"reference-count":51,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2024,9,11]],"date-time":"2024-09-11T00:00:00Z","timestamp":1726012800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["EP\/SO23607\/1"],"award-info":[{"award-number":["EP\/SO23607\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Royal Society University Research Fellowship","award":["UHQT\/NFQI"],"award-info":[{"award-number":["UHQT\/NFQI"]}]},{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["EP\/R043957\/1"],"award-info":[{"award-number":["EP\/R043957\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["EP\/S005021\/1"],"award-info":[{"award-number":["EP\/S005021\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["EP\/T001062\/1"],"award-info":[{"award-number":["EP\/T001062\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>We consider models of quantum computation that involve operations performed on some fixed resourceful quantum state. Examples that fit this paradigm include magic state injection and measurement-based approaches. We introduce a framework that incorporates both of these cases and focus on the role of coherence (or superposition) in this context, as exemplified through the Hadamard gate. We prove that given access to incoherent unitaries (those that are unable to generate superposition from computational basis states, e.g. CNOT, diagonal gates), classical control, computational basis measurements, and any resourceful ancillary state (of arbitrary dimension), it is not possible to implement any coherent unitary (e.g. Hadamard) exactly with non-zero probability. We also consider the approximate case by providing lower bounds for the induced trace distance between the above operations and <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>n<\/mml:mi><\/mml:math> Hadamard gates. To demonstrate the stability of this result, this is then extended to a similar no-go result for the case of using <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>k<\/mml:mi><\/mml:math> Hadamard gates to exactly implement <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>n<\/mml:mi><mml:mo>&amp;#x003E;<\/mml:mo><mml:mi>k<\/mml:mi><\/mml:math> Hadamard gates.<\/jats:p>","DOI":"10.22331\/q-2024-09-11-1470","type":"journal-article","created":{"date-parts":[[2024,9,11]],"date-time":"2024-09-11T14:24:51Z","timestamp":1726064691000},"page":"1470","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":4,"title":["The Hadamard gate cannot be replaced by a resource state in universal quantum computation"],"prefix":"10.22331","volume":"8","author":[{"given":"Benjamin D. M.","family":"Jones","sequence":"first","affiliation":[{"name":"H. H. Wills Physics Laboratory, University of Bristol, Bristol, BS8 1TL, UK."},{"name":"School of Mathematics, University of Bristol, Fry Building, Woodland Road, Bristol, BS8 1UG, UK."},{"name":"Quantum Engineering Centre for Doctoral Training, University of Bristol, Bristol, BS8 1FD UK."}]},{"given":"Noah","family":"Linden","sequence":"additional","affiliation":[{"name":"School of Mathematics, University of Bristol, Fry Building, Woodland Road, Bristol, BS8 1UG, UK."}]},{"given":"Paul","family":"Skrzypczyk","sequence":"additional","affiliation":[{"name":"H. H. Wills Physics Laboratory, University of Bristol, Bristol, BS8 1TL, UK."},{"name":"CIFAR Azrieli Global Scholars Program, CIFAR, Toronto Canada."}]}],"member":"9598","published-online":{"date-parts":[[2024,9,11]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Ryszard Horodecki, Pawe\u0142 Horodecki, Micha\u0142 Horodecki, and Karol Horodecki. Quantum entanglement. Reviews of Modern Physics, 81 (2): 865, 2009. 10.1103\/RevModPhys.81.865.","DOI":"10.1103\/RevModPhys.81.865"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Otfried G\u00fchne, Erkka Haapasalo, Tristan Kraft, Juha-Pekka Pellonp\u00e4\u00e4, and Roope Uola. Colloquium: Incompatible measurements in quantum information science. Reviews of Modern Physics, 95: 011003, Feb 2023. 10.1103\/RevModPhys.95.011003.","DOI":"10.1103\/RevModPhys.95.011003"},{"key":"2","doi-asserted-by":"crossref","unstructured":"Michael A Nielsen and Isaac Chuang. Quantum computation and quantum information, 2002.","DOI":"10.1119\/1.1463744"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Richard Jozsa. An introduction to measurement based quantum computation. NATO Science Series, III: Computer and Systems Sciences. Quantum Information Processing-From Theory to Experiment, 199: 137\u2013158, 2006. 10.48550\/arXiv.quant-ph\/0508124.","DOI":"10.48550\/arXiv.quant-ph\/0508124"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Earl T Campbell, Barbara M Terhal, and Christophe Vuillot. Roads towards fault-tolerant universal quantum computation. Nature, 549 (7671): 172\u2013179, 2017. 10.1038\/nature23460.","DOI":"10.1038\/nature23460"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Tameem Albash and Daniel A Lidar. Adiabatic quantum computation. Reviews of Modern Physics, 90 (1): 015002, 2018. 10.1103\/RevModPhys.90.015002.","DOI":"10.1103\/RevModPhys.90.015002"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Samuel L Braunstein and Peter Van Loock. Quantum information with continuous variables. Reviews of Modern Physics, 77 (2): 513, 2005. 10.1103\/RevModPhys.77.513.","DOI":"10.1103\/RevModPhys.77.513"},{"key":"7","doi-asserted-by":"publisher","unstructured":"M Van den Nest, W D\u00fcr, A Miyake, and HJ Briegel. Fundamentals of universality in one-way quantum computation. New Journal of Physics, 9 (6): 204, 2007a. 10.1088\/1367-2630\/9\/6\/204.","DOI":"10.1088\/1367-2630\/9\/6\/204"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Yuki Takeuchi, Tomoyuki Morimae, and Masahito Hayashi. Quantum computational universality of hypergraph states with pauli-x and z basis measurements. Scientific reports, 9 (1): 1\u201314, 2019. 10.1038\/s41598-019-49968-3.","DOI":"10.1038\/s41598-019-49968-3"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Eric Chitambar and Gilad Gour. Quantum resource theories. Reviews of Modern Physics, 91 (2): 025001, 2019. 10.1103\/RevModPhys.91.025001.","DOI":"10.1103\/RevModPhys.91.025001"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Alexander Streltsov, Gerardo Adesso, and Martin B Plenio. Colloquium: Quantum coherence as a resource. Reviews of Modern Physics, 89 (4): 041003, 2017. 10.1103\/RevModPhys.89.041003.","DOI":"10.1103\/RevModPhys.89.041003"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Khaled Ben Dana, Mar\u00eda Garc\u00eda D\u00edaz, Mohamed Mejatty, and Andreas Winter. Resource theory of coherence: Beyond states. Physical Review A, 95 (6): 062327, 2017. 10.1103\/PhysRevA.95.062327.","DOI":"10.1103\/PhysRevA.95.062327"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Daniel Gottesman. Stabilizer codes and quantum error correction. California Institute of Technology, 1997. 10.48550\/arXiv.quant-ph\/9705052.","DOI":"10.48550\/arXiv.quant-ph\/9705052"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Physical Review A, 70 (5): 052328, 2004. 10.1103\/PhysRevA.70.052328.","DOI":"10.1103\/PhysRevA.70.052328"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Richard Jozsa and Marten Van Den Nest. Classical Simulation Complexity of Extended Clifford Circuits. Quantum Info. Comput., 14: 633\u2013648, may 2014. ISSN 1533-7146. 10.26421\/QIC14.7-8-7.","DOI":"10.26421\/QIC14.7-8-7"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Martin Hebenstreit, Richard Jozsa, Barbara Kraus, Sergii Strelchuk, and Mithuna Yoganathan. All pure fermionic non-Gaussian states are magic states for matchgate computations. Physical Review Letters, 123 (8): 080503, 2019. 10.1103\/PhysRevLett.123.080503.","DOI":"10.1103\/PhysRevLett.123.080503"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Martin Hebenstreit, Richard Jozsa, Barbara Kraus, and Sergii Strelchuk. Computational power of matchgates with supplementary resources. Physical Review A, 102 (5): 052604, 2020. 10.1103\/PhysRevA.102.052604.","DOI":"10.1103\/PhysRevA.102.052604"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Richard Jozsa and Akimasa Miyake. Matchgates and classical simulation of quantum circuits. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 464 (2100): 3089\u20133106, 2008. 10.1098\/rspa.2008.0189.","DOI":"10.1098\/rspa.2008.0189"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Barbara M Terhal and David P DiVincenzo. Classical simulation of noninteracting-fermion quantum circuits. Physical Review A, 65 (3): 032325, 2002. 10.1103\/PhysRevA.65.032325.","DOI":"10.1103\/PhysRevA.65.032325"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Robert Raussendorf and Hans J Briegel. A one-way quantum computer. Physical Review Letters, 86 (22): 5188, 2001. 10.1103\/PhysRevLett.86.5188.","DOI":"10.1103\/PhysRevLett.86.5188"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Michael A Nielsen. Cluster-state quantum computation. Reports on Mathematical Physics, 57 (1): 147\u2013161, 2006. 10.1016\/S0034-4877(06)80014-5.","DOI":"10.1016\/S0034-4877(06)80014-5"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Daniel Gottesman and Isaac L Chuang. Quantum teleportation is a universal computational primitive. arXiv preprint quant-ph\/9908010, 1999. 10.1038\/46503.","DOI":"10.1038\/46503"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Eric Chitambar and Gilad Gour. Critical Examination of Incoherent Operations and a Physically Consistent Resource Theory of Quantum Coherence. Physical Review Letters, 117: 030401, Jul 2016a. 10.1103\/PhysRevLett.117.030401.","DOI":"10.1103\/PhysRevLett.117.030401"},{"key":"23","doi-asserted-by":"publisher","unstructured":"Maarten Van den Nest, Wolfgang D\u00fcr, Guifr\u00e9 Vidal, and Hans J Briegel. Classical simulation versus universality in measurement-based quantum computation. Physical Review A, 75 (1): 012337, 2007b. 10.1103\/PhysRevA.75.012337.","DOI":"10.1103\/PhysRevA.75.012337"},{"key":"24","doi-asserted-by":"publisher","unstructured":"M Nest. Classical simulation of quantum computation, the Gottesman-Knill theorem, and slightly beyond. arXiv preprint arXiv:0811.0898, 2008. 10.26421\/QIC10.3-4-6.","DOI":"10.26421\/QIC10.3-4-6"},{"key":"25","doi-asserted-by":"publisher","unstructured":"Xiaosi Xu, Simon Benjamin, Jinzhao Sun, Xiao Yuan, and Pan Zhang. A Herculean task: Classical simulation of quantum computers. arXiv preprint arXiv:2302.08880, 2023. 10.48550\/arXiv.2302.08880.","DOI":"10.48550\/arXiv.2302.08880"},{"key":"26","doi-asserted-by":"publisher","unstructured":"Caterina E Mora, Marco Piani, Akimasa Miyake, Maarten Van den Nest, Wolfgang D\u00fcr, and Hans J Briegel. Universal resources for approximate and stochastic measurement-based quantum computation. Physical Review A, 81 (4): 042315, 2010. 10.1103\/PhysRevA.81.042315.","DOI":"10.1103\/PhysRevA.81.042315"},{"key":"27","doi-asserted-by":"publisher","unstructured":"Aram W Harrow and Ashley Montanaro. Quantum computational supremacy. Nature, 549 (7671): 203\u2013209, 2017. 10.1038\/nature23458.","DOI":"10.1038\/nature23458"},{"key":"28","doi-asserted-by":"publisher","unstructured":"Luke E Heyfron and Earl T Campbell. An efficient quantum compiler that reduces t count. Quantum Science and Technology, 4 (1): 015004, 2018. 10.1088\/2058-9565\/aad604.","DOI":"10.1088\/2058-9565\/aad604"},{"key":"29","doi-asserted-by":"publisher","unstructured":"J. Niel de Beaudrap, Xiaoning Bian, and Quanlong Wang. Fast and Effective Techniques for T-Count Reduction via Spider Nest Identities. In Theory of Quantum Computation, Communication, and Cryptography, 2020. 10.4230\/LIPIcs.TQC.2020.11.","DOI":"10.4230\/LIPIcs.TQC.2020.11"},{"key":"30","doi-asserted-by":"publisher","unstructured":"Michael J Bremner, Richard Jozsa, and Dan J Shepherd. Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 467 (2126): 459\u2013472, 2011. 10.1098\/rspa.2010.0301.","DOI":"10.1098\/rspa.2010.0301"},{"key":"31","doi-asserted-by":"publisher","unstructured":"Matteo Rossi, Marcus Huber, Dagmar Bru\u00df, and Chiara Macchiavello. Quantum hypergraph states. New Journal of Physics, 15 (11): 113022, 2013. 10.1088\/1367-2630\/15\/11\/113022.","DOI":"10.1088\/1367-2630\/15\/11\/113022"},{"key":"32","doi-asserted-by":"publisher","unstructured":"Yaoyun Shi. Both Toffoli and Controlled-NOT Need Little Help to Do Universal Quantum Computing. 3 (1): 84\u201392, 2003. ISSN 1533-7146. 10.5555\/2011508.2011515.","DOI":"10.5555\/2011508.2011515"},{"key":"33","doi-asserted-by":"publisher","unstructured":"Dorit Aharonov. A simple proof that Toffoli and Hadamard are quantum universal. arXiv preprint quant-ph\/0301040, 2003. 10.48550\/arXiv.quant-ph\/0301040.","DOI":"10.48550\/arXiv.quant-ph\/0301040"},{"key":"34","doi-asserted-by":"publisher","unstructured":"Sergey Bravyi and Alexei Kitaev. Universal quantum computation with ideal clifford gates and noisy ancillas. Physical Review A, 71 (2): 022316, 2005. 10.1103\/PhysRevA.71.022316.","DOI":"10.1103\/PhysRevA.71.022316"},{"key":"35","doi-asserted-by":"publisher","unstructured":"Hans J Briegel, David E Browne, Wolfgang D\u00fcr, Robert Raussendorf, and Maarten Van den Nest. Measurement-based quantum computation. Nature Physics, 5 (1): 19\u201326, 2009. 10.1038\/nphys1157.","DOI":"10.1038\/nphys1157"},{"key":"36","doi-asserted-by":"publisher","unstructured":"Sergey Bravyi, Graeme Smith, and John A Smolin. Trading classical and quantum computational resources. Physical Review X, 6 (2): 021043, 2016. 10.1103\/PhysRevX.6.021043.","DOI":"10.1103\/PhysRevX.6.021043"},{"key":"37","doi-asserted-by":"publisher","unstructured":"Adriano Barenco, Charles H Bennett, Richard Cleve, David P DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A Smolin, and Harald Weinfurter. Elementary gates for quantum computation. Physical review A, 52 (5): 3457, 1995. 10.1103\/PhysRevA.52.3457.","DOI":"10.1103\/PhysRevA.52.3457"},{"key":"38","doi-asserted-by":"publisher","unstructured":"Nathan Killoran, Frank ES Steinhoff, and Martin B Plenio. Converting nonclassicality into entanglement. Physical Review Letters, 116 (8): 080402, 2016. 10.1103\/PhysRevLett.116.080402.","DOI":"10.1103\/PhysRevLett.116.080402"},{"key":"39","doi-asserted-by":"publisher","unstructured":"Mark M Wilde. Quantum information theory. Cambridge University Press, 2013. 10.1017\/9781316809976.","DOI":"10.1017\/9781316809976"},{"key":"40","doi-asserted-by":"publisher","unstructured":"John Watrous. The Theory of Quantum Information. Cambridge University Press, 2018. 10.1017\/9781316848142.","DOI":"10.1017\/9781316848142"},{"key":"41","doi-asserted-by":"publisher","unstructured":"Patrick Hayden, Debbie Leung, Peter W Shor, and Andreas Winter. Randomizing quantum states: Constructions and applications. Communications in Mathematical Physics, 250: 371\u2013391, 2004. 10.1007\/s00220-004-1087-6.","DOI":"10.1007\/s00220-004-1087-6"},{"key":"42","doi-asserted-by":"publisher","unstructured":"Ashley Montanaro. Quantum states cannot be transmitted efficiently classically. Quantum, 3: 154, 2019. 10.22331\/q-2019-06-28-154.","DOI":"10.22331\/q-2019-06-28-154"},{"key":"43","doi-asserted-by":"publisher","unstructured":"Teiko Heinosaari, Takayuki Miyadera, and M\u00e1rio Ziman. An invitation to quantum incompatibility. Journal of Physics A: Mathematical and Theoretical, 49 (12): 123001, 2016. 10.1088\/1751-8113\/49\/12\/123001.","DOI":"10.1088\/1751-8113\/49\/12\/123001"},{"key":"44","doi-asserted-by":"publisher","unstructured":"Mar\u00eda Garc\u00eda D\u00edaz, Kun Fang, Xin Wang, Matteo Rosati, Michalis Skotiniotis, John Calsamiglia, and Andreas Winter. Using and reusing coherence to realize quantum processes. Quantum, 2: 100, 2018. 10.22331\/q-2018-10-19-100.","DOI":"10.22331\/q-2018-10-19-100"},{"key":"45","doi-asserted-by":"publisher","unstructured":"Ludovico Lami, Bartosz Regula, and Gerardo Adesso. Generic bound coherence under strictly incoherent operations. Physical review letters, 122 (15): 150402, 2019. 10.1103\/PhysRevLett.122.150402.","DOI":"10.1103\/PhysRevLett.122.150402"},{"key":"46","doi-asserted-by":"publisher","unstructured":"Ryuji Takagi and Hiroyasu Tajima. Universal limitations on implementing resourceful unitary evolutions. Physical Review A, 101 (2): 022315, 2020. 10.1103\/PhysRevA.101.022315.","DOI":"10.1103\/PhysRevA.101.022315"},{"key":"47","doi-asserted-by":"publisher","unstructured":"Giulio Chiribella, Yuxiang Yang, and Renato Renner. Fundamental energy requirement of reversible quantum operations. Physical Review X, 11 (2): 021014, 2021. 10.1103\/PhysRevX.11.021014.","DOI":"10.1103\/PhysRevX.11.021014"},{"key":"48","doi-asserted-by":"publisher","unstructured":"Mark Howard and Earl Campbell. Application of a resource theory for magic states to fault-tolerant quantum computing. Physical Review Letters, 118 (9): 090501, 2017. 10.1103\/PhysRevLett.118.090501.","DOI":"10.1103\/PhysRevLett.118.090501"},{"key":"49","doi-asserted-by":"publisher","unstructured":"James R Seddon and Earl T Campbell. Quantifying magic for multi-qubit operations. Proceedings of the Royal Society A, 475 (2227): 20190251, 2019. 10.1098\/rspa.2019.0251.","DOI":"10.1098\/rspa.2019.0251"},{"key":"50","doi-asserted-by":"publisher","unstructured":"Eric Chitambar and Gilad Gour. Comparison of incoherent operations and measures of coherence. Physical Review A, 94 (5): 052336, 2016b. 10.1103\/PhysRevA.94.052336.","DOI":"10.1103\/PhysRevA.94.052336"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-09-11-1470\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,9,12]],"date-time":"2024-09-12T12:46:30Z","timestamp":1726145190000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-09-11-1470\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,11]]},"references-count":51,"URL":"https:\/\/doi.org\/10.22331\/q-2024-09-11-1470","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"type":"electronic","value":"2521-327X"}],"subject":[],"published":{"date-parts":[[2024,9,11]]},"article-number":"1470"}}