Quantum Advantage In Temporally Flat Measurement-based Quantum Computation

Republished By Plato

Followers: 0

Michael de Oliveira^1,2,3, Luís S. Barbosa^1,2,3, and Ernesto F. Galvão^3,4

¹University of Minho, Department of Computer Science, Braga, Portugal
²INESC TEC, Braga, Portugal
³International Iberian Nanotechnology Laboratory (INL) Av. Mestre Jose Veiga, 4715-330, Braga, Portugal
⁴Instituto de Física, Universidade Federal Fluminense Av. Gal. Milton Tavares de Souza s/n, Niterói, RJ, 24210-340, Brazil

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

Abstract

Several classes of quantum circuits have been shown to provide a quantum computational advantage under certain assumptions. The study of ever more restricted classes of quantum circuits capable of quantum advantage is motivated by possible simplifications in experimental demonstrations. In this paper we study the efficiency of measurement-based quantum computation with a completely flat temporal ordering of measurements. We propose new constructions for the deterministic computation of arbitrary Boolean functions, drawing on correlations present in multi-qubit Greenberger, Horne, and Zeilinger (GHZ) states. We characterize the necessary measurement complexity using the Clifford hierarchy, and also generally decrease the number of qubits needed with respect to previous constructions. In particular, we identify a family of Boolean functions for which deterministic evaluation using non-adaptive MBQC is possible, featuring quantum advantage in width and number of gates with respect to classical circuits.

Featured image: The non-adaptive MBQC model can be described by a specific computational architecture that is divided into the quantum state preparation process, the measurement routine, and the associated pre- and post-classical linear processing (top left). This model facilitates the study of resource requirements for evaluating symmetric Boolean functions in terms of the asymptotic number of qubits and operations required (top right). These elements reveal our main results [bottom], which are articulated for standard classical and quantum gate sets and circuit descriptions [bottom left], characterizing the set of Boolean functions that demonstrate quantum advantage with respect to the number of gates and the width of the circuits (bottom right).

[embedded content]

Popular summary

Quantum computing promises to deliver computational advantage with respect to the best classical algorithms for many tasks. Rigorous results quantifying this advantage are rare, and help focus the research on the crucial quantum resources that deliver better-than-classical performance. This quantum advantage can happen with respect to different resources: the total number of gates required, the depth of the resulting circuits, or the size of the memory used (known as circuit width).

In this work we analyse the evaluation of Boolean functions, something that quantum computers can do using the correlated outcomes of measurements on entangled Greenberger-Horne-Zeilinger (GHZ) states of many qubits. This variant of measurement-based quantum computation requires no adaptivity, so all qubits can be measured simultaneously. This flat temporal structure of the computational process results, in some cases, in very economical quantum circuits. We identify the characteristics of a Boolean function that determine how many qubits are needed, and the required measurement precision. For a particular family of Boolean functions we show there is a rigorous advantage in width and number of gates with respect to the corresponding family of classical circuits. In the future, our techniques may help devise better ways of using quantum resources also for adaptive circuits displaying more computational expressivity.

► BibTeX data

@article{Oliveira2024quantumadvantagein, doi = {10.22331/q-2024-04-09-1312}, url = {https://doi.org/10.22331/q-2024-04-09-1312}, title = {Quantum advantage in temporally flat measurement-based quantum computation}, author = {Oliveira, Michael de and Barbosa, Lu{‘{i}}s S. and Galv{~{a}}o, Ernesto F.}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {8}, pages = {1312}, month = apr, year = {2024} }

► References

[1] Scott Aaronson, DeVon Ingram, and William Kretschmer. “The Acrobatics of BQP”. In Shachar Lovett, editor, 37th Computational Complexity Conference (CCC 2022). Volume 234 of Leibniz International Proceedings in Informatics (LIPIcs), pages 20:1–20:17. Dagstuhl, Germany (2022). Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.CCC.2022.20

[2] Richard Jozsa and Noah Linden. “On the role of entanglement in quantum-computational speed-up”. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences 459, 2011–2032 (2003).
https://doi.org/10.1098/rspa.2002.1097

[3] Mark Howard, Joel Wallman, Victor Veitch, and Joseph Emerson. “Contextuality supplies the ‘magic’ for quantum computation”. Nature 510, 351–355 (2014).
https://doi.org/10.1038/nature13460

[4] Juan Bermejo-Vega, Nicolas Delfosse, Dan E. Browne, Cihan Okay, and Robert Raussendorf. “Contextuality as a resource for models of quantum computation with qubits”. Phys. Rev. Lett. 119, 120505 (2017).
https://doi.org/10.1103/PhysRevLett.119.120505

[5] Ernesto F. Galvão. “Discrete wigner functions and quantum computational speedup”. Phys. Rev. A 71, 042302 (2005).
https://doi.org/10.1103/PhysRevA.71.042302

[6] A. Mari and J. Eisert. “Positive wigner functions render classical simulation of quantum computation efficient”. Phys. Rev. Lett. 109, 230503 (2012).
https://doi.org/10.1103/PhysRevLett.109.230503

[7] Lov K. Grover. “The advantages of superposition”. Science 280, 228–228 (1998).
https://doi.org/10.1126/science.280.5361.228

[8] Robert Raussendorf and Hans J. Briegel. “A one-way quantum computer”. Phys. Rev. Lett. 86, 5188–5191 (2001).
https://doi.org/10.1103/PhysRevLett.86.5188

[9] Maarten Van den Nest, Akimasa Miyake, Wolfgang Dür, and Hans J. Briegel. “Universal resources for measurement-based quantum computation”. Phys. Rev. Lett. 97, 150504 (2006).
https://doi.org/10.1103/PhysRevLett.97.150504

[10] Janet Anders and Dan E. Browne. “Computational power of correlations”. Phys. Rev. Lett. 102, 050502 (2009).
https://doi.org/10.1103/PhysRevLett.102.050502

[11] Vincent Danos and Elham Kashefi. “Determinism in the one-way model”. Phys. Rev. A 74, 052310 (2006).
https://doi.org/10.1103/PhysRevA.74.052310

[12] Daniel E Browne, Elham Kashefi, Mehdi Mhalla, and Simon Perdrix. “Generalized flow and determinism in measurement-based quantum computation”. New Journal of Physics 9, 250 (2007).
https://doi.org/10.1088/1367-2630/9/8/250

[13] Michael J Bremner, Ashley Montanaro, and Dan J Shepherd. “Average-Case Complexity Versus Approximate Simulation of Commuting Quantum Computations”. Phys. Rev. Lett. 117, 080501 (2016).
https://doi.org/10.1103/PhysRevLett.117.080501

[14] Matty J. Hoban, Joel J. Wallman, Hussain Anwar, Naïri Usher, Robert Raussendorf, and Dan E. Browne. “Measurement-based classical computation”. Phys. Rev. Lett. 112, 140505 (2014).
https://doi.org/10.1103/PhysRevLett.112.140505

[15] Michael J. Bremner, Ashley Montanaro, and Dan J. Shepherd. “Achieving quantum supremacy with sparse and noisy commuting quantum computations”. Quantum 1, 8 (2017).
https://doi.org/10.22331/q-2017-04-25-8

[16] Leonardo Novo, Juani Bermejo-Vega, and Raúl García-Patrón. “Quantum advantage from energy measurements of many-body quantum systems”. Quantum 5, 465 (2021).
https://doi.org/10.22331/q-2021-06-02-465

[17] Masahito Hayashi and Yuki Takeuchi. “Verifying commuting quantum computations via fidelity estimation of weighted graph states”. New Journal of Physics 21, 93060 (2019).
https://doi.org/10.1088/1367-2630/ab3d88

[18] Juan Bermejo-Vega, Dominik Hangleiter, Martin Schwarz, Robert Raussendorf, and Jens Eisert. “Architectures for Quantum Simulation Showing a Quantum Speedup”. Phys. Rev. X 8, 021010 (2018).
https://doi.org/10.1103/PhysRevX.8.021010

[19] Jacob Miller, Stephen Sanders, and Akimasa Miyake. “Quantum supremacy in constant-time measurement-based computation: A unified architecture for sampling and verification”. Phys. Rev. A 96, 062320 (2017).
https://doi.org/10.1103/PhysRevA.96.062320

[20] Matty J Hoban, Earl T Campbell, Klearchos Loukopoulos, and Dan E Browne. “Non-adaptive measurement-based quantum computation and multi-party Bell inequalities”. New Journal of Physics 13, 23014 (2011).
https://doi.org/10.1088/1367-2630/13/2/023014

[21] Ryuhei Mori. “Periodic Fourier representation of Boolean functions”. Quantum Info. Comput. 19, 392–412 (2019). url: https://dl.acm.org/doi/abs/10.5555/3370251.3370253.
https://dl.acm.org/doi/abs/10.5555/3370251.3370253

[22] Markus Frembs, Sam Roberts, Earl T Campbell, and Stephen D Bartlett. “Hierarchies of resources for measurement-based quantum computation”. New Journal of Physics 25, 013002 (2023).
https://doi.org/10.1088/1367-2630/acaee2

[23] Jelena Mackeprang, Daniel Bhatti, Matty J Hoban, and Stefanie Barz. “The power of qutrits for non-adaptive measurement-based quantum computing”. New Journal of Physics 25, 073007 (2023).
https://doi.org/10.1088/1367-2630/acdf77

[24] Daniel Collins, Nicolas Gisin, Sandu Popescu, David Roberts, and Valerio Scarani. “Bell-Type Inequalities to Detect True $mathit{n}$-Body Nonseparability”. Phys. Rev. Lett. 88, 170405 (2002).
https://doi.org/10.1103/PhysRevLett.88.170405

[25] Nicolas Brunner, Daniel Cavalcanti, Stefano Pironio, Valerio Scarani, and Stephanie Wehner. “Bell nonlocality”. Rev. Mod. Phys. 86, 419–478 (2014).
https://doi.org/10.1103/RevModPhys.86.419

[26] Dmitrijs Kravčenko. “Quantum Games, Quantum States, Their Properties and Applications”. PhD thesis. Latvijas Universitāte. (2013).

[27] William Slofstra. “Lower bounds on the entanglement needed to play XOR non-local games”. Journal of Mathematical Physics 52, 102202 (2011).
https://doi.org/10.1063/1.3652924

[28] Andris Ambainis, Jānis Iraids, Dmitry Kravchenko, and Madars Virza. “Advantage of quantum strategies in random symmetric xor games”. In Antonín Kučera, Thomas A. Henzinger, Jaroslav Nešetřil, Tomáš Vojnar, and David Antoš, editors, Mathematical and Engineering Methods in Computer Science. Pages 57–68. Berlin, Heidelberg (2013). Springer Berlin Heidelberg.
https://doi.org/10.1007/978-3-642-36046-6_7

[29] Andris Ambainis and Janis Iraids. “Provable Advantage for Quantum Strategies in Random Symmetric XOR Games”. In Simone Severini and Fernando Brandao, editors, 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013). Volume 22 of Leibniz International Proceedings in Informatics (LIPIcs), pages 146–156. Dagstuhl, Germany (2013). Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.TQC.2013.146

[30] Samuel Marcovitch and Benni Reznik. “Implications of communication complexity in multipartite systems”. Phys. Rev. A 77, 032120 (2008).
https://doi.org/10.1103/PhysRevA.77.032120

[31] Marcin Pawłowski, Tomasz Paterek, Dagomir Kaszlikowski, Valerio Scarani, Andreas Winter, and Marek Żukowski. “Information causality as a physical principle”. Nature 461, 1101–1104 (2009).
https://doi.org/10.1038/nature08400

[32] Sandu Popescu and Daniel Rohrlich. “Quantum nonlocality as an axiom”. Foundations of Physics 24, 379–385 (1994).
https://doi.org/10.1007/BF02058098

[33] Jonathan Barrett, Noah Linden, Serge Massar, Stefano Pironio, Sandu Popescu, and David Roberts. “Nonlocal correlations as an information-theoretic resource”. Phys. Rev. A 71, 022101 (2005).
https://doi.org/10.1103/PhysRevA.71.022101

[34] A A Razborov. “Quantum communication complexity of symmetric predicates”. Izvestiya: Mathematics 67, 145 (2003).
https://doi.org/10.1070/IM2003v067n01ABEH000422

[35] Zhiqiang Zhang and Yaoyun Shi. “Communication complexities of symmetric XOR functions”. Quantum Information and Computation 9, 255–263 (2009). url: https://dl.acm.org/doi/abs/10.5555/2011781.2011786.
https://dl.acm.org/doi/abs/10.5555/2011781.2011786

[36] Pierre Botteron. “NonLocal Boxes and Communication Complexity”. Master’s thesis. Université Paul Sabatier Toulouse III. (2022). url: https://pierre-botteron.github.io/Articles/2022-06-MSc-Thesis.pdf.
https://pierre-botteron.github.io/Articles/2022-06-MSc-Thesis.pdf

[37] Kwangil Bae and Wonmin Son. “Generalized nonlocality criteria under the correlation symmetry”. Phys. Rev. A 98, 022116 (2018).
https://doi.org/10.1103/PhysRevA.98.022116

[38] Markus Frembs, Sam Roberts, and Stephen D Bartlett. “Contextuality as a resource for measurement-based quantum computation beyond qubits”. New Journal of Physics 20, 103011 (2018).
https://doi.org/10.1088/1367-2630/aae3ad

[39] Sergey Bravyi, David Gosset, and Robert König. “Quantum advantage with shallow circuits”. Science 362, 308–311 (2018).
https://doi.org/10.1126/science.aar3106

[40] Daniel Grier and Luke Schaeffer. “Interactive Shallow Clifford Circuits: Quantum Advantage against NC¹ and Beyond”. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. Pages 875–888. STOC 2020New York, NY, USA (2020). Association for Computing Machinery.
https://doi.org/10.1145/3357713.3384332

[41] Libor Caha, Xavier Coiteux-Roy, and Robert Koenig. “Single-qubit gate teleportation provides a quantum advantage” (2022). arXiv:2209.14158.
arXiv:2209.14158

[42] François Le Gall. “Average-Case Quantum Advantage with Shallow Circuits”. In Amir Shpilka, editor, 34th Computational Complexity Conference (CCC 2019). Volume 137 of Leibniz International Proceedings in Informatics (LIPIcs), pages 21:1—-21:20. Dagstuhl, Germany (2019). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
https://doi.org/10.4230/LIPIcs.CCC.2019.21

[43] Matthew Coudron, Jalex Stark, and Thomas Vidick. “Trading locality for time: certifiable randomness from low-depth circuits”. Communications in mathematical physics 382, 49–86 (2021).
https://doi.org/10.1007/s00220-021-03963-w

[44] Sergey Bravyi, David Gosset, Robert König, and Marco Tomamichel. “Quantum advantage with noisy shallow circuits”. Nature Physics 16, 1040–1045 (2020).
https://doi.org/10.1038/s41567-020-0948-z

[45] Atsuya Hasegawa and François Le Gall. “Quantum Advantage with Shallow Circuits Under Arbitrary Corruption”. In Hee-Kap Ahn and Kunihiko Sadakane, editors, 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Volume 212 of Leibniz International Proceedings in Informatics (LIPIcs), pages 74:1–74:16. Dagstuhl, Germany (2021). Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.ISAAC.2021.74

[46] Adam Bene Watts, Robin Kothari, Luke Schaeffer, and Avishay Tal. “Exponential Separation between Shallow Quantum Circuits and Unbounded Fan-in Shallow Classical Circuits”. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. Pages 515–526. STOC 2019New York, NY, USA (2019). Association for Computing Machinery.
https://doi.org/10.1145/3313276.3316404

[47] Natalie Parham. “On the Power and Limitations of Shallow Quantum Circuits”. Master’s thesis. University of Waterloo. (2022). url: https://uwspace.uwaterloo.ca/handle/10012/18702.
https://uwspace.uwaterloo.ca/handle/10012/18702

[48] Dmitri Maslov, Jin-Sung Kim, Sergey Bravyi, Theodore J Yoder, and Sarah Sheldon. “Quantum advantage for computations with limited space”. Nature Physics 17, 894–897 (2021).
https://doi.org/10.1038/s41567-021-01271-7

[49] Farid Ablayev, Aida Gainutdinova, Marek Karpinski, Cristopher Moore, and Christopher Pollett. “On the computational power of probabilistic and quantum branching program”. Information and Computation 203, 145–162 (2005).
https://doi.org/10.1016/j.ic.2005.04.003

[50] D Shepherd and M. J. Bremner. “Temporally unstructured quantum computation”. Proceedings of the Royal Society of London Series A 465, 1413–1439 (2009).
https://doi.org/10.1098/rspa.2008.0443

[51] Daniel M Greenberger, Michael A Horne, and Anton Zeilinger. “Going Beyond Bell’s Theorem”. In Menas Kafatos, editor, Bell’s Theorem, Quantum Theory and Conceptions of the Universe. Pages 69–72. Dordrecht (1989). Springer Netherlands.
https://doi.org/10.1007/978-94-017-0849-4_10

[52] Diogo Cruz, Romain Fournier, Fabien Gremion, Alix Jeannerot, Kenichi Komagata, Tara Tosic, Jarla Thiesbrummel, Chun Lam Chan, Nicolas Macris, Marc-André Dupertuis, and Clément Javerzac-Galy. “Efficient Quantum Algorithms for GHZ and W States, and Implementation on the IBM Quantum Computer”. Advanced Quantum Technologies 2, 1900015 (2019).
https://doi.org/10.1002/qute.201900015

[53] R. F. Werner and M. M. Wolf. “All-multipartite bell-correlation inequalities for two dichotomic observables per site”. Phys. Rev. A 64, 032112 (2001).
https://doi.org/10.1103/PhysRevA.64.032112

[54] Ryan O’Donnell. “Analysis of boolean functions”. Cambridge University Press. (2014). url: http://www.cs.cmu.edu/ ./odonnell/papers/Analysis-of-Boolean-Functions-by-Ryan-ODonnell.pdf.
http://www.cs.cmu.edu/~./odonnell/papers/Analysis-of-Boolean-Functions-by-Ryan-ODonnell.pdf

[55] Anastasiya Chistopolskaya and Vladimir V. Podolskii. “Parity Decision Tree Complexity is Greater Than Granularity” (2018). arXiv:1810.08668.
arXiv:1810.08668

[56] A Canteaut and M Videau. “Symmetric Boolean functions”. IEEE Transactions on Information Theory 51, 2791–2811 (2005).
https://doi.org/10.1109/TIT.2005.851743

[57] Larry J Stockmeyer. “On the combinational complexity of certain symmetric Boolean functions”. Mathematical systems theory 10, 323–336 (1976).
https://doi.org/10.1007/BF01683282

[58] R F Arnold and M A Harrison. “Algebraic Properties of Symmetric and Partially Symmetric Boolean Functions”. IEEE Transactions on Electronic Computers EC-12, 244–251 (1963).
https://doi.org/10.1109/PGEC.1963.263535

[59] An Braeken and Bart Preneel. “On the algebraic immunity of symmetric boolean functions”. In Subhamoy Maitra, C. E. Veni Madhavan, and Ramarathnam Venkatesan, editors, Progress in Cryptology – INDOCRYPT 2005. Volume 3797 of Lecture Notes in Computer Science, pages 35–48. Berlin, Heidelberg (2005). Springer Berlin Heidelberg.
https://doi.org/10.1007/11596219_4

[60] Harry Buhrman and Ronald de Wolf. “Complexity measures and decision tree complexity: a survey”. Theoretical Computer Science 288, 21–43 (2002).
https://doi.org/10.1016/S0304-3975(01)00144-X

[61] Matthew Amy, Dmitri Maslov, Michele Mosca, and Martin Roetteler. “A Meet-in-the-Middle Algorithm for Fast Synthesis of Depth-Optimal Quantum Circuits”. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 32, 818–830 (2013).
https://doi.org/10.1109/TCAD.2013.2244643

[62] V V Shende, S S Bullock, and I L Markov. “Synthesis of quantum-logic circuits”. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 25, 1000–1010 (2006).
https://doi.org/10.1109/TCAD.2005.855930

[63] Juha J Vartiainen, Mikko Möttönen, and Martti M Salomaa. “Efficient Decomposition of Quantum Gates”. Phys. Rev. Lett. 92, 177902 (2004).
https://doi.org/10.1103/PhysRevLett.92.177902

[64] Bei Zeng, Xie Chen, and Isaac L Chuang. “Semi-Clifford operations, structure of $mathcal{C}_{k}$ hierarchy, and gate complexity for fault-tolerant quantum computation”. Phys. Rev. A 77, 042313 (2008).
https://doi.org/10.1103/PhysRevA.77.042313

[65] Gary J Mooney, Charles D Hill, and Lloyd C L Hollenberg. “Cost-optimal single-qubit gate synthesis in the Clifford hierarchy”. Quantum 5, 396 (2021).
https://doi.org/10.22331/q-2021-02-15-396

[66] Nadish de Silva. “Efficient quantum gate teleportation in higher dimensions”. Proceedings of the Royal Society A 477, 20200865 (2021).
https://doi.org/10.1098/rspa.2020.0865

[67] Daniel Gottesman and Isaac L Chuang. “Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations”. Nature 402, 390–393 (1999).
https://doi.org/10.1038/46503

[68] Daniel Gottesman. “The Heisenberg Representation of Quantum Computers” (1998). arXiv:quant-ph/9807006.
arXiv:quant-ph/9807006

[69] Vadym Kliuchnikov, Dmitri Maslov, and Michele Mosca. “Fast and efficient exact synthesis of single-qubit unitaries generated by clifford and t gates”. Quantum Info. Comput. 13, 607–630 (2013). url: https://dl.acm.org/doi/abs/10.5555/2535649.2535653.
https://dl.acm.org/doi/abs/10.5555/2535649.2535653

[70] Nicolas Brunner, James Sharam, and Tamás Vértesi. “Testing the structure of multipartite entanglement with bell inequalities”. Phys. Rev. Lett. 108, 110501 (2012).
https://doi.org/10.1103/PhysRevLett.108.110501

[71] Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner, and Thomas Vidick. “Entangled Games Are Hard to Approximate”. SIAM Journal on Computing 40, 848–877 (2011).
https://doi.org/10.1137/090751293

[72] Yihui Quek, Eneet Kaur, and Mark M. Wilde. “Multivariate trace estimation in constant quantum depth”. Quantum 8, 1220 (2024).
https://doi.org/10.22331/q-2024-01-10-1220

[73] Peter Selinger. “Efficient Clifford+T Approximation of Single-Qubit Operators”. Quantum Info. Comput. 15, 159–180 (2015).

[74] Vadym Kliuchnikov, Dmitri Maslov, and Michele Mosca. “Practical Approximation of Single-Qubit Unitaries by Single-Qubit Quantum Clifford and T Circuits”. IEEE Transactions on Computers 65, 161–172 (2016).
https://doi.org/10.1109/TC.2015.2409842

[75] Neil J Ross. “Optimal Ancilla-Free CLIFFORD+V Approximation of Z-Rotations”. Quantum Info. Comput. 15, 932–950 (2015). url: https://dl.acm.org/doi/abs/10.5555/2871350.2871354.
https://dl.acm.org/doi/abs/10.5555/2871350.2871354

[76] Ethan Bernstein and Umesh Vazirani. “Quantum Complexity Theory”. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing. Pages 11–20. STOC ’93New York, NY, USA (1993). Association for Computing Machinery.
https://doi.org/10.1145/167088.167097

[77] Alex Bocharov, Martin Roetteler, and Krysta M Svore. “Efficient synthesis of probabilistic quantum circuits with fallback”. Phys. Rev. A 91, 052317 (2015).
https://doi.org/10.1103/PhysRevA.91.052317

[78] Alex Bocharov, Martin Roetteler, and Krysta M Svore. “Efficient Synthesis of Universal Repeat-Until-Success Quantum Circuits”. Phys. Rev. Lett. 114, 080502 (2015).
https://doi.org/10.1103/PhysRevLett.114.080502

[79] Ingo Wegener. “The Complexity of Boolean Functions”. John Wiley $&$ Sons, Inc. USA (1987).

[80] Heribert Vollmer. “Introduction to Circuit Complexity: A Uniform Approach”. Springer Publishing Company, Incorporated. (2010). 1st edition. url: https://link.springer.com/book/10.1007/978-3-662-03927-4.
https://link.springer.com/book/10.1007/978-3-662-03927-4

[81] R Smolensky. “Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity”. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing. Pages 77–82. STOC ’87New York, NY, USA (1987). Association for Computing Machinery.
https://doi.org/10.1145/28395.28404

[82] Jaikumar Radhakrishnan. “Better bounds for threshold formulas”. In [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science. Pages 314–323. IEEE Computer Society (1991).
https://doi.org/10.1109/SFCS.1991.185384

[83] Michael J Fischer, Albert R Meyer, and Michael S Paterson. “$Omega(Nlog n)$ Lower Bounds on Length of Boolean Formulas”. SIAM J. Comput. 11, 416–427 (1982).
https://doi.org/10.1137/0211033

[84] Sanjeev Arora and Boaz Barak. “Computational Complexity: A Modern Approach”. Cambridge University Press. USA (2009). 1st edition. url: https://dl.acm.org/doi/abs/10.5555/1540612.
https://dl.acm.org/doi/abs/10.5555/1540612

[85] Scott Aaronson. “How Much Structure Is Needed for Huge Quantum Speedups?” (2022). arXiv:2209.06930.
arXiv:2209.06930

[86] David A Barrington. “Bounded-width polynomial-size branching programs recognize exactly those languages in NC1”. Journal of Computer and System Sciences 38, 150–164 (1989).
https://doi.org/10.1016/0022-0000(89)90037-8

[87] Scott Aaronson and Alex Arkhipov. “The Computational Complexity of Linear Optics”. In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing. Pages 333–342. STOC ’11New York, NY, USA (2011). Association for Computing Machinery.
https://doi.org/10.1145/1993636.1993682

[88] Peter W Shor. “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”. SIAM Review 41, 303–332 (1999).
https://doi.org/10.1137/S0036144598347011

[89] Daniel R Simon. “On the Power of Quantum Computation”. SIAM Journal on Computing 26, 1474–1483 (1997).
https://doi.org/10.1137/S0097539796298637

[90] Gilles Brassard, Harry Buhrman, Noah Linden, André Allan Méthot, Alain Tapp, and Unger Falk. “Limit on Nonlocality in Any World in Which Communication Complexity Is Not Trivial”. Phys. Rev. Lett. 96, 250401 (2006).
https://doi.org/10.1103/PhysRevLett.96.250401

[91] Wim van Dam. “Implausible consequences of superstrong nonlocality”. Natural Computing 12, 9–12 (2013).
https://doi.org/10.1007/s11047-012-9353-6

[92] Matthew Amy and Michele Mosca. “T-Count Optimization and Reed–Muller Codes”. IEEE Transactions on Information Theory 65, 4771–4784 (2019).
https://doi.org/10.1109/TIT.2019.2906374

[93] Peter Bürgisser, Michael Clausen, and Mohammad A Shokrollahi. “Algebraic complexity theory”. Volume 315. Springer Science & Business Media. (2013). url: https://dl.acm.org/doi/abs/10.5555/1965416.
https://dl.acm.org/doi/abs/10.5555/1965416

[94] Guang Hao Low and Isaac L. Chuang. “Optimal hamiltonian simulation by quantum signal processing”. Phys. Rev. Lett. 118, 010501 (2017).
https://doi.org/10.1103/PhysRevLett.118.010501

[95] Jeongwan Haah. “Product Decomposition of Periodic Functions in Quantum Signal Processing”. Quantum 3, 190 (2019).
https://doi.org/10.22331/q-2019-10-07-190

[96] Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao, and Avishay Tal. “Degree vs. Approximate Degree and Quantum Implications of Huang’s Sensitivity Theorem”. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. Pages 1330–1342. STOC 2021New York, NY, USA (2021). Association for Computing Machinery.
https://doi.org/10.1145/3406325.3451047

[97] Hao Huang. “Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture”. Annals of Mathematics 190, 949–955 (2019).
https://doi.org/10.4007/annals.2019.190.3.6

[98] Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, and Juris Smotrovs. “Separations in Query Complexity Based on Pointer Functions”. J. ACM 64 (2017).
https://doi.org/10.1145/3106234

[99] Peter Høyer and Robert Špalek. “Quantum circuits with unbounded fan-out”. In Helmut Alt and Michel Habib, editors, STACS 2003. Pages 234–246. Berlin, Heidelberg (2003). Springer Berlin Heidelberg.
https://doi.org/10.1007/3-540-36494-3_22

[100] Austin K Daniel, Yingyue Zhu, C Huerta Alderete, Vikas Buchemmavari, Alaina M Green, Nhung H Nguyen, Tyler G Thurtell, Andrew Zhao, Norbert M Linke, and Akimasa Miyake. “Quantum computational advantage attested by nonlocal games with the cyclic cluster state”. Phys. Rev. Research 4, 033068 (2022).
https://doi.org/10.1103/PhysRevResearch.4.033068

[101] Paul Herringer and Robert Raussendorf. “Classification of measurement-based quantum wire in stabilizer PEPS”. Quantum 7, 1041 (2023).
https://doi.org/10.22331/q-2023-06-12-1041

[102] Abhishek Anand. “On the power of interleaved low-depth quantum and classical circuits”. Master’s thesis. University of Waterloo. (2022). url: https://uwspace.uwaterloo.ca/handle/10012/18805.
https://uwspace.uwaterloo.ca/handle/10012/18805

[103] John Preskill. “Quantum Computing in the NISQ era and beyond”. Quantum 2, 79 (2018).
https://doi.org/10.22331/q-2018-08-06-79

[104] Bülent Demirel, Weikai Weng, Christopher Thalacker, Matty Hoban, and Stefanie Barz. “Correlations for computation and computation for correlations”. npj Quantum Information 7, 1–8 (2021).
https://doi.org/10.1038/s41534-020-00354-2

[105] Manoranjan Swain, Amit Rai, Bikash K Behera, and Prasanta K Panigrahi. “Experimental demonstration of the violations of Mermin’s and Svetlichny’s inequalities for W and GHZ states”. Quantum Information Processing 18, 218 (2019).
https://doi.org/10.1007/s11128-019-2331-5

[106] Bo Yang, Rudy Raymond, Hiroshi Imai, Hyungseok Chang, and Hidefumi Hiraishi. “Testing scalable bell inequalities for quantum graph states on ibm quantum devices”. IEEE Journal on Emerging and Selected Topics in Circuits and Systems 12, 638–647 (2022).
https://doi.org/10.1109/JETCAS.2022.3201730

[107] F. Baccari, R. Augusiak, I. Šupić, J. Tura, and A. Acín. “Scalable bell inequalities for qubit graph states and robust self-testing”. Phys. Rev. Lett. 124, 020402 (2020).
https://doi.org/10.1103/PhysRevLett.124.020402

[108] Ken X Wei, Isaac Lauer, Srikanth Srinivasan, Neereja Sundaresan, Douglas T McClure, David Toyli, David C McKay, Jay M Gambetta, and Sarah Sheldon. “Verifying multipartite entangled Greenberger-Horne-Zeilinger states via multiple quantum coherences”. Phys. Rev. A 101, 032343 (2020).
https://doi.org/10.1103/PhysRevA.101.032343

[109] Wei-Jia Huang, Wei-Chen Chien, Chien-Hung Cho, Che-Chun Huang, Tsung-Wei Huang, and Ching-Ray Chang. “Mermin’s inequalities of multiple qubits with orthogonal measurements on IBM Q 53-qubit system”. Quantum Engineering 2, e45 (2020).
https://doi.org/10.1002/que2.45

[110] Meron Sheffer, Daniel Azses, and Emanuele G Dalla Torre. “Playing Quantum Nonlocal Games with Six Noisy Qubits on the Cloud”. Advanced Quantum Technologies 5, 2100081 (2022).
https://doi.org/10.1002/qute.202100081

[111] Vedran Dunjko, Theodoros Kapourniotis, and Elham Kashefi. “Quantum-Enhanced Secure Delegated Classical Computing”. Quantum Info. Comput. 16, 61–86 (2016).

[112] Stefanie Barz, Vedran Dunjko, Florian Schlederer, Merritt Moore, Elham Kashefi, and Ian A. Walmsley. “Enhanced delegated computing using coherence”. Phys. Rev. A 93, 032339 (2016).
https://doi.org/10.1103/PhysRevA.93.032339

[113] Marco Clementi, Anna Pappa, Andreas Eckstein, Ian A Walmsley, Elham Kashefi, and Stefanie Barz. “Classical multiparty computation using quantum resources”. Physical Review A 96, 062317 (2017).
https://doi.org/10.1103/PhysRevA.96.062317

[114] Nasir Ahmed and Kamisetty Ramamohan Rao. “Walsh-hadamard transform”. In Orthogonal transforms for digital signal processing. Pages 99–152. Springer (1975).

[115] Michael A Nielsen and Isaac L Chuang. “Quantum Computation and Quantum Information: 10th Anniversary Edition”. Cambridge University Press. (2010).
https://doi.org/10.1017/CBO9780511976667

[116] Philip Feinsilver and Jerzy Kocik. “Krawtchouk polynomials and krawtchouk matrices”. Pages 115–141. Recent Advances in Applied Probability. Springer US. Boston, MA (2005).
https://doi.org/10.1007/0-387-23394-6_5

[117] Philip Feinsilver and Rene Schott. “Krawtchouk transforms and convolutions”. Bulletin of Mathematical SciencesPages 1–19 (2018).
https://doi.org/10.1007/s13373-018-0132-2

[118] M. Stobińska, A. Buraczewski, M. Moore, W. R. Clements, J. J. Renema, S. W. Nam, T. Gerrits, A. Lita, W. S. Kolthammer, A. Eckstein, and I. A. Walmsley. “Quantum interference enables constant-time quantum information processing”. Science Advances 5, eaau9674 (2019).
https://doi.org/10.1126/sciadv.aau9674

[119] Ravindran Kannan and Achim Bachem. “Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix”. SIAM Journal on Computing 8, 499–507 (1979).
https://doi.org/10.1137/0208040

[120] Josh Alman and Virginia Vassilevska Williams. “A refined laser method and faster matrix multiplication”. In Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms. Page 522–539. SODA ’21USA (2021). Society for Industrial and Applied Mathematics.
https://doi.org/10.1137/1.9781611976465.32

Cited by

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.

SEO Powered Content & PR Distribution. Get Amplified Today.
PlatoData.Network Vertical Generative Ai. Empower Yourself. Access Here.
PlatoAiStream. Web3 Intelligence. Knowledge Amplified. Access Here.
PlatoESG. Carbon, CleanTech, Energy, Environment, Solar, Waste Management. Access Here.
PlatoHealth. Biotech and Clinical Trials Intelligence. Access Here.
Source: https://quantum-journal.org/papers/q-2024-04-09-1312/

Time Stamp: April 9, 2024

Time Stamp: May 15, 2023

Quantum advantage in temporally flat measurement-based quantum computation

Republished By Plato

Abstract

Popular summary

► BibTeX data

► References

Cited by

More from Quantum Journal

Latency considerations for stochastic optimizers in variational quantum algorithms

Analyticity constraints bound the decay of the spectral form factor

Half-integer vs. integer effects in quantum synchronization of spin systems

On tests of the quantum nature of gravitational interactions in presence of non-linear corrections to quantum mechanics

Towards a general framework of Randomized Benchmarking incorporating non-Markovian Noise

Classical simulations of communication channels

Mean field study of 2D quasiparticle condensate formation in presence of strong decay

Rapid quantum approaches for combinatorial optimisation inspired by optimal state-transfer

Persistent nonlocality in an ultracold-atom environment

Robust quantum many-body scars in lattice gauge theories

About Us

Vertical Search & Ai

Platform

Stay Connected

Account