The Hadamard gate cannot be replaced by a resource state in universal quantum computation

Benjamin D. M. Jones; Noah Linden; Paul Skrzypczyk

doi:10.22331/q-2024-09-11-1470

The Hadamard gate cannot be replaced by a resource state in universal quantum computation

Benjamin D. M. Jones^1,2,3, Noah Linden², and Paul Skrzypczyk^1,4

¹H. H. Wills Physics Laboratory, University of Bristol, Bristol, BS8 1TL, UK.
²School of Mathematics, University of Bristol, Fry Building, Woodland Road, Bristol, BS8 1UG, UK.
³Quantum Engineering Centre for Doctoral Training, University of Bristol, Bristol, BS8 1FD UK.
⁴CIFAR Azrieli Global Scholars Program, CIFAR, Toronto Canada.

Published:	2024-09-11, volume 8, page 1470
Eprint:	arXiv:2312.03515v6
Doi:	https://doi.org/10.22331/q-2024-09-11-1470
Citation:	Quantum 8, 1470 (2024).

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

Updated after initial publication: This publication was updated to version v6 after the initial publication. The authors left the following comment on the arXiv:

31 pages, 3 figures. Latest version includes an improved bound for Lemma 19, added references, data access statement, and amended grant code. Accepted in Quantum

Abstract

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 $n$ Hadamard gates. To demonstrate the stability of this result, this is then extended to a similar no-go result for the case of using $k$ Hadamard gates to exactly implement $n \gt k$ Hadamard gates.

Featured image: In the Clifford + $T$ gate set, one can replace all $T$ gates with $T$ states and perform magic state injection. One can also perform measurement based quantum computation if one removes $CNOT$ from this gate set, given access to a cluster state, computational basis measurements, and classical control. We ask whether or not one can replace the Hadamard gate with some supplementary state, and still be able to perform universal quanutum computation.

Popular summary

In quantum mechanics, three key phenomena are coherence (or superposition), entanglement, and magic (or non-stabiliserness). In quantum computation, it is known that the resources of entanglement and magic do not necessarily need to be present dynamically in the operations performed; they can be provided as supplementary states, as demonstrated respectively by measurement-based quantum computation and magic state injection. In our work, we study coherence in this context and argue that, unlike entanglement and magic, coherence must be present in the operations themselves to enable full quantum computational capabilities. To support this, we present several no-go theorems, drawing extensively from the literature on the resource theory of coherence. We also focus on the Clifford + $T$ gate set and the role of the Hadamard gate in this context.

► BibTeX data

@article{Jones2024hadamardgatecannot,
  doi = {10.22331/q-2024-09-11-1470},
  url = {https://doi.org/10.22331/q-2024-09-11-1470},
  title = {The {H}adamard gate cannot be replaced by a resource state in universal quantum computation},
  author = {Jones, Benjamin D. M. and Linden, Noah and Skrzypczyk, Paul},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {8},
  pages = {1470},
  month = sep,
  year = {2024}
}

► References

[1] Ryszard Horodecki, Paweł Horodecki, Michał Horodecki, and Karol Horodecki. Quantum entanglement. Reviews of Modern Physics, 81 (2): 865, 2009. 10.1103/RevModPhys.81.865.
https://doi.org/10.1103/RevModPhys.81.865

[2] Otfried Gühne, Erkka Haapasalo, Tristan Kraft, Juha-Pekka Pellonpää, and Roope Uola. Colloquium: Incompatible measurements in quantum information science. Reviews of Modern Physics, 95: 011003, Feb 2023. 10.1103/RevModPhys.95.011003.
https://doi.org/10.1103/RevModPhys.95.011003

[3] Michael A Nielsen and Isaac Chuang. Quantum computation and quantum information, 2002.

[4] 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–158, 2006. 10.48550/arXiv.quant-ph/0508124.
https://doi.org/10.48550/arXiv.quant-ph/0508124
arXiv:quant-ph/0508124

[5] Earl T Campbell, Barbara M Terhal, and Christophe Vuillot. Roads towards fault-tolerant universal quantum computation. Nature, 549 (7671): 172–179, 2017. 10.1038/nature23460.
https://doi.org/10.1038/nature23460

[6] Tameem Albash and Daniel A Lidar. Adiabatic quantum computation. Reviews of Modern Physics, 90 (1): 015002, 2018. 10.1103/RevModPhys.90.015002.
https://doi.org/10.1103/RevModPhys.90.015002

[7] 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.
https://doi.org/10.1103/RevModPhys.77.513

[8] M Van den Nest, W Dür, 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.
https://doi.org/10.1088/1367-2630/9/6/204

[9] 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–14, 2019. 10.1038/s41598-019-49968-3.
https://doi.org/10.1038/s41598-019-49968-3

[10] Eric Chitambar and Gilad Gour. Quantum resource theories. Reviews of Modern Physics, 91 (2): 025001, 2019. 10.1103/RevModPhys.91.025001.
https://doi.org/10.1103/RevModPhys.91.025001

[11] 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.
https://doi.org/10.1103/RevModPhys.89.041003

[12] Khaled Ben Dana, María García Díaz, Mohamed Mejatty, and Andreas Winter. Resource theory of coherence: Beyond states. Physical Review A, 95 (6): 062327, 2017. 10.1103/PhysRevA.95.062327.
https://doi.org/10.1103/PhysRevA.95.062327

[13] Daniel Gottesman. Stabilizer codes and quantum error correction. California Institute of Technology, 1997. 10.48550/arXiv.quant-ph/9705052.
https://doi.org/10.48550/arXiv.quant-ph/9705052
arXiv:quant-ph/9705052

[14] Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Physical Review A, 70 (5): 052328, 2004. 10.1103/PhysRevA.70.052328.
https://doi.org/10.1103/PhysRevA.70.052328

[15] Richard Jozsa and Marten Van Den Nest. Classical Simulation Complexity of Extended Clifford Circuits. Quantum Info. Comput., 14: 633–648, may 2014. ISSN 1533-7146. 10.26421/QIC14.7-8-7.
https://doi.org/10.26421/QIC14.7-8-7

[16] 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.
https://doi.org/10.1103/PhysRevLett.123.080503

[17] 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.
https://doi.org/10.1103/PhysRevA.102.052604

[18] 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–3106, 2008. 10.1098/rspa.2008.0189.
https://doi.org/10.1098/rspa.2008.0189

[19] 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.
https://doi.org/10.1103/PhysRevA.65.032325

[20] Robert Raussendorf and Hans J Briegel. A one-way quantum computer. Physical Review Letters, 86 (22): 5188, 2001. 10.1103/PhysRevLett.86.5188.
https://doi.org/10.1103/PhysRevLett.86.5188

[21] Michael A Nielsen. Cluster-state quantum computation. Reports on Mathematical Physics, 57 (1): 147–161, 2006. 10.1016/S0034-4877(06)80014-5.
https://doi.org/10.1016/S0034-4877(06)80014-5

[22] Daniel Gottesman and Isaac L Chuang. Quantum teleportation is a universal computational primitive. arXiv preprint quant-ph/9908010, 1999. 10.1038/46503.
https://doi.org/10.1038/46503
arXiv:quant-ph/9908010

[23] 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.
https://doi.org/10.1103/PhysRevLett.117.030401

[24] Maarten Van den Nest, Wolfgang Dür, Guifré 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.
https://doi.org/10.1103/PhysRevA.75.012337

[25] 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.
https://doi.org/10.26421/QIC10.3-4-6
arXiv:0811.0898

[26] 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.
https://doi.org/10.48550/arXiv.2302.08880
arXiv:2302.08880

[27] Caterina E Mora, Marco Piani, Akimasa Miyake, Maarten Van den Nest, Wolfgang Dür, 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.
https://doi.org/10.1103/PhysRevA.81.042315

[28] Aram W Harrow and Ashley Montanaro. Quantum computational supremacy. Nature, 549 (7671): 203–209, 2017. 10.1038/nature23458.
https://doi.org/10.1038/nature23458

[29] 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.
https://doi.org/10.1088/2058-9565/aad604

[30] 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.
https://doi.org/10.4230/LIPIcs.TQC.2020.11

[31] 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–472, 2011. 10.1098/rspa.2010.0301.
https://doi.org/10.1098/rspa.2010.0301

[32] Matteo Rossi, Marcus Huber, Dagmar Bruß, and Chiara Macchiavello. Quantum hypergraph states. New Journal of Physics, 15 (11): 113022, 2013. 10.1088/1367-2630/15/11/113022.
https://doi.org/10.1088/1367-2630/15/11/113022

[33] Yaoyun Shi. Both Toffoli and Controlled-NOT Need Little Help to Do Universal Quantum Computing. 3 (1): 84–92, 2003. ISSN 1533-7146. 10.5555/2011508.2011515.
https://doi.org/10.5555/2011508.2011515

[34] Dorit Aharonov. A simple proof that Toffoli and Hadamard are quantum universal. arXiv preprint quant-ph/0301040, 2003. 10.48550/arXiv.quant-ph/0301040.
https://doi.org/10.48550/arXiv.quant-ph/0301040
arXiv:quant-ph/0301040

[35] 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.
https://doi.org/10.1103/PhysRevA.71.022316

[36] Hans J Briegel, David E Browne, Wolfgang Dür, Robert Raussendorf, and Maarten Van den Nest. Measurement-based quantum computation. Nature Physics, 5 (1): 19–26, 2009. 10.1038/nphys1157.
https://doi.org/10.1038/nphys1157

[37] 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.
https://doi.org/10.1103/PhysRevX.6.021043

[38] 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.
https://doi.org/10.1103/PhysRevA.52.3457

[39] 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.
https://doi.org/10.1103/PhysRevLett.116.080402

[40] Mark M Wilde. Quantum information theory. Cambridge University Press, 2013. 10.1017/9781316809976.
https://doi.org/10.1017/9781316809976

[41] John Watrous. The Theory of Quantum Information. Cambridge University Press, 2018. 10.1017/9781316848142.
https://doi.org/10.1017/9781316848142

[42] Patrick Hayden, Debbie Leung, Peter W Shor, and Andreas Winter. Randomizing quantum states: Constructions and applications. Communications in Mathematical Physics, 250: 371–391, 2004. 10.1007/s00220-004-1087-6.
https://doi.org/10.1007/s00220-004-1087-6

[43] Ashley Montanaro. Quantum states cannot be transmitted efficiently classically. Quantum, 3: 154, 2019. 10.22331/q-2019-06-28-154.
https://doi.org/10.22331/q-2019-06-28-154

[44] Teiko Heinosaari, Takayuki Miyadera, and Mário Ziman. An invitation to quantum incompatibility. Journal of Physics A: Mathematical and Theoretical, 49 (12): 123001, 2016. 10.1088/1751-8113/49/12/123001.
https://doi.org/10.1088/1751-8113/49/12/123001

[45] María García Díaz, 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.
https://doi.org/10.22331/q-2018-10-19-100

[46] 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.
https://doi.org/10.1103/PhysRevLett.122.150402

[47] Ryuji Takagi and Hiroyasu Tajima. Universal limitations on implementing resourceful unitary evolutions. Physical Review A, 101 (2): 022315, 2020. 10.1103/PhysRevA.101.022315.
https://doi.org/10.1103/PhysRevA.101.022315

[48] 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.
https://doi.org/10.1103/PhysRevX.11.021014

[49] 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.
https://doi.org/10.1103/PhysRevLett.118.090501

[50] 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.
https://doi.org/10.1098/rspa.2019.0251

[51] 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.
https://doi.org/10.1103/PhysRevA.94.052336

Cited by

[1] Yu Luo, "One-shot manipulation of coherence in dynamic quantum resource theory", Physical Review A 111 2, 022447 (2025).

[2] Yiran Wang and Yongming Li, "Using magic resource to realize probabilistic channel simulation", Physical Review A 113 4, 042438 (2026).

[3] Sascha Heußen and Janine Hilder, "Efficient fault-tolerant code switching via one-way transversal CNOT gates", Quantum 9, 1846 (2025).

[4] Aidin Salamzadeh, Leo-Paul Dana, Morteza Hadizadeh, and Niloofar Rastgoo, "Quantum-enhanced AI entrepreneurship in tourism: Transforming dynamic and personalized business models", Journal of Entrepreneurial Researchers 3 2, 005 (2025).

[5] Benchi Zhao, Kosuke Ito, and Keisuke Fujii, "Probabilistic channel simulation using coherence", Physical Review Research 6 4, 043316 (2024).

[6] Victor V. Albert and Philippe Faist, "Handbook of Error-Correcting Codes", arXiv:2606.11484, (2026).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-17 22:16:39) and SAO/NASA ADS (last updated successfully 2026-08-17 22:16:40). The list may be incomplete as not all publishers provide suitable and complete citation data.

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.