Millennium Institute for Research in Optics and Physics Department, Universidad de Concepción, 160-C Concepción, Chile
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
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 “query per gate” 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.
Featured image: Example of a four-path quantum switch involving three unitary operations.
Popular summary
In particular, the quantum switch provides computational advantage in solving some promise problems, such as the Fourier Promise Problem. However, experimental implementations of this task are technically difficult, since they require the dimension of the quantum systems to scale factorially with the number of gates.
Here, we generalise previous approaches by introducing the Complex Hadamard Promise Problem and prove that this family exists for every finite dimension, removing the unfavourable scaling of the Fourier Promise Problem. Moreover, we take its study to the continuous variable regime and loosen restrictions on a number of parameters. This should inspire new practical implementations of promise problems using the quantum switch.
► BibTeX data
► References
[1] 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–401. Springer Netherlands, Dordrecht (2009).
https://doi.org/10.1007/978-1-4020-9107-0_21
[2] Ognyan Oreshkov, Fabio Costa, and Časlav Brukner. “Quantum correlations with no causal order”. Nature Communications 3, 1092 (2012).
https://doi.org/10.1038/ncomms2076
[3] Giulio Chiribella, Giacomo Mauro D’Ariano, Paolo Perinotti, and Benoit Valiron. “Quantum computations without definite causal structure”. Phys. Rev. A 88, 022318 (2013).
https://doi.org/10.1103/PhysRevA.88.022318
[4] Cyril Branciard. “Witnesses of causal nonseparability: an introduction and a few case studies”. Scientific Reports 6, 26018 (2016).
https://doi.org/10.1038/srep26018
[5] Giulia Rubino, Lee A. Rozema, Adrien Feix, Mateus Araújo, Jonas M. Zeuner, Lorenzo M. Procopio, Časlav Brukner, and Philip Walther. “Experimental verification of an indefinite causal order”. Science Advances 3, e1602589 (2017).
https://doi.org/10.1126/sciadv.1602589
[6] 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).
https://doi.org/10.1103/PhysRevLett.121.090503
[7] Flaminia Giacomini, Esteban Castro-Ruiz, and Časlav Brukner. “Indefinite causal structures for continuous-variable systems”. New Journal of Physics 18, 113026 (2016).
https://doi.org/10.1088/1367-2630/18/11/113026
[8] Jessica Bavaresco, Mateus Araújo, Časlav Brukner, and Marco Túlio Quintino. “Semi-device-independent certification of indefinite causal order”. Quantum 3, 176 (2019).
https://doi.org/10.22331/q-2019-08-19-176
[9] 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.
https://doi.org/10.48550/arXiv.2202.05346
arXiv:2202.05346
[10] 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).
https://doi.org/10.1103/PRXQuantum.2.030335
[11] Giulio Chiribella. “Perfect discrimination of no-signalling channels via quantum superposition of causal structures”. Phys. Rev. A 86, 040301 (2012).
https://doi.org/10.1103/PhysRevA.86.040301
[12] Lorenzo M. Procopio, Amir Moqanaki, Mateus Araújo, Fabio Costa, Irati Alonso Calafell, Emma G. Dowd, Deny R. Hamel, Lee A. Rozema, Časlav Brukner, and Philip Walther. “Experimental superposition of orders of quantum gates”. Nature Communications 6, 7913 (2015).
https://doi.org/10.1038/ncomms8913
[13] Mateus Araújo, Fabio Costa, and Časlav Brukner. “Computational advantage from quantum-controlled ordering of gates”. Phys. Rev. Lett. 113, 250402 (2014).
https://doi.org/10.1103/PhysRevLett.113.250402
[14] Márcio M. Taddei, Jaime Cariñe, Daniel Martínez, Tania García, Nayda Guerrero, Alastair A. Abbott, Mateus Araújo, Cyril Branciard, Esteban S. Gómez, 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).
https://doi.org/10.1103/PRXQuantum.2.010320
[15] Martin J. Renner and Časlav Brukner. “Computational advantage from a quantum superposition of qubit gate orders”. Phys. Rev. Lett. 128, 230503 (2022).
https://doi.org/10.1103/PhysRevLett.128.230503
[16] Adrien Feix, Mateus Araújo, and Časlav Brukner. “Quantum superposition of the order of parties as a communication resource”. Phys. Rev. A 92, 052326 (2015).
https://doi.org/10.1103/PhysRevA.92.052326
[17] Philippe Allard Guérin, Adrien Feix, Mateus Araújo, and Časlav Brukner. “Exponential communication complexity advantage from quantum superposition of the direction of communication”. Phys. Rev. Lett. 117, 100502 (2016).
https://doi.org/10.1103/PhysRevLett.117.100502
[18] 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).
https://doi.org/10.1103/PhysRevLett.122.120504
[19] Daniel Ebler, Sina Salek, and Giulio Chiribella. “Enhanced communication with the assistance of indefinite causal order”. Phys. Rev. Lett. 120, 120502 (2018).
https://doi.org/10.1103/PhysRevLett.120.120502
[20] Lorenzo M. Procopio, Francisco Delgado, Marco Enríquez, 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).
https://doi.org/10.3390/e21101012
[21] Lorenzo M. Procopio, Francisco Delgado, Marco Enríquez, Nadia Belabas, and Juan Ariel Levenson. “Sending classical information via three noisy channels in superposition of causal orders”. Phys. Rev. A 101, 012346 (2020).
https://doi.org/10.1103/PhysRevA.101.012346
[22] Lorenzo M. Procopio, Francisco Delgado, Marco Enríquez, and Nadia Belabas. “Multifold behavior of the information transmission by the quantum 3-switch”. Quantum Inf. Process. 20, 219 (2021).
https://doi.org/10.1007/s11128-021-03159-0
[23] 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).
https://doi.org/10.1103/PhysRevResearch.2.033292
[24] 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).
https://doi.org/10.1103/PhysRevLett.124.030502
[25] 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).
https://doi.org/10.1088/1367-2630/abe7a0
[26] 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).
https://doi.org/10.1103/PhysRevLett.127.190502
[27] Matt Wilson and Giulio Chiribella. “A diagrammatic approach to information transmission in generalised switches”. In Benoı̂t 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–348. Open Publishing Association (2021).
https://doi.org/10.4204/EPTCS.340.17
[28] 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).
https://doi.org/10.1103/PhysRevA.103.062610
[29] David Felce and Vlatko Vedral. “Quantum refrigeration with indefinite causal order”. Phys. Rev. Lett. 125, 070603 (2020).
https://doi.org/10.1103/PhysRevLett.125.070603
[30] Kyrylo Simonov, Gianluca Francica, Giacomo Guarnieri, and Mauro Paternostro. “Work extraction from coherently activated maps via quantum switch”. Phys. Rev. A 105, 032217 (2022).
https://doi.org/10.1103/PhysRevA.105.032217
[31] Michael Frey. “Indefinite causal order aids quantum depolarizing channel identification”. Quantum Inf. Process. 18 (2019).
https://doi.org/10.1007/s11128-019-2186-9
[32] Xiaobin Zhao, Yuxiang Yang, and Giulio Chiribella. “Quantum metrology with indefinite causal order”. Phys. Rev. Lett. 124, 190503 (2020).
https://doi.org/10.1103/PhysRevLett.124.190503
[33] François Chapeau-Blondeau. “Noisy quantum metrology with the assistance of indefinite causal order”. Phys. Rev. A 103, 032615 (2021).
https://doi.org/10.1103/PhysRevA.103.032615
[34] 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–331. Cham (2015). Springer International Publishing.
https://doi.org/10.1007/978-3-319-17142-5_28
[35] Martin J. Renner and Časlav Brukner. “Reassessing the computational advantage of quantum-controlled ordering of gates”. Phys. Rev. Research 3, 043012 (2021).
https://doi.org/10.1103/PhysRevResearch.3.043012
[36] Mohammad Mirhosseini, Omar S Magaña-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).
https://doi.org/10.1088/1367-2630/17/3/033033
[37] Leonardo Neves, G. Lima, J. G. Aguirre Gómez, C. H. Monken, C. Saavedra, and S. Pádua. “Generation of entangled states of qudits using twin photons”. Phys. Rev. Lett. 94, 100501 (2005).
https://doi.org/10.1103/PhysRevLett.94.100501
[38] 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).
https://doi.org/10.1103/PhysRevLett.96.090501
[39] Wojciech Tadej and Karol Życzkowski. “A concise guide to complex hadamard matrices”. Open Systems & Information Dynamics 13, 133––177 (2006).
https://doi.org/10.1007/s11080-006-8220-2
[40] A. T. Butson. “Generalized hadamard matrices”. Proceedings of the American Mathematical Society 13, 894–898 (1962).
https://doi.org/10.1090/S0002-9939-1962-0142557-0
[41] Timoteo Colnaghi, Giacomo Mauro D’Ariano, Stefano Facchini, and Paolo Perinotti. “Quantum computation with programmable connections between gates”. Physics Letters A 376, 2940–2943 (2012).
https://doi.org/10.1016/j.physleta.2012.08.028
[42] Kari-Jouko Räihä and Esko Ukkonen. “The shortest common supersequence problem over binary alphabet is np-complete”. Theoretical Computer Science 16, 187–198 (1981).
https://doi.org/10.1016/0304-3975(81)90075-X
[43] 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–90. (2006).
https://doi.org/10.1109/IMSCCS.2006.136
[44] P.J. Koutas and T.C. Hu. “Shortest string containing all permutations”. Discrete Mathematics 11, 125–132 (1975).
https://doi.org/10.1016/0012-365X(75)90004-7
[45] 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).
https://doi.org/10.1103/PhysRevA.65.022304
[46] Michael Reck, Anton Zeilinger, Herbert J. Bernstein, and Philip Bertani. “Experimental realization of any discrete unitary operator”. Phys. Rev. Lett. 73, 58–61 (1994).
https://doi.org/10.1103/PhysRevLett.73.58
[47] Andrea Crespi, Roberto Osellame, Roberta Ramponi, Marco Bentivegna, Fulvio Flamini, Nicolò 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).
https://doi.org/10.1038/ncomms10469
[48] J. Cariñe, G. Cañas, P. Skrzypczyk, I. Šupić, 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–550 (2020).
https://doi.org/10.1364/OPTICA.388912
[49] Alexandra Maria Pălici, Tudor-Alexandru Isdrailă, Stefan Ataman, and Radu Ionicioiu. “OAM tomography with heisenberg–weyl observables”. Quantum Science and Technology 5, 045004 (2020).
https://doi.org/10.1088/2058-9565/ab9e5b
[50] Osvaldo Jiménez Farías, Fernando de Melo, Pérola Milman, and Stephen P. Walborn. “Quantum information processing by weaving quantum talbot carpets”. Phys. Rev. A 91, 062328 (2015).
https://doi.org/10.1103/PhysRevA.91.062328
[51] Mariana R. Barros, Andreas Ketterer, Osvaldo Jiménez Farías, and Stephen P. Walborn. “Free-space entangled quantum carpets”. Phys. Rev. A. 95, 042311 (2017).
https://doi.org/10.1103/PhysRevA.95.042311
[52] 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).
https://doi.org/10.1103/PhysRevA.83.052325
Cited by
Could not fetch Crossref cited-by data during last attempt 2023-03-09 17:32:18: Could not fetch cited-by data for 10.22331/q-2023-03-09-945 from Crossref. This is normal if the DOI was registered recently. On SAO/NASA ADS no data on citing works was found (last attempt 2023-03-09 17:32:19).
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.
- Platoblockchain. Web3 Metaverse Intelligence. Knowledge Amplified. Access Here.
- Source: https://quantum-journal.org/papers/q-2023-03-09-945/
