No-signalling constrains quantum computation with indefinite causal structure

Luca Apadula1,2, Alessandro Bisio3,4, and Paolo Perinotti3,4

1University of Vienna, Boltzmanngasse 5, 1090 Vienna, Austria
2Institute for Quantum Optics and Quantum Information (IQOQI), Austrian Academy of Sciences, Boltzmanngasse 3, 1090 Vienna, Austria
3Dipartimento di Fisica, Università di Pavia, via Bassi 6, 27100 Pavia, Italy
4Istituto Nazionale di Fisica Nucleare, Sezione di Pavia, Italy

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


Quantum processes with indefinite causal structure emerge when we wonder which are the most general evolutions, allowed by quantum theory, of a set of local systems which are not assumed to be in any particular causal order. These processes can be described within the framework of $higher-order$ quantum theory which, starting from considering maps from quantum transformations to quantum transformations, recursively constructs a hierarchy of quantum maps of increasingly higher order. In this work, we develop a formalism for quantum computation with indefinite causal structures; namely, we characterize the computational structure of higher order quantum maps. Taking an axiomatic approach, the rules of this computation are identified as the most general compositions of higher order maps which are compatible with the mathematical structure of quantum theory. We provide a mathematical characterization of the admissible composition for arbitrary higher order quantum maps. We prove that these rules, which have a computational and information-theoretic nature, are determined by the more physical notion of the signalling relations between the quantum systems of the higher order quantum maps.

► BibTeX data

► References

[1] Carl W. Helstrom. Quantum detection and estimation theory. Journal of Statistical Physics, 1 (2): 231–252, June 1969. 10.1007/​BF01007479.

[2] Aleksei Yur'evich Kitaev. Quantum computations: algorithms and error correction. Uspekhi Matematicheskikh Nauk, 52 (6): 53–112, 1997. 10.1070/​RM1997v052n06ABEH002155. URL https:/​/​​10.1070/​RM1997v052n06ABEH002155.

[3] Andrew Childs, John Preskill, and Joseph Renes. Quantum information and precision measurement. Journal of Modern Optics - J MOD OPTIC, 47, 05 1999. 10.1080/​09500340008244034.

[4] A. Acín. Statistical distinguishability between unitary operations. Phys. Rev. Lett., 87: 177901, Oct 2001. 10.1103/​PhysRevLett.87.177901. URL https:/​/​​10.1103/​PhysRevLett.87.177901.

[5] G. Mauro D'Ariano, Paoloplacido Lo Presti, and Matteo G. A. Paris. Using entanglement improves the precision of quantum measurements. Phys. Rev. Lett., 87: 270404, Dec 2001. 10.1103/​PhysRevLett.87.270404. URL https:/​/​​10.1103/​PhysRevLett.87.270404.

[6] Runyao Duan, Yuan Feng, and Mingsheng Ying. Entanglement is not necessary for perfect discrimination between unitary operations. Phys. Rev. Lett., 98: 100503, Mar 2007. 10.1103/​PhysRevLett.98.100503. URL https:/​/​​10.1103/​PhysRevLett.98.100503.

[7] Massimiliano F. Sacchi. Optimal discrimination of quantum operations. Phys. Rev. A, 71: 062340, Jun 2005. 10.1103/​PhysRevA.71.062340. URL https:/​/​​10.1103/​PhysRevA.71.062340.

[8] Giulio Chiribella, Giacomo M. D'Ariano, and Paolo Perinotti. Memory effects in quantum channel discrimination. Phys. Rev. Lett., 101: 180501, Oct 2008a. 10.1103/​PhysRevLett.101.180501. URL https:/​/​​10.1103/​PhysRevLett.101.180501.

[9] Stefano Pirandola, Riccardo Laurenza, Cosmo Lupo, and Jason L. Pereira. Fundamental limits to quantum channel discrimination. npj Quantum Information, 5 (1): 50, 2019. 10.1038/​s41534-019-0162-y. URL https:/​/​​10.1038/​s41534-019-0162-y.

[10] Mário Ziman. Process positive-operator-valued measure: A mathematical framework for the description of process tomography experiments. Phys. Rev. A, 77: 062112, Jun 2008. 10.1103/​PhysRevA.77.062112. URL https:/​/​​10.1103/​PhysRevA.77.062112.

[11] Giulio Chiribella, Giacomo Mauro D'Ariano, and Paolo Perinotti. Theoretical framework for quantum networks. Phys. Rev. A, 80: 022339, Aug 2009. 10.1103/​PhysRevA.80.022339.

[12] Alessandro Bisio and Paolo Perinotti. Theoretical framework for higher-order quantum theory. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 475 (2225): 20180706, 2019. 10.1098/​rspa.2018.0706. URL https:/​/​​doi/​abs/​10.1098/​rspa.2018.0706.

[13] Giulio Chiribella, Giacomo Mauro D'Ariano, and Paolo Perinotti. Optimal cloning of unitary transformation. Phys. Rev. Lett., 101: 180504, Oct 2008b. 10.1103/​PhysRevLett.101.180504. URL https:/​/​​10.1103/​PhysRevLett.101.180504.

[14] A. Bisio, G. Chiribella, G. M. D'Ariano, S. Facchini, and P. Perinotti. Optimal quantum tomography of states, measurements, and transformations. Phys. Rev. Lett., 102: 010404, Jan 2009. 10.1103/​PhysRevLett.102.010404. URL https:/​/​​10.1103/​PhysRevLett.102.010404.

[15] Alessandro Bisio, Giulio Chiribella, Giacomo Mauro D'Ariano, Stefano Facchini, and Paolo Perinotti. Optimal quantum learning of a unitary transformation. Phys. Rev. A, 81: 032324, Mar 2010. 10.1103/​PhysRevA.81.032324. URL https:/​/​​10.1103/​PhysRevA.81.032324.

[16] Gus Gutoski. On a measure of distance for quantum strategies. Journal of Mathematical Physics, 53 (3): 032202, 03 2012a. ISSN 0022-2488. 10.1063/​1.3693621. URL https:/​/​​10.1063/​1.3693621.

[17] Gus Gutoski. On a measure of distance for quantum strategies. Journal of Mathematical Physics, 53 (3): 032202, 03 2012b. ISSN 0022-2488. 10.1063/​1.3693621. URL https:/​/​​10.1063/​1.3693621.

[18] Anna Jenčová and Martin Plávala. Conditions for optimal input states for discrimination of quantum channels. Journal of Mathematical Physics, 57 (12): 122203, 12 2016. ISSN 0022-2488. 10.1063/​1.4972286. URL https:/​/​​10.1063/​1.4972286.

[19] Michal Sedlák, Alessandro Bisio, and Mário Ziman. Optimal probabilistic storage and retrieval of unitary channels. Phys. Rev. Lett., 122: 170502, May 2019. 10.1103/​PhysRevLett.122.170502. URL https:/​/​​10.1103/​PhysRevLett.122.170502.

[20] Yin Mo and Giulio Chiribella. Quantum-enhanced learning of rotations about an unknown direction. New Journal of Physics, 21 (11): 113003, nov 2019. 10.1088/​1367-2630/​ab4d9a. URL https:/​/​​10.1088/​1367-2630/​ab4d9a.

[21] Qingxiuxiong Dong, Marco Túlio Quintino, Akihito Soeda, and Mio Murao. Success-or-draw: A strategy allowing repeat-until-success in quantum computation. Physical Review Letters, 126 (15), April 2021. ISSN 1079-7114. 10.1103/​physrevlett.126.150504. URL http:/​/​​10.1103/​PhysRevLett.126.150504.

[22] Akihito Soeda, Atsushi Shimbo, and Mio Murao. Optimal quantum discrimination of single-qubit unitary gates between two candidates. Phys. Rev. A, 104: 022422, Aug 2021. 10.1103/​PhysRevA.104.022422. URL https:/​/​​10.1103/​PhysRevA.104.022422.

[23] A. Bisio, G. Chiribella, G. D'Ariano, and P. Perinotti. Quantum networks: General theory and applications. Acta Physica Slovaca. Reviews and Tutorials, 61 (3), June 2011. ISSN 0323-0465. 10.2478/​v10155-011-0003-9. URL http:/​/​​10.2478/​v10155-011-0003-9.

[24] Ognyan Oreshkov, Fabio Costa, and Časlav Brukner. Quantum correlations with no causal order. Nature Communications, 3 (1): 1092, 2012. 10.1038/​ncomms2076. URL https:/​/​​10.1038/​ncomms2076.

[25] Giulio Chiribella, Giacomo Mauro D'Ariano, Paolo Perinotti, and Benoit Valiron. Quantum computations without definite causal structure. Phys. Rev. A, 88: 022318, Aug 2013. 10.1103/​PhysRevA.88.022318. URL https:/​/​​10.1103/​PhysRevA.88.022318.

[26] 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, Aug 2018. 10.1103/​PhysRevLett.121.090503. URL https:/​/​​10.1103/​PhysRevLett.121.090503.

[27] Timoteo Colnaghi, Giacomo Mauro D'Ariano, Stefano Facchini, and Paolo Perinotti. Quantum computation with programmable connections between gates. Physics Letters A, 376 (45): 2940–2943, October 2012. ISSN 0375-9601. 10.1016/​j.physleta.2012.08.028. URL http:/​/​​10.1016/​j.physleta.2012.08.028.

[28] Mateus Araújo, Fabio Costa, and Časlav Brukner. Computational advantage from quantum-controlled ordering of gates. Phys. Rev. Lett., 113: 250402, Dec 2014. 10.1103/​PhysRevLett.113.250402. URL https:/​/​​10.1103/​PhysRevLett.113.250402.

[29] Daniel Ebler, Sina Salek, and Giulio Chiribella. Enhanced communication with the assistance of indefinite causal order. Phys. Rev. Lett., 120: 120502, Mar 2018. 10.1103/​PhysRevLett.120.120502. URL https:/​/​​10.1103/​PhysRevLett.120.120502.

[30] Xiaobin Zhao, Yuxiang Yang, and Giulio Chiribella. Quantum metrology with indefinite causal order. Phys. Rev. Lett., 124: 190503, May 2020. 10.1103/​PhysRevLett.124.190503. URL https:/​/​​10.1103/​PhysRevLett.124.190503.

[31] Jessica Bavaresco, Mio Murao, and Marco Túlio Quintino. Strict hierarchy between parallel, sequential, and indefinite-causal-order strategies for channel discrimination. Phys. Rev. Lett., 127: 200504, Nov 2021. 10.1103/​PhysRevLett.127.200504. URL https:/​/​​10.1103/​PhysRevLett.127.200504.

[32] Martin J. Renner and Časlav Brukner. Reassessing the computational advantage of quantum-controlled ordering of gates. Phys. Rev. Res., 3: 043012, Oct 2021. 10.1103/​PhysRevResearch.3.043012. URL https:/​/​​10.1103/​PhysRevResearch.3.043012.

[33] 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 EP –, 08 2015. URL http:/​/​​10.1038/​ncomms8913.

[34] Timothy M. Rambo, Joseph B. Altepeter, Prem Kumar, and G. Mauro D'Ariano. Functional quantum computing: An optical approach. Phys. Rev. A, 93: 052321, May 2016. 10.1103/​PhysRevA.93.052321. URL https:/​/​​10.1103/​PhysRevA.93.052321.

[35] 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. Physical Review Letters, 124 (3), January 2020. ISSN 1079-7114. 10.1103/​physrevlett.124.030502. URL http:/​/​​10.1103/​PhysRevLett.124.030502.

[36] 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, Feb 2021. 10.1103/​PRXQuantum.2.010320. URL https:/​/​​10.1103/​PRXQuantum.2.010320.

[37] Robin Lorenz and Jonathan Barrett. Causal and compositional structure of unitary transformations. Quantum, 5: 511, July 2021. ISSN 2521-327X. 10.22331/​q-2021-07-28-511. URL http:/​/​​10.22331/​q-2021-07-28-511.

[38] A. Kissinger and S. Uijlen. A categorical semantics for causal structure. In 2017 32nd Annual ACM/​IEEE Symposium on Logic in Computer Science (LICS), pages 1–12, June 2017. 10.1109/​LICS.2017.8005095.

[39] Karl Kraus, A. Böhm, J. D. Dollard, and W. H. Wootters. States, Effects, and Operations Fundamental Notions of Quantum Theory, volume 190. 1983. 10.1007/​3-540-12732-1.

[40] Man-Duen Choi. Completely positive linear maps on complex matrices. Linear Algebra and its Applications, 10 (3): 285 – 290, 1975. ISSN 0024-3795. http:/​/​​10.1016/​0024-3795(75)90075-0. URL http:/​/​​science/​article/​pii/​0024379575900750.

[41] A. Jamiołkowski. Linear transformations which preserve trace and positive semidefiniteness of operators. Reports on Mathematical Physics, 3 (4): 275–278, 1972. ISSN 0034-4877. https:/​/​​10.1016/​0034-4877(72)90011-0. URL https:/​/​​science/​article/​pii/​0034487772900110.

[42] Supplemental Material.

[43] Mateus Araújo, Cyril Branciard, Fabio Costa, Adrien Feix, Christina Giarmatzi, and Časlav Brukner. Witnessing causal nonseparability. New Journal of Physics, 17 (10): 102001, October 2015. ISSN 1367-2630. 10.1088/​1367-2630/​17/​10/​102001. URL http:/​/​​10.1088/​1367-2630/​17/​10/​102001.

[44] Ognyan Oreshkov and Christina Giarmatzi. Causal and causally separable processes. New Journal of Physics, 18 (9): 093020, September 2016. ISSN 1367-2630. 10.1088/​1367-2630/​18/​9/​093020. URL http:/​/​​10.1088/​1367-2630/​18/​9/​093020.

[45] Cyril Branciard, Mateus Araújo, Adrien Feix, Fabio Costa, and Časlav Brukner. The simplest causal inequalities and their violation. New Journal of Physics, 18 (1): 013008, December 2015. ISSN 1367-2630. 10.1088/​1367-2630/​18/​1/​013008. URL http:/​/​​10.1088/​1367-2630/​18/​1/​013008.

[46] Esteban Castro-Ruiz, Flaminia Giacomini, and Časlav Brukner. Dynamics of quantum causal structures. Phys. Rev. X, 8: 011047, Mar 2018. 10.1103/​PhysRevX.8.011047. URL https:/​/​​10.1103/​PhysRevX.8.011047.

[47] David Beckman, Daniel Gottesman, M. A. Nielsen, and John Preskill. Causal and localizable quantum operations. Phys. Rev. A, 64: 052309, Oct 2001. 10.1103/​PhysRevA.64.052309. URL https:/​/​​10.1103/​PhysRevA.64.052309.

[48] Eggeling, T., Schlingemann, D., and Werner, R. F. Semicausal operations are semilocalizable. Europhys. Lett., 57 (6): 782–788, 2002. 10.1209/​epl/​i2002-00579-4. URL https:/​/​​10.1209/​epl/​i2002-00579-4.

[49] G. Chiribella, G. M. D'Ariano, and P. Perinotti. Quantum circuit architecture. Phys. Rev. Lett., 101: 060401, Aug 2008c. 10.1103/​PhysRevLett.101.060401. URL https:/​/​​10.1103/​PhysRevLett.101.060401.

[50] G. Chiribella, G. M. D'Ariano, and P. Perinotti. Transforming quantum operations: Quantum supermaps. EPL (Europhysics Letters), 83 (3): 30004, July 2008d. ISSN 1286-4854. 10.1209/​0295-5075/​83/​30004. URL http:/​/​​10.1209/​0295-5075/​83/​30004.

[51] K. Hrbacek and T. Jech. Introduction to set theory third edition, revised and expanded. 01 2017. 10.1201/​9781315274096.

Cited by

[1] James Hefford and Matt Wilson, "A Profunctorial Semantics for Quantum Supermaps", arXiv:2402.02997, (2024).

[2] Will Simmons and Aleks Kissinger, "A complete logic for causal consistency", arXiv:2403.09297, (2024).

[3] Simon Milz and Marco Túlio Quintino, "Transformations between arbitrary (quantum) objects and the emergence of indefinite causality", arXiv:2305.01247, (2023).

[4] Eleftherios-Ermis Tselentis and ńmin Baumeler, "Admissible Causal Structures and Correlations", PRX Quantum 4 4, 040307 (2023).

[5] Kyrylo Simonov, Marcello Caleffi, Jessica Illiano, and Angela Sara Cacciapuoti, "Universal Quantum Computation via Superposed Orders of Single-Qubit Gates", arXiv:2311.13654, (2023).

[6] Matt Wilson and Giulio Chiribella, "Free Polycategories for Unitary Supermaps of Arbitrary Dimension", arXiv:2207.09180, (2022).

The above citations are from SAO/NASA ADS (last updated successfully 2024-04-21 16:50:10). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2024-04-21 16:50:09).