Causal and compositional structure of unitary transformations

Robin Lorenz1,2 and Jonathan Barrett1

1Department of Computer Science, University of Oxford, Wolfson Building, Parks Road, Oxford OX1 3QD, UK
2Cambridge Quantum Computing Ltd, 17 Beaumont Street, Oxford OX1 2NA, UK

Abstract

The causal structure of a unitary transformation is the set of relations of possible influence between any input subsystem and any output subsystem. We study whether such causal structure can be understood in terms of compositional structure of the unitary. Given a quantum circuit with no path from input system $A$ to output system $B$, system $A$ cannot influence system $B$. Conversely, given a unitary $U$ with a no-influence relation from input $A$ to output $B$, it follows from [B. Schumacher and M. D. Westmoreland, Quantum Information Processing 4 no. 1, (Feb, 2005)] that there exists a circuit decomposition of $U$ with no path from $A$ to $B$. However, as we argue, there are unitaries for which there does not exist a circuit decomposition that makes all causal constraints evident $\textit{simultaneously}$. To address this, we introduce a new formalism of `extended circuit diagrams', which goes beyond what is expressible with quantum circuits, with the core new feature being the ability to represent direct sum structures in addition to sequential and tensor product composition. A $\textit{causally faithful}$ extended circuit decomposition, representing a unitary $U$, is then one for which there is a path from an input $A$ to an output $B$ if and only if there actually is influence from $A$ to $B$ in $U$. We derive causally faithful extended circuit decompositions for a large class of unitaries, where in each case, the decomposition is implied by the unitary's respective causal structure. We hypothesize that every finite-dimensional unitary transformation has a causally faithful extended circuit decomposition.

Whenever one is able to draw an intuitive picture that succinctly captures the essential features of a complicated whole, then not only does it usually help communication, arguably, this also is a sign of having achieved good conceptual understanding. Also for quantum theory there is a rich history of developing and employing diagrammatic reasoning, where quantum circuit diagrams capture aspects of how quantum systems interact with each other and evolve over time. Circuit diagrams are the basic ingredient to one of the main paradigms of quantum computation, and have also proven useful in research ranging from the foundations of quantum theory to the design of algorithms and efficient quantum compilers. One particular area of research of foundational, as well as applied importance is causality. Unitary transformations that play a fundamental role in the quantum formalism, describe the evolution of a set of systems and have a clear notion of causal structure: which of the systems can causally influence which other systems.

Combining all these lines of thought, this paper asks: can one understand the causal structure of a unitary transformation in compositional terms, i.e. through an intuitive diagram, where its components are connected up in such a way that lays bare where and how causal influence goes? We first show that this is generally not possible with ordinary circuit diagrams. We then derive new kinds of decompositions for many causal structures, as well as introduce a new graphical language of 'extended circuit diagrams' to visualise them. This novel perspective to study causal structure and its ramifications is of conceptual significance, as well as likely to facilitate progress with other open problems, which it in fact already has in the study of indefinite causal order, a much debated area of quantum physics.

► References

[1] G. Chiribella, G. M. D'Ariano, and P. Perinotti. Transforming quantum operations: Quantum supermaps. EPL (Europhysics Letters), 83 (3): 30004, jul 2008. 10.1209/​0295-5075/​83/​30004.
https:/​/​doi.org/​10.1209/​0295-5075/​83/​30004

[2] 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.
https:/​/​doi.org/​10.1103/​PhysRevA.80.022339

[3] 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.
https:/​/​doi.org/​10.1103/​PhysRevA.88.022318

[4] Rafael Chaves, Lukas Luft, and David Gross. Causal structures from entropic information: geometry and novel scenarios. New Journal of Physics, 16 (4): 043001, apr 2014. 10.1088/​1367-2630/​16/​4/​043001.
https:/​/​doi.org/​10.1088/​1367-2630/​16/​4/​043001

[5] Christopher J Wood and Robert W Spekkens. The lesson of causal discovery algorithms for quantum correlations: causal explanations of bell-inequality violations require fine-tuning. New Journal of Physics, 17 (3): 033002, mar 2015. 10.1088/​1367-2630/​17/​3/​033002.
https:/​/​doi.org/​10.1088/​1367-2630/​17/​3/​033002

[6] Tobias Fritz. Beyond bell’s theorem ii: Scenarios with arbitrary causal structure. Communications in Mathematical Physics, 341 (2): 391–434, 2016. 10.1007/​s00220-015-2495-5.
https:/​/​doi.org/​10.1007/​s00220-015-2495-5

[7] Rafael Chaves. Polynomial bell inequalities. Phys. Rev. Lett., 116: 010402, Jan 2016. 10.1103/​PhysRevLett.116.010402.
https:/​/​doi.org/​10.1103/​PhysRevLett.116.010402

[8] Marc-Olivier Renou, Elisa Bäumer, Sadra Boreiri, Nicolas Brunner, Nicolas Gisin, and Salman Beigi. Genuine quantum nonlocality in the triangle network. Phys. Rev. Lett., 123: 140401, Sep 2019. 10.1103/​PhysRevLett.123.140401.
https:/​/​doi.org/​10.1103/​PhysRevLett.123.140401

[9] Robert R Tucci. Quantum bayesian nets. International Journal of Modern Physics B, 9 (03): 295–337, 1995. 10.1142/​S0217979295000148.
https:/​/​doi.org/​10.1142/​S0217979295000148

[10] Robert R. Tucci. Factorization of quantum density matrices according to bayesian and markov networks. arXiv preprint quant-ph/​0701201. 2007.
arXiv:quant-ph/0701201

[11] M. S. Leifer and Robert W. Spekkens. Towards a formulation of quantum theory as a causally neutral theory of bayesian inference. Phys. Rev. A, 88: 052130, Nov 2013. 10.1103/​PhysRevA.88.052130.
https:/​/​doi.org/​10.1103/​PhysRevA.88.052130

[12] Rafael Chaves, Christian Majenz, and David Gross. Information–theoretic implications of quantum causal structures. Nature communications, 6 (1): 1–8, 2015. 10.1038/​ncomms6766.
https:/​/​doi.org/​10.1038/​ncomms6766

[13] Fabio Costa and Sally Shrapnel. Quantum causal modelling. New Journal of Physics, 18 (6): 063032, jun 2016. 10.1088/​1367-2630/​18/​6/​063032.
https:/​/​doi.org/​10.1088/​1367-2630/​18/​6/​063032

[14] John-Mark A. Allen, Jonathan Barrett, Dominic C. Horsman, Ciarán M. Lee, and Robert W. Spekkens. Quantum common causes and quantum causal models. Phys. Rev. X, 7: 031021, Jul 2017. 10.1103/​PhysRevX.7.031021.
https:/​/​doi.org/​10.1103/​PhysRevX.7.031021

[15] Jonathan Barrett, Robin Lorenz, and Ognyan Oreshkov. Quantum causal models. arXiv preprint quant-ph/​1906.10726. 2019.
arXiv:quant-ph/1906.10726

[16] Lucien Hardy. Probability theories with dynamic causal structure: a new framework for quantum gravity. arXiv preprint gr-qc/​0509120. 2005. https:/​/​arxiv.org/​abs/​gr-qc/​0509120.
https:/​/​arxiv.org/​abs/​gr-qc/​0509120

[17] Giulio Chiribella. Perfect discrimination of no-signalling channels via quantum superposition of causal structures. Phys. Rev. A, 86: 040301, Oct 2012. 10.1103/​PhysRevA.86.040301.
https:/​/​doi.org/​10.1103/​PhysRevA.86.040301

[18] Ognyan Oreshkov, Fabio Costa, and Caslav Brukner. Quantum correlations with no causal order. Nature Commun., 3: 1092, 2012. 10.1038/​ncomms2076.
https:/​/​doi.org/​10.1038/​ncomms2076

[19] 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, Sep 2016. 10.1103/​PhysRevLett.117.100502.
https:/​/​doi.org/​10.1103/​PhysRevLett.117.100502

[20] Caslav Brukner. Quantum causality. Nat Phys, 10 (4): 259–263, April 2014. 10.1038/​nphys2930.
https:/​/​doi.org/​10.1038/​nphys2930

[21] Christopher Portmann, Christian Matt, Ueli Maurer, Renato Renner, and Björn Tackmann. Causal boxes: Quantum information-processing systems closed under composition. IEEE Transactions on Information Theory, 63 (5): 3277–3305, 2017. 10.1109/​TIT.2017.2676805.
https:/​/​doi.org/​10.1109/​TIT.2017.2676805

[22] Ciarán M. Lee and Matty J. Hoban. Towards device-independent information processing on general quantum networks. Phys. Rev. Lett., 120: 020504, Jan 2018. 10.1103/​PhysRevLett.120.020504.
https:/​/​doi.org/​10.1103/​PhysRevLett.120.020504

[23] David Beckman, Daniel Gottesman, M. A. Nielsen, and John Preskill. Causal and localizable quantum operations. Phys. Rev., A64: 052309, 2001. 10.1103/​PhysRevA.64.052309.
https:/​/​doi.org/​10.1103/​PhysRevA.64.052309

[24] Benjamin Schumacher and Michael D. Westmoreland. Locality and information transfer in quantum operations. Quantum Information Processing, 4 (1): 13–34, Feb 2005. ISSN 1573-1332. 10.1007/​s11128-004-3193-y.
https:/​/​doi.org/​10.1007/​s11128-004-3193-y

[25] Pablo Arrighi, Vincent Nesme, and Reinhard Werner. Unitarity plus causality implies localizability. Journal of Computer and System Sciences, 77 (2): 372–378, 2011a. 10.1016/​j.jcss.2010.05.004.
https:/​/​doi.org/​10.1016/​j.jcss.2010.05.004

[26] T Eggeling, D Schlingemann, and R. F Werner. Semicausal operations are semilocalizable. Europhysics Letters (EPL), 57 (6): 782–788, mar 2002. 10.1209/​epl/​i2002-00579-4.
https:/​/​doi.org/​10.1209/​epl/​i2002-00579-4

[27] M. Piani, M. Horodecki, P. Horodecki, and R. Horodecki. Properties of quantum nonsignaling boxes. Phys. Rev. A, 74: 012305, Jul 2006. 10.1103/​PhysRevA.74.012305.
https:/​/​doi.org/​10.1103/​PhysRevA.74.012305

[28] Benjamin Schumacher and Michael D Westmoreland. Isolation and information flow in quantum dynamics. Foundations of Physics, 42 (7): 926–931, 2012. 10.1007/​s10701-012-9651-y.
https:/​/​doi.org/​10.1007/​s10701-012-9651-y

[29] Cédric Bény. Causal structure of the entanglement renormalization ansatz. New Journal of Physics, 15 (2): 023020, feb 2013. 10.1088/​1367-2630/​15/​2/​023020.
https:/​/​doi.org/​10.1088/​1367-2630/​15/​2/​023020

[30] B. Schumacher and R. F. Werner. Reversible quantum cellular automata. arXiv preprint quant-ph/​0405174. 2004.
arXiv:quant-ph/0405174

[31] Pablo Arrighi, Vincent Nesme, and Reinhard Werner. One-dimensional quantum cellular automata over finite, unbounded configurations. In International Conference on Language and Automata Theory and Applications, pages 64–75. Springer, 2008. 10.1007/​978-3-540-88282-4_8.
https:/​/​doi.org/​10.1007/​978-3-540-88282-4_8

[32] Pablo Arrighi, Renan Fargetton, Vincent Nesme, and Eric Thierry. Applying causality principles to the axiomatization of probabilistic cellular automata. In Conference on Computability in Europe, pages 1–10. Springer, 2011b. 10.1007/​978-3-642-21875-0_1.
https:/​/​doi.org/​10.1007/​978-3-642-21875-0_1

[33] Asif Shakeel and Peter J Love. When is a quantum cellular automaton (qca) a quantum lattice gas automaton (qlga)? Journal of Mathematical Physics, 54 (9): 092203, 2013. 10.1063/​1.4821640.
https:/​/​doi.org/​10.1063/​1.4821640

[34] Terence C. Farrelly and Anthony J. Short. Causal fermions in discrete space-time. Phys. Rev. A, 89: 012302, Jan 2014. 10.1103/​PhysRevA.89.012302.
https:/​/​doi.org/​10.1103/​PhysRevA.89.012302

[35] Giacomo Mauro D'Ariano and Paolo Perinotti. Derivation of the dirac equation from principles of information processing. Phys. Rev. A, 90: 062106, Dec 2014. 10.1103/​PhysRevA.90.062106.
https:/​/​doi.org/​10.1103/​PhysRevA.90.062106

[36] Alessandro Bisio, Giacomo Mauro D'Ariano, and Paolo Perinotti. Special relativity in a discrete quantum universe. Phys. Rev. A, 94: 042120, Oct 2016. 10.1103/​PhysRevA.94.042120.
https:/​/​doi.org/​10.1103/​PhysRevA.94.042120

[37] Pablo Arrighi and Simon Martiel. Quantum causal graph dynamics. Physical Review D, 96 (2): 024026, 2017. 10.1103/​PhysRevD.96.024026.
https:/​/​doi.org/​10.1103/​PhysRevD.96.024026

[38] Pablo Arrighi, Cédric Bény, and Terry Farrelly. A quantum cellular automaton for one-dimensional qed. Quantum Information Processing, 19 (3): 1–28, 2020. 10.1007/​s11128-019-2555-4.
https:/​/​doi.org/​10.1007/​s11128-019-2555-4

[39] Paolo Perinotti. Cellular automata in operational probabilistic theories. Quantum, 4: 294, July 2020. ISSN 2521-327X. 10.22331/​q-2020-07-09-294.
https:/​/​doi.org/​10.22331/​q-2020-07-09-294

[40] Samson Abramsky and Bob Coecke. A categorical semantics of quantum protocols. 2004. 10.1109/​LICS.2004.1319636.
https:/​/​doi.org/​10.1109/​LICS.2004.1319636

[41] Samson Abramsky and Ross Duncan. A categorical quantum logic. Mathematical Structures in Computer Science, 16 (3): 469–489, 2006. 10.1017/​S0960129506005275.
https:/​/​doi.org/​10.1017/​S0960129506005275

[42] Bob Coecke and Aleks Kissinger. Picturing Quantum Processes: A First Course in Quantum Theory and Diagrammatic Reasoning. Cambridge University Press, 2017. 10.1017/​9781316219317.
https:/​/​doi.org/​10.1017/​9781316219317

[43] Chris Heunen and Jamie Vicary. Categories for Quantum Theory: an introduction. Oxford University Press, USA, 2019. 10.1093/​oso/​9780198739623.001.0001.
https:/​/​doi.org/​10.1093/​oso/​9780198739623.001.0001

[44] Bob Coecke and Raymond Lal. Causal categories: relativistically interacting processes. Foundations of Physics, 43 (4): 458–501, 2013. 10.1007/​s10701-012-9646-8.
https:/​/​doi.org/​10.1007/​s10701-012-9646-8

[45] Aleks Kissinger, Matty Hoban, and Bob Coecke. Equivalence of relativistic causal structure and process terminality. https:/​/​arxiv.org/​abs/​1708.04118. 2017.
arXiv:1708.04118

[46] 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:/​/​doi.org/​10.1016/​0034-4877(72)90011-0.
https:/​/​doi.org/​10.1016/​0034-4877(72)90011-0

[47] Man-Duen Choi. Completely positive linear maps on complex matrices. Linear Algebra and its Applications, 10 (3): 285 – 290, 1975. ISSN 0024-3795. https:/​/​doi.org/​10.1016/​0024-3795(75)90075-0.
https:/​/​doi.org/​10.1016/​0024-3795(75)90075-0

[48] Sandu Popescu, Master's thesis, unpublished.

[49] H. Buhrman and S. Massar. Causality and tsirelson's bounds. Phys. Rev. A, 72: 052103, Nov 2005. 10.1103/​PhysRevA.72.052103.
https:/​/​doi.org/​10.1103/​PhysRevA.72.052103

[50] Robert Spekkens. Private communication.

[51] Yakir Aharonov and Lev Vaidman. The Two-State Vector Formalism: An Updated Review, pages 399–447. Springer Berlin Heidelberg, Berlin, Heidelberg, 2008. ISBN 978-3-540-73473-4. 10.1007/​978-3-540-73473-4_13.
https:/​/​doi.org/​10.1007/​978-3-540-73473-4_13

[52] Yakir Aharonov, Sandu Popescu, Jeff Tollaksen, and Lev Vaidman. Multiple-time states and multiple-time measurements in quantum mechanics. Phys. Rev. A, 79: 052110, May 2009. 10.1103/​PhysRevA.79.052110.
https:/​/​doi.org/​10.1103/​PhysRevA.79.052110

[53] Ralph Silva, Yelena Guryanova, Nicolas Brunner, Noah Linden, Anthony J. Short, and Sandu Popescu. Pre- and postselected quantum states: Density matrices, tomography, and kraus operators. Phys. Rev. A, 89: 012121, Jan 2014. 10.1103/​PhysRevA.89.012121.
https:/​/​doi.org/​10.1103/​PhysRevA.89.012121

[54] Yakir Aharonov, Sandu Popescu, and Jeff Tollaksen. Each instant of time a new universe. Springer, Milano, Milano, 2014. ISBN 978-88-470-5216-1. 10.1007/​978-88-470-5217-8_3.
https:/​/​doi.org/​10.1007/​978-88-470-5217-8_3

[55] Ralph Silva, Yelena Guryanova, Anthony J Short, Paul Skrzypczyk, Nicolas Brunner, and Sandu Popescu. Connecting processes with indefinite causal order and multi-time quantum states. New Journal of Physics, 19 (10): 103022, oct 2017. 10.1088/​1367-2630/​aa84fe.
https:/​/​doi.org/​10.1088/​1367-2630/​aa84fe

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

[57] Ognyan Oreshkov and Nicolas J Cerf. Operational quantum theory without predefined time. New Journal of Physics, 18 (7): 073037, jul 2016. 10.1088/​1367-2630/​18/​7/​073037.
https:/​/​doi.org/​10.1088/​1367-2630/​18/​7/​073037

[58] Ognyan Oreshkov and Christina Giarmatzi. Causal and causally separable processes. New Journal of Physics, 18 (9): 093020, sep 2016. 10.1088/​1367-2630/​18/​9/​093020.
https:/​/​doi.org/​10.1088/​1367-2630/​18/​9/​093020

[59] Felix A. Pollock, César Rodríguez-Rosario, Thomas Frauenheim, Mauro Paternostro, and Kavan Modi. Non-markovian quantum processes: Complete framework and efficient characterization. Phys. Rev. A, 97: 012127, Jan 2018a. 10.1103/​PhysRevA.97.012127.
https:/​/​doi.org/​10.1103/​PhysRevA.97.012127

[60] Felix A. Pollock, César Rodríguez-Rosario, Thomas Frauenheim, Mauro Paternostro, and Kavan Modi. Operational markov condition for quantum processes. Phys. Rev. Lett., 120: 040405, Jan 2018b. 10.1103/​PhysRevLett.120.040405.
https:/​/​doi.org/​10.1103/​PhysRevLett.120.040405

[61] Augustin Vanrietvelde, Hlér Kristjánsson, and Jonathan Barrett. Routed quantum circuits. https:/​/​arxiv.org/​abs/​2011.08120. 2020.
arXiv:2011.08120

[62] David J Reutter and Jamie Vicary. Shaded tangles for the design and verification of quantum circuits. Proceedings of the Royal Society A, 475 (2224): 20180338, 2019a. 10.1098/​rspa.2018.0338.
https:/​/​doi.org/​10.1098/​rspa.2018.0338

[63] David J Reutter and Jamie Vicary. Biunitary constructions in quantum information. Higher Structures, 3, 2019b.

[64] Jamie Vicary. Higher quantum theory. arXiv preprint arXiv:1207.4563. 2012.
arXiv:1207.4563

[65] Ross Duncan. Generalised Proof-Nets for Compact Categories with Biproducts, pages 70–134. Cambridge University Press, 2009. Preprint available at http:/​/​arxiv.org/​abs/​0903.5154.
arXiv:0903.5154

Cited by

[1] Paolo Perinotti, "Causal influence in operational probabilistic theories", Quantum 5, 515 (2021).

[2] Jonathan Barrett, Robin Lorenz, and Ognyan Oreshkov, "Quantum Causal Models", arXiv:1906.10726.

[3] Jonathan Barrett, Robin Lorenz, and Ognyan Oreshkov, "Cyclic quantum causal models", Nature Communications 12, 885 (2021).

[4] Wataru Yokojima, Marco Túlio Quintino, Akihito Soeda, and Mio Murao, "Consequences of preserving reversibility in quantum superchannels", arXiv:2003.05682.

[5] Augustin Vanrietvelde, Hlér Kristjánsson, and Jonathan Barrett, "Routed quantum circuits", arXiv:2011.08120.

[6] Pablo Arrighi, Christopher Cedzich, Marin Costes, Ulysse Rémond, and Benoît Valiron, "Addressable quantum gates", arXiv:2109.08050.

[7] Matt Wilson and Augustin Vanrietvelde, "Composable constraints", arXiv:2112.06818.

The above citations are from Crossref's cited-by service (last updated successfully 2022-01-23 15:07:46) and SAO/NASA ADS (last updated successfully 2022-01-23 15:07:47). The list may be incomplete as not all publishers provide suitable and complete citation data.