{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,27]],"date-time":"2026-10-27T17:02:55Z","timestamp":1793120575547,"version":"4.5.0"},"reference-count":52,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2023,3,9]],"date-time":"2023-03-09T00:00:00Z","timestamp":1678320000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100002850","name":"Fondo Nacional de Desarrollo Cient\u00edfico y Tecnol\u00f3gico","doi-asserted-by":"crossref","award":["1200266"],"award-info":[{"award-number":["1200266"]}],"id":[{"id":"10.13039\/501100002850","id-type":"DOI","asserted-by":"crossref"}]},{"name":"ANID\u2013 Millennium Science Initiative Program","award":["ICN17_012"],"award-info":[{"award-number":["ICN17_012"]}]},{"name":"ANID - Subdirecci\u00f3n de Capital Humano\/Doctorado Nacional","award":["2021-21211347"],"award-info":[{"award-number":["2021-21211347"]}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"The quantum switch is a quantum computational primitive that provides computational advantage by applying operations in a superposition of orders. In particular, it can reduce the number of gate queries required for solving promise problems where the goal is to discriminate between a set of properties of a given set of unitary gates. In this work, we use Complex Hadamard matrices to introduce more general promise problems, which reduce to the known Fourier and Hadamard promise problems as limiting cases. Our generalization loosens the restrictions on the size of the matrices, number of gates and dimension of the quantum systems, providing more parameters to explore. In addition, it leads to the conclusion that a continuous variable system is necessary to implement the most general promise problem. In the finite dimensional case, the family of matrices is restricted to the so-called Butson-Hadamard type, and the complexity of the matrix enters as a constraint. We introduce the \u201cquery per gate&apos;&apos; parameter and use it to prove that the quantum switch provides computational advantage for both the continuous and discrete cases. Our results should inspire implementations of promise problems using the quantum switch where parameters and therefore experimental setups can be chosen much more freely.<\/jats:p>","DOI":"10.22331\/q-2023-03-09-945","type":"journal-article","created":{"date-parts":[[2023,3,9]],"date-time":"2023-03-09T17:35:26Z","timestamp":1678383326000},"page":"945","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":10,"title":["Practical computational advantage from the quantum switch on a generalized family of promise problems"],"prefix":"10.22331","volume":"7","author":[{"given":"Jorge","family":"Escand\u00f3n-Monardes","sequence":"first","affiliation":[{"name":"Millennium Institute for Research in Optics and Physics Department, Universidad de Concepci\u00f3n, 160-C Concepci\u00f3n, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aldo","family":"Delgado","sequence":"additional","affiliation":[{"name":"Millennium Institute for Research in Optics and Physics Department, Universidad de Concepci\u00f3n, 160-C Concepci\u00f3n, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stephen P.","family":"Walborn","sequence":"additional","affiliation":[{"name":"Millennium Institute for Research in Optics and Physics Department, Universidad de Concepci\u00f3n, 160-C Concepci\u00f3n, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"9598","published-online":{"date-parts":[[2023,3,9]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Lucien Hardy. ``Quantum gravity computers: On the theory of computation with indefinite causal structure''. In Quantum Reality, Relativistic Causality, and Closing the Epistemic Circle: Essays in Honour of Abner Shimony. Pages 379\u2013401. Springer Netherlands, Dordrecht (2009).","DOI":"10.1007\/978-1-4020-9107-0_21"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Ognyan Oreshkov, Fabio Costa, and \u010caslav Brukner. ``Quantum correlations with no causal order''. Nature Communications 3, 1092 (2012).","DOI":"10.1038\/ncomms2076"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Giulio Chiribella, Giacomo Mauro D'Ariano, Paolo Perinotti, and Benoit Valiron. ``Quantum computations without definite causal structure''. Phys. Rev. A 88, 022318 (2013).","DOI":"10.1103\/PhysRevA.88.022318"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Cyril Branciard. ``Witnesses of causal nonseparability: an introduction and a few case studies''. Scientific Reports 6, 26018 (2016).","DOI":"10.1038\/srep26018"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Giulia Rubino, Lee A. Rozema, Adrien Feix, Mateus Ara\u00fajo, Jonas M. Zeuner, Lorenzo M. Procopio, \u010caslav Brukner, and Philip Walther. ``Experimental verification of an indefinite causal order''. Science Advances 3, e1602589 (2017).","DOI":"10.1126\/sciadv.1602589"},{"key":"5","doi-asserted-by":"publisher","unstructured":"K. Goswami, C. Giarmatzi, M. Kewming, F. Costa, C. Branciard, J. Romero, and A. G. White. ``Indefinite causal order in a quantum switch''. Phys. Rev. Lett. 121, 090503 (2018).","DOI":"10.1103\/PhysRevLett.121.090503"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Flaminia Giacomini, Esteban Castro-Ruiz, and \u010caslav Brukner. ``Indefinite causal structures for continuous-variable systems''. New Journal of Physics 18, 113026 (2016).","DOI":"10.1088\/1367-2630\/18\/11\/113026"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Jessica Bavaresco, Mateus Ara\u00fajo, \u010caslav Brukner, and Marco T\u00falio Quintino. ``Semi-device-independent certification of indefinite causal order''. Quantum 3, 176 (2019).","DOI":"10.22331\/q-2019-08-19-176"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Huan Cao, Jessica Bavaresco, Ning-Ning Wang, Lee A. Rozema, Chao Zhang, Yun-Feng Huang, Bi-Heng Liu, Chuan-Feng Li, Guang-Can Guo, and Philip Walther. ``Experimental semi-device-independent certification of indefinite causal order'' (2022). arXiv:2202.05346.","DOI":"10.48550\/arXiv.2202.05346"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Julian Wechs, Hippolyte Dourdent, Alastair A. Abbott, and Cyril Branciard. ``Quantum circuits with classical versus quantum control of causal order''. PRX Quantum 2, 030335 (2021).","DOI":"10.1103\/PRXQuantum.2.030335"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Giulio Chiribella. ``Perfect discrimination of no-signalling channels via quantum superposition of causal structures''. Phys. Rev. A 86, 040301 (2012).","DOI":"10.1103\/PhysRevA.86.040301"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Lorenzo M. Procopio, Amir Moqanaki, Mateus Ara\u00fajo, Fabio Costa, Irati Alonso Calafell, Emma G. Dowd, Deny R. Hamel, Lee A. Rozema, \u010caslav Brukner, and Philip Walther. ``Experimental superposition of orders of quantum gates''. Nature Communications 6, 7913 (2015).","DOI":"10.1038\/ncomms8913"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Mateus Ara\u00fajo, Fabio Costa, and \u010caslav Brukner. ``Computational advantage from quantum-controlled ordering of gates''. Phys. Rev. Lett. 113, 250402 (2014).","DOI":"10.1103\/PhysRevLett.113.250402"},{"key":"13","doi-asserted-by":"publisher","unstructured":"M\u00e1rcio M. Taddei, Jaime Cari\u00f1e, Daniel Mart\u00ednez, Tania Garc\u00eda, Nayda Guerrero, Alastair A. Abbott, Mateus Ara\u00fajo, Cyril Branciard, Esteban S. G\u00f3mez, Stephen P. Walborn, Leandro Aolita, and Gustavo Lima. ``Computational advantage from the quantum superposition of multiple temporal orders of photonic gates''. PRX Quantum 2, 010320 (2021).","DOI":"10.1103\/PRXQuantum.2.010320"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Martin J. Renner and \u010caslav Brukner. ``Computational advantage from a quantum superposition of qubit gate orders''. Phys. Rev. Lett. 128, 230503 (2022).","DOI":"10.1103\/PhysRevLett.128.230503"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Adrien Feix, Mateus Ara\u00fajo, and \u010caslav Brukner. ``Quantum superposition of the order of parties as a communication resource''. Phys. Rev. A 92, 052326 (2015).","DOI":"10.1103\/PhysRevA.92.052326"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Philippe Allard Gu\u00e9rin, Adrien Feix, Mateus Ara\u00fajo, and \u010caslav Brukner. ``Exponential communication complexity advantage from quantum superposition of the direction of communication''. Phys. Rev. Lett. 117, 100502 (2016).","DOI":"10.1103\/PhysRevLett.117.100502"},{"key":"17","doi-asserted-by":"publisher","unstructured":"Kejin Wei, Nora Tischler, Si-Ran Zhao, Yu-Huai Li, Juan Miguel Arrazola, Yang Liu, Weijun Zhang, Hao Li, Lixing You, Zhen Wang, Yu-Ao Chen, Barry C. Sanders, Qiang Zhang, Geoff J. Pryde, Feihu Xu, and Jian-Wei Pan. ``Experimental quantum switching for exponentially superior quantum communication complexity''. Phys. Rev. Lett. 122, 120504 (2019).","DOI":"10.1103\/PhysRevLett.122.120504"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Daniel Ebler, Sina Salek, and Giulio Chiribella. ``Enhanced communication with the assistance of indefinite causal order''. Phys. Rev. Lett. 120, 120502 (2018).","DOI":"10.1103\/PhysRevLett.120.120502"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Lorenzo M. Procopio, Francisco Delgado, Marco Enr\u00edquez, Nadia Belabas, and Juan Ariel Levenson. ``Communication enhancement through quantum coherent control of n channels in an indefinite causal-order scenario''. Entropy 21, 1012 (2019).","DOI":"10.3390\/e21101012"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Lorenzo M. Procopio, Francisco Delgado, Marco Enr\u00edquez, Nadia Belabas, and Juan Ariel Levenson. ``Sending classical information via three noisy channels in superposition of causal orders''. Phys. Rev. A 101, 012346 (2020).","DOI":"10.1103\/PhysRevA.101.012346"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Lorenzo M. Procopio, Francisco Delgado, Marco Enr\u00edquez, and Nadia Belabas. ``Multifold behavior of the information transmission by the quantum 3-switch''. Quantum Inf. Process. 20, 219 (2021).","DOI":"10.1007\/s11128-021-03159-0"},{"key":"22","doi-asserted-by":"publisher","unstructured":"K. Goswami, Y. Cao, G. A. Paz-Silva, J. Romero, and A. G. White. ``Increasing communication capacity via superposition of order''. Phys. Rev. Research 2, 033292 (2020).","DOI":"10.1103\/PhysRevResearch.2.033292"},{"key":"23","doi-asserted-by":"publisher","unstructured":"Yu Guo, Xiao-Min Hu, Zhi-Bo Hou, Huan Cao, Jin-Ming Cui, Bi-Heng Liu, Yun-Feng Huang, Chuan-Feng Li, Guang-Can Guo, and Giulio Chiribella. ``Experimental transmission of quantum information using a superposition of causal orders''. Phys. Rev. Lett. 124, 030502 (2020).","DOI":"10.1103\/PhysRevLett.124.030502"},{"key":"24","doi-asserted-by":"publisher","unstructured":"Giulio Chiribella, Manik Banik, Some Sankar Bhattacharya, Tamal Guha, Mir Alimuddin, Arup Roy, Sutapa Saha, Sristy Agrawal, and Guruprasad Kar. ``Indefinite causal order enables perfect quantum communication with zero capacity channels''. New Journal of Physics 23, 033039 (2021).","DOI":"10.1088\/1367-2630\/abe7a0"},{"key":"25","doi-asserted-by":"publisher","unstructured":"Giulio Chiribella, Matt Wilson, and H. F. Chau. ``Quantum and classical data transmission through completely depolarizing channels in a superposition of cyclic orders''. Phys. Rev. Lett. 127, 190502 (2021).","DOI":"10.1103\/PhysRevLett.127.190502"},{"key":"26","doi-asserted-by":"publisher","unstructured":"Matt Wilson and Giulio Chiribella. ``A diagrammatic approach to information transmission in generalised switches''. In Beno\u0131\u0302t Valiron, Shane Mansfield, Pablo Arrighi, and Prakash Panangaden, editors, Proceedings 17th International Conference on Quantum Physics and Logic, Paris, France, June 2 - 6, 2020. Volume 340 of Electronic Proceedings in Theoretical Computer Science, pages 333\u2013348. Open Publishing Association (2021).","DOI":"10.4204\/EPTCS.340.17"},{"key":"27","doi-asserted-by":"publisher","unstructured":"Sk Sazim, Michal Sedlak, Kratveer Singh, and Arun Kumar Pati. ``Classical communication with indefinite causal order for $n$ completely depolarizing channels''. Phys. Rev. A 103, 062610 (2021).","DOI":"10.1103\/PhysRevA.103.062610"},{"key":"28","doi-asserted-by":"publisher","unstructured":"David Felce and Vlatko Vedral. ``Quantum refrigeration with indefinite causal order''. Phys. Rev. Lett. 125, 070603 (2020).","DOI":"10.1103\/PhysRevLett.125.070603"},{"key":"29","doi-asserted-by":"publisher","unstructured":"Kyrylo Simonov, Gianluca Francica, Giacomo Guarnieri, and Mauro Paternostro. ``Work extraction from coherently activated maps via quantum switch''. Phys. Rev. A 105, 032217 (2022).","DOI":"10.1103\/PhysRevA.105.032217"},{"key":"30","doi-asserted-by":"publisher","unstructured":"Michael Frey. ``Indefinite causal order aids quantum depolarizing channel identification''. Quantum Inf. Process. 18 (2019).","DOI":"10.1007\/s11128-019-2186-9"},{"key":"31","doi-asserted-by":"publisher","unstructured":"Xiaobin Zhao, Yuxiang Yang, and Giulio Chiribella. ``Quantum metrology with indefinite causal order''. Phys. Rev. Lett. 124, 190503 (2020).","DOI":"10.1103\/PhysRevLett.124.190503"},{"key":"32","doi-asserted-by":"publisher","unstructured":"Fran\u00e7ois Chapeau-Blondeau. ``Noisy quantum metrology with the assistance of indefinite causal order''. Phys. Rev. A 103, 032615 (2021).","DOI":"10.1103\/PhysRevA.103.032615"},{"key":"33","doi-asserted-by":"publisher","unstructured":"Stefano Facchini and Simon Perdrix. ``Quantum circuits for the unitary permutation problem''. In Rahul Jain, Sanjay Jain, and Frank Stephan, editors, Theory and Applications of Models of Computation. Pages 324\u2013331. Cham (2015). Springer International Publishing.","DOI":"10.1007\/978-3-319-17142-5_28"},{"key":"34","doi-asserted-by":"publisher","unstructured":"Martin J. Renner and \u010caslav Brukner. ``Reassessing the computational advantage of quantum-controlled ordering of gates''. Phys. Rev. Research 3, 043012 (2021).","DOI":"10.1103\/PhysRevResearch.3.043012"},{"key":"35","doi-asserted-by":"publisher","unstructured":"Mohammad Mirhosseini, Omar S Maga\u00f1a-Loaiza, Malcolm N O'Sullivan, Brandon Rodenburg, Mehul Malik, Martin P J Lavery, Miles J Padgett, Daniel J Gauthier, and Robert W Boyd. ``High-dimensional quantum cryptography with twisted light''. New Journal of Physics 17, 033033 (2015).","DOI":"10.1088\/1367-2630\/17\/3\/033033"},{"key":"36","doi-asserted-by":"publisher","unstructured":"Leonardo Neves, G. Lima, J. G. Aguirre G\u00f3mez, C. H. Monken, C. Saavedra, and S. P\u00e1dua. ``Generation of entangled states of qudits using twin photons''. Phys. Rev. Lett. 94, 100501 (2005).","DOI":"10.1103\/PhysRevLett.94.100501"},{"key":"37","doi-asserted-by":"publisher","unstructured":"S. P. Walborn, D. S. Lemelle, M. P. Almeida, and P. H. Souto Ribeiro. ``Quantum key distribution with higher-order alphabets using spatially encoded qudits''. Phys. Rev. Lett. 96, 090501 (2006).","DOI":"10.1103\/PhysRevLett.96.090501"},{"key":"38","doi-asserted-by":"publisher","unstructured":"Wojciech Tadej and Karol \u017byczkowski. ``A concise guide to complex hadamard matrices''. Open Systems & Information Dynamics 13, 133\u2013\u2013177 (2006).","DOI":"10.1007\/s11080-006-8220-2"},{"key":"39","doi-asserted-by":"publisher","unstructured":"A. T. Butson. ``Generalized hadamard matrices''. Proceedings of the American Mathematical Society 13, 894\u2013898 (1962).","DOI":"10.1090\/S0002-9939-1962-0142557-0"},{"key":"40","doi-asserted-by":"publisher","unstructured":"Timoteo Colnaghi, Giacomo Mauro D'Ariano, Stefano Facchini, and Paolo Perinotti. ``Quantum computation with programmable connections between gates''. Physics Letters A 376, 2940\u20132943 (2012).","DOI":"10.1016\/j.physleta.2012.08.028"},{"key":"41","doi-asserted-by":"publisher","unstructured":"Kari-Jouko R\u00e4ih\u00e4 and Esko Ukkonen. ``The shortest common supersequence problem over binary alphabet is np-complete''. Theoretical Computer Science 16, 187\u2013198 (1981).","DOI":"10.1016\/0304-3975(81)90075-X"},{"key":"42","doi-asserted-by":"publisher","unstructured":"Kang Ning and Hon Wai Leong. ``Towards a better solution to the shortest common supersequence problem: The deposition and reduction algorithm''. In First International Multi-Symposiums on Computer and Computational Sciences (IMSCCS'06). Volume 1, pages 84\u201390. (2006).","DOI":"10.1109\/IMSCCS.2006.136"},{"key":"43","doi-asserted-by":"publisher","unstructured":"P.J. Koutas and T.C. Hu. ``Shortest string containing all permutations''. Discrete Mathematics 11, 125\u2013132 (1975).","DOI":"10.1016\/0012-365X(75)90004-7"},{"key":"44","doi-asserted-by":"publisher","unstructured":"X. S. Liu, G. L. Long, D. M. Tong, and Feng Li. ``General scheme for superdense coding between multiparties''. Phys. Rev. A 65, 022304 (2002).","DOI":"10.1103\/PhysRevA.65.022304"},{"key":"45","doi-asserted-by":"publisher","unstructured":"Michael Reck, Anton Zeilinger, Herbert J. Bernstein, and Philip Bertani. ``Experimental realization of any discrete unitary operator''. Phys. Rev. Lett. 73, 58\u201361 (1994).","DOI":"10.1103\/PhysRevLett.73.58"},{"key":"46","doi-asserted-by":"publisher","unstructured":"Andrea Crespi, Roberto Osellame, Roberta Ramponi, Marco Bentivegna, Fulvio Flamini, Nicol\u00f2 Spagnolo, Niko Viggianiello, Luca Innocenti, Paolo Mataloni, and Fabio Sciarrino. ``Suppression law of quantum states in a 3d photonic fast fourier transform chip''. Nature Communications 7, 10469 (2016).","DOI":"10.1038\/ncomms10469"},{"key":"47","doi-asserted-by":"publisher","unstructured":"J. Cari\u00f1e, G. Ca\u00f1as, P. Skrzypczyk, I. \u0160upi\u0107, N. Guerrero, T. Garcia, L. Pereira, M. A. S. Prosser, G. B. Xavier, A. Delgado, S. P. Walborn, D. Cavalcanti, and G. Lima. ``Multi-core fiber integrated multi-port beam splitters for quantum information processing''. Optica 7, 542\u2013550 (2020).","DOI":"10.1364\/OPTICA.388912"},{"key":"48","doi-asserted-by":"publisher","unstructured":"Alexandra Maria P\u0103lici, Tudor-Alexandru Isdrail\u0103, Stefan Ataman, and Radu Ionicioiu. ``OAM tomography with heisenberg\u2013weyl observables''. Quantum Science and Technology 5, 045004 (2020).","DOI":"10.1088\/2058-9565\/ab9e5b"},{"key":"49","doi-asserted-by":"publisher","unstructured":"Osvaldo Jim\u00e9nez Far\u00edas, Fernando de Melo, P\u00e9rola Milman, and Stephen P. Walborn. ``Quantum information processing by weaving quantum talbot carpets''. Phys. Rev. A 91, 062328 (2015).","DOI":"10.1103\/PhysRevA.91.062328"},{"key":"50","doi-asserted-by":"publisher","unstructured":"Mariana R. Barros, Andreas Ketterer, Osvaldo Jim\u00e9nez Far\u00edas, and Stephen P. Walborn. ``Free-space entangled quantum carpets''. Phys. Rev. A. 95, 042311 (2017).","DOI":"10.1103\/PhysRevA.95.042311"},{"key":"51","doi-asserted-by":"publisher","unstructured":"D. S. Tasca, R. M. Gomes, F. Toscano, P. H. Souto Ribeiro, and S. P. Walborn. ``Continuous-variable quantum computation with spatial degrees of freedom of photons''. Phys. Rev. A 83, 052325 (2011).","DOI":"10.1103\/PhysRevA.83.052325"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2023-03-09-945\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2023,3,9]],"date-time":"2023-03-09T17:35:39Z","timestamp":1678383339000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2023-03-09-945\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,9]]},"references-count":52,"URL":"https:\/\/doi.org\/10.22331\/q-2023-03-09-945","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,3,9]]},"article-number":"945"}}