The Min-Entropy of Classical-Quantum Combs for Measurement-Based Applications

Isaac D. Smith, Marius Krumm, Lukas J. Fiderer, Hendrik Poulsen Nautrup, and Hans J. Briegel

Institute for Theoretical Physics, UIBK, 6020 Innsbruck, Austria

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


Learning a hidden property of a quantum system typically requires a series of interactions. In this work, we formalise such multi-round learning processes using a generalisation of classical-quantum states, called classical-quantum combs. Here, "classical" refers to a random variable encoding the hidden property to be learnt, and "quantum" refers to the quantum comb describing the behaviour of the system. The optimal strategy for learning the hidden property can be quantified by applying the comb min-entropy (Chiribella and Ebler, NJP, 2016) to classical-quantum combs. To demonstrate the power of this approach, we focus attention on an array of problems derived from measurement-based quantum computation (MBQC) and related applications. Specifically, we describe a known blind quantum computation (BQC) protocol using the combs formalism and thereby leverage the min-entropy to provide a proof of single-shot security for multiple rounds of the protocol, extending the existing result in the literature. Furthermore, we consider a range of operationally motivated examples related to the verification of a partially unknown MBQC device. These examples involve learning the features of the device necessary for its correct use, including learning its internal reference frame for measurement calibration. We also introduce a novel connection between MBQC and quantum causal models that arises in this context.

Imagine you have a machine in front of you, covered in buttons and displays. You know something about this machine, but not everything: you know that the internal workings are in one of a set of possible configurations, but not which one. Your job is to try and learn this configuration by sequentially pressing buttons and observing display output. Is it possible to learn the internal workings of the machine exactly? This paper considers this type of scenario in a quantum information-theoretic setting. Instead of buttons and displays, the machine receives and outputs quantum states. The different configurations are described by different quantum operators (called quantum combs) and the machine is described by an ensemble of these operators indexed by a random variable (called a classical-quantum comb). Using an entropic quantity (the comb min-entropy) it is possible to quantify how well the configuration of the machine can be learnt under an optimal sequence of interactions. This technique is applied to two applications within quantum computing: to verify aspects of a quantum computing device (the machine represents the computing device) and to analyse the security of a cryptographic quantum computing protocol (the machine represents a client of a quantum computing service).

► BibTeX data

► References

[1] John Preskill ``Quantum Computing in the NISQ era and beyond'' Quantum 2, 79 (2018).

[2] H.-J. Briegel, W. Dür, J. I. Cirac, and P. Zoller, ``Quantum Repeaters: The Role of Imperfect Local Operations in Quantum Communication'' Phys. Rev. Lett. 81, 5932–5935 (1998).

[3] Rodney Van Meter ``Quantum Networking'' ISTE Ltd/​John Wiley Sons Inc, Hoboken, NJ (2014).

[4] Davide Castelvecchi ``The quantum internet has arrived (and it hasn't).'' Nature 554, 289–293 (2018).

[5] Sheng-Kai Liao, Wen-Qi Cai, Johannes Handsteiner, Bo Liu, Juan Yin, Liang Zhang, Dominik Rauch, Matthias Fink, Ji-Gang Ren, and Wei-Yue Liu, ``Satellite-relayed intercontinental quantum network'' Physical review letters 120, 030501 (2018).

[6] CT Nguyen, DD Sukachev, MK Bhaskar, Bartholomeus Machielse, DS Levonian, EN Knall, Pavel Stroganov, Ralf Riedinger, Hongkun Park, and M Lončar, ``Quantum network nodes based on diamond qubits with an efficient nanophotonic interface'' Physical review letters 123, 183602 (2019).

[7] Peter C Humphreys, Norbert Kalb, Jaco PJ Morits, Raymond N Schouten, Raymond FL Vermeulen, Daniel J Twitchen, Matthew Markham, and Ronald Hanson, ``Deterministic delivery of remote entanglement on a quantum network'' Nature 558, 268–273 (2018).

[8] Boris Korzh, Charles Ci Wen Lim, Raphael Houlmann, Nicolas Gisin, Ming Jun Li, Daniel Nolan, Bruno Sanguinetti, Rob Thew, and Hugo Zbinden, ``Provably secure and practical quantum key distribution over 307 km of optical fibre'' Nature Photonics 9, 163–168 (2015).

[9] Rachel Courtland ``China's 2,000-km quantum link is almost complete'' IEEE Spectrum 53, 11–12 (2016).

[10] Mohamed Elboukhari, Mostafa Azizi, and Abdelmalek Azizi, ``Quantum Key Distribution Protocols: A Survey.'' International Journal of Universal Computer Science 1 (2010).

[11] Angela Sara Cacciapuoti, Marcello Caleffi, Francesco Tafuri, Francesco Saverio Cataliotti, Stefano Gherardini, and Giuseppe Bianchi, ``Quantum internet: networking challenges in distributed quantum computing'' IEEE Network 34, 137–143 (2019).

[12] Quantum Internet Alliance https:/​/​ (2022).

[13] Antonio Acín, Immanuel Bloch, Harry Buhrman, Tommaso Calarco, Christopher Eichler, Jens Eisert, Daniel Esteve, Nicolas Gisin, Steffen J Glaser, Fedor Jelezko, Stefan Kuhr, Maciej Lewenstein, Max F Riedel, Piet O Schmidt, Rob Thew, Andreas Wallraff, Ian Walmsley, and Frank K Wilhelm, ``The quantum technologies roadmap: a European community view'' New Journal of Physics 20, 080201 (2018).

[14] Robert Beals, Stephen Brierley, Oliver Gray, Aram W Harrow, Samuel Kutin, Noah Linden, Dan Shepherd, and Mark Stather, ``Efficient distributed quantum computing'' Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 469, 20120686 (2013).

[15] Vasil S Denchevand Gopal Pandurangan ``Distributed quantum computing: A new frontier in distributed systems or science fiction?'' ACM SIGACT News 39, 77–95 (2008).

[16] Rene Allerstorfer, Harry Buhrman, Florian Speelman, and Philip Verduyn Lunel, ``On the Role of Quantum Communication and Loss in Attacks on Quantum Position Verification'' arXiv:2208.04341 (2022).

[17] Joseph F Fitzsimons ``Private quantum computation: an introduction to blind quantum computing and related protocols'' npj Quantum Information 3, 1–11 (2017).

[18] Giulio Chiribella, Giacomo Mauro D’Ariano, and Paolo Perinotti, ``Theoretical framework for quantum networks'' Physical Review A 80, 022339 (2009).

[19] Giulio Chiribella, G Mauro D’Ariano, and Paolo Perinotti, ``Quantum circuit architecture'' Physical review letters 101, 060401 (2008).

[20] Michael A. Nielsenand Isaac L. Chuang ``Quantum Computation and Quantum Information: 10th Anniversary Edition'' Cambridge University Press (2010).

[21] Felix A Pollock, César Rodríguez-Rosario, Thomas Frauenheim, Mauro Paternostro, and Kavan Modi, ``Non-Markovian quantum processes: Complete framework and efficient characterization'' Physical Review A 97, 012127 (2018).

[22] Giulio Chiribellaand Daniel Ebler ``Optimal quantum networks and one-shot entropies'' New Journal of Physics 18, 093053 (2016).

[23] Robert Konig, Renato Renner, and Christian Schaffner, ``The operational meaning of min-and max-entropy'' IEEE Transactions on Information theory 55, 4337–4347 (2009).

[24] Renato Renner ``Security of quantum key distribution'' International Journal of Quantum Information 6, 1–127 (2008).

[25] Mark M. Wilde ``Quantum Information Theory'' Cambridge University Press (2017).

[26] Robert Raussendorfand Hans J Briegel ``A one-way quantum computer'' Physical review letters 86, 5188 (2001).

[27] Hans J Briegel, Daniel E Browne, Wolfgang Dür, Robert Raussendorf, and Maarten Van den Nest, ``Measurement-based quantum computation'' Nature Physics 5, 19–26 (2009).

[28] Robert Raussendorf, Daniel E Browne, and Hans J Briegel, ``Measurement-based quantum computation on cluster states'' Physical review A 68, 022312 (2003).

[29] Robert Raussendorfand Hans Briegel ``Computational model underlying the one-way quantum computer'' arXiv preprint quant-ph/​0108067 (2001).

[30] Richard Jozsa ``An introduction to measurement based quantum computation'' NATO Science Series, III: Computer and Systems Sciences. Quantum Information Processing-From Theory to Experiment 199, 137–158 (2006).

[31] D Grossand J Eisert ``Novel schemes for measurement-based quantum computation'' Physical review letters 98, 220503 (2007).

[32] Hans J Briegeland Robert Raussendorf ``Persistent entanglement in arrays of interacting particles'' Physical Review Letters 86, 910 (2001).

[33] Marc Hein, Wolfgang Dür, Jens Eisert, Robert Raussendorf, M Van den Nest, and H J Briegel, ``Entanglement in graph states and its applications'' arXiv preprint quant-ph/​0602096 (2006).

[34] Marc Hein, Wolfgang Dür, Jens Eisert, Robert Raussendorf, M Van den Nest, and H J Briegel, ``Entanglement in graph states and its applications'' Volume 162: Quantum Computers, Algorithms and Chaos 115–218 (2006).

[35] Marc Hein, Jens Eisert, and Hans J Briegel, ``Multiparty entanglement in graph states'' Physical Review A 69, 062311 (2004).

[36] Mehdi Mhalla, Mio Murao, Simon Perdrix, Masato Someya, and Peter S Turner, ``Which graph states are useful for quantum information processing?'' Conference on Quantum Computation, Communication, and Cryptography 174–187 (2011).

[37] 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).

[38] Vincent Danosand Elham Kashefi ``Determinism in the one-way model'' Physical Review A 74, 052310 (2006).

[39] Damian Markhamand Elham Kashefi ``Entanglement, flow and classical simulatability in measurement based quantum computation'' Springer (2014).

[40] Vincent Danos, Elham Kashefi, and Prakash Panangaden, ``The measurement calculus'' Journal of the ACM (JACM) 54, 8–es (2007).

[41] Maarten Van den Nest, Jeroen Dehaene, and Bart De Moor, ``Graphical description of the action of local Clifford transformations on graph states'' Physical Review A 69, 022316 (2004).

[42] Maarten Van den Nest, Jeroen Dehaene, and Bart De Moor, ``Local unitary versus local Clifford equivalence of stabilizer states'' Physical Review A 71, 062323 (2005).

[43] Philip Walther, Kevin J Resch, Terry Rudolph, Emmanuel Schenck, Harald Weinfurter, Vlatko Vedral, Markus Aspelmeyer, and Anton Zeilinger, ``Experimental one-way quantum computing'' Nature 434, 169–176 (2005).

[44] Robert Raussendorf, Jim Harrington, and Kovid Goyal, ``Topological fault-tolerance in cluster state quantum computation'' New Journal of Physics 9, 199 (2007).

[45] M. S. Tame, R. Prevedel, M. Paternostro, P. Böhi, M. S. Kim, and A. Zeilinger, ``Experimental Realization of Deutsch's Algorithm in a One-Way Quantum Computer'' Phys. Rev. Lett. 98, 140501 (2007).

[46] Anne Broadbent, Joseph Fitzsimons, and Elham Kashefi, ``Universal blind quantum computation'' 2009 50th Annual IEEE Symposium on Foundations of Computer Science 517–526 (2009).

[47] Atul Mantri, Tommaso F Demarie, Nicolas C Menicucci, and Joseph F Fitzsimons, ``Flow ambiguity: A path towards classically driven blind quantum computation'' Physical Review X 7, 031004 (2017).

[48] Tomoyuki Morimaeand Keisuke Fujii ``Blind quantum computation protocol in which Alice only makes measurements'' Physical Review A 87, 050301 (2013).

[49] Tomoyuki Morimae ``Verification for measurement-only blind quantum computing'' Physical Review A 89, 060302 (2014).

[50] Christopher Portmannand Renato Renner ``Security in quantum cryptography'' Reviews of Modern Physics 94, 025008 (2022).

[51] Jonathan Barrett, Robin Lorenz, and Ognyan Oreshkov, ``Quantum causal models'' arXiv preprint arXiv:1906.10726 (2019).

[52] Fabio Costaand Sally Shrapnel ``Quantum causal modelling'' New Journal of Physics 18, 063032 (2016).

[53] John-Mark A Allen, Jonathan Barrett, Dominic C Horsman, Ciarán M Lee, and Robert W Spekkens, ``Quantum common causes and quantum causal models'' Physical Review X 7, 031021 (2017).

[54] Katja Ried, Megan Agnew, Lydia Vermeyden, Dominik Janzing, Robert W Spekkens, and Kevin J Resch, ``A quantum advantage for inferring causal structure'' Nature Physics 11, 414–420 (2015).

[55] Joseph F Fitzsimons, Jonathan A Jones, and Vlatko Vedral, ``Quantum correlations which imply causation'' Scientific reports 5, 1–7 (2015).

[56] Giulio Chiribellaand Daniel Ebler ``Quantum speedup in the identification of cause–effect relations'' Nature communications 10, 1–8 (2019).

[57] Jonas M Küblerand Daniel Braun ``Two-qubit causal structures and the geometry of positive qubit-maps'' New Journal of Physics 20, 083015 (2018).

[58] Man-Duen Choi ``Completely positive linear maps on complex matrices'' Linear algebra and its applications 10, 285–290 (1975).

[59] Andrzej Jamiołkowski ``Linear transformations which preserve trace and positive semidefiniteness of operators'' Reports on Mathematical Physics 3, 275–278 (1972).

[60] Heinz-Peter Breuerand Francesco Petruccione ``The theory of open quantum systems'' Oxford University Press, USA (2002).

[61] Philip Pechukas ``Reduced Dynamics Need Not Be Completely Positive'' Phys. Rev. Lett. 73, 1060–1062 (1994).

[62] Robert Alicki ``Comment on ``Reduced Dynamics Need Not Be Completely Positive'''' Phys. Rev. Lett. 75, 3020–3020 (1995).

[63] Philip Pechukas ``Pechukas Replies:'' Phys. Rev. Lett. 75, 3021–3021 (1995).

[64] Antoine Royer ``Reduced Dynamics with Initial Correlations, and Time-Dependent Environment and Hamiltonians'' Phys. Rev. Lett. 77, 3272–3275 (1996).

[65] Simon Milz, Felix A Pollock, and Kavan Modi, ``An introduction to operational quantum dynamics'' Open Systems & Information Dynamics 24, 1740016 (2017).

[66] Gus Gutoskiand John Watrous ``Toward a general theory of quantum games'' Proceedings of the thirty-ninth annual ACM symposium on Theory of computing 565–574 (2007).

[67] Ognyan Oreshkov, Fabio Costa, and Časlav Brukner, ``Quantum correlations with no causal order'' Nature communications 3, 1–8 (2012).

[68] Jonathan Barrett, Robin Lorenz, and Ognyan Oreshkov, ``Cyclic quantum causal models'' Nature communications 12, 1–15 (2021).

[69] Giacomo Mauro D’Ariano ``Causality re-established'' Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences 376, 20170313 (2018).

[70] Alexander S Holevo ``Probabilistic and statistical aspects of quantum theory'' Edizioni della Normale Pisa (2011).

[71] A. S. Holevo ``Statistical problems in quantum physics'' Proceedings of the Second Japan-USSR Symposium on Probability Theory 104–119 (1973).

[72] Carl W Helstrom ``Detection theory and quantum mechanics'' Information and Control 10, 254–291 (1967).

[73] Alexander S Holevo ``Statistical decision theory for quantum systems'' Journal of multivariate analysis 3, 337–394 (1973).

[74] Simon Milz, Dario Egloff, Philip Taranto, Thomas Theurer, Martin B. Plenio, Andrea Smirne, and Susana F. Huelga, ``When Is a Non-Markovian Quantum Process Classical?'' Phys. Rev. X 10, 041049 (2020).

[75] Marco Tomamichel, Roger Colbeck, and Renato Renner, ``A fully quantum asymptotic equipartition property'' IEEE Transactions on information theory 55, 5840–5847 (2009).

[76] Marco Tomamichel ``Quantum information processing with finite resources: mathematical foundations'' Springer (2015).

[77] H. Yuen, R. Kennedy, and M. Lax, ``Optimum testing of multiple hypotheses in quantum detection theory'' IEEE Transactions on Information Theory 21, 125–134 (1975).

[78] Johannes Jakob Meyer, Sumeet Khatri, Daniel Stilck França, Jens Eisert, and Philippe Faist, ``Quantum metrology in the finite-sample regime'' arXiv preprint arXiv:2307.06370 (2023).

[79] Daniel Gottesman ``Stabilizer codes and quantum error correction'' California Institute of Technology (1997).

[80] Mehdi Mhallaand Simon Perdrix ``Finding optimal flows efficiently'' International Colloquium on Automata, Languages, and Programming 857–868 (2008).

[81] Niel De Beaudrap ``Finding flows in the one-way measurement model'' Physical Review A 77, 022328 (2008).

[82] 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, 3277–3305 (2017).

[83] Ueli Maurer ``Abstract models of computation in cryptography'' IMA International Conference on Cryptography and Coding 1–12 (2005).

[84] Atul Mantri, Tommaso F Demarie, and Joseph F Fitzsimons, ``Universality of quantum computation with cluster states and (X, Y)-plane measurements'' Scientific reports 7, 1–7 (2017).

[85] Charles H Bennettand Gilles Brassard ``Quantum cryptography: Public key distribution and coin tossing'' Theoretical computer science 560, 7–11 (2014).

[86] Artur K. Ekert ``Quantum cryptography based on Bell's theorem'' Phys. Rev. Lett. 67, 661–663 (1991).

[87] John Watrous ``The theory of quantum information'' Cambridge university press (2018).

[88] Michael Ben-Or, Michał Horodecki, Debbie W Leung, Dominic Mayers, and Jonathan Oppenheim, ``The universal composable security of quantum key distribution'' Theory of Cryptography: Second Theory of Cryptography Conference, TCC 2005, Cambridge, MA, USA, February 10-12, 2005. Proceedings 2 386–406 (2005).

[89] Renato Rennerand Robert König ``Universally composable privacy amplification against quantum adversaries'' Theory of Cryptography Conference 407–425 (2005).

[90] A Yu Kitaev ``Quantum measurements and the Abelian stabilizer problem'' arXiv preprint quant-ph/​9511026 (1995).

[91] Jessica Bavaresco, Patryk Lipka-Bartosik, Pavel Sekatski, and Mohammad Mehboudi, ``Designing optimal protocols in Bayesian quantum parameter estimation with higher-order operations'' arXiv preprint arXiv:2311.01513 (2023).

[92] Stephen D Bartlett, Terry Rudolph, and Robert W Spekkens, ``Reference frames, superselection rules, and quantum information'' Reviews of Modern Physics 79, 555 (2007).

[93] Judea Pearl ``Causality'' Cambridge University Press (2009).

[94] Peter Spirtes, Clark N Glymour, Richard Scheines, and David Heckerman, ``Causation, prediction, and search'' MIT press (2000).

[95] Bernhard Schölkopf, Dominik Janzing, Jonas Peters, Eleni Sgouritsa, Kun Zhang, and Joris Mooij, ``On causal and anticausal learning'' arXiv preprint arXiv:1206.6471 (2012).

[96] Christopher J Woodand 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, 033002 (2015).

[97] Robin Lorenzand Jonathan Barrett ``Causal and compositional structure of unitary transformations'' Quantum 5, 511 (2021).

[98] Nick Ormrod, Augustin Vanrietvelde, and Jonathan Barrett, ``Causal structure in the presence of sectorial constraints, with application to the quantum switch'' Quantum 7, 1028 (2023).

[99] Mingdi Huand Yuexian Hou ``Discrimination between quantum common causes and quantum causality'' Physical Review A 97, 062125 (2018).

[100] Christoph Hirche ``Quantum network discrimination'' Quantum 7, 1064 (2023).

[101] Isaac D. Smithand Marius Krumm ``Min-Entropy and MBQC''.

[102] Steven Diamondand Stephen Boyd ``CVXPY: A Python-embedded modeling language for convex optimization'' Journal of Machine Learning Research 17, 1–5 (2016).

[103] Akshay Agrawal, Robin Verschueren, Steven Diamond, and Stephen Boyd, ``A rewriting system for convex optimization problems'' Journal of Control and Decision 5, 42–60 (2018).

[104] Brendan O'Donoghue, Eric Chu, Neal Parikh, and Stephen Boyd, ``Conic Optimization via Operator Splitting and Homogeneous Self-Dual Embedding'' Journal of Optimization Theory and Applications 169, 1042–1068 (2016).

Cited by

On Crossref's cited-by service no data on citing works was found (last attempt 2024-06-22 12:48:00). On SAO/NASA ADS no data on citing works was found (last attempt 2024-06-22 12:48:01).