Graphical Methods in Device-Independent Quantum Cryptography

Spencer Breiner1, Carl A. Miller1,2, and Neil J. Ross2,3

1National Institute of Standards and Technology (NIST), Gaithersburg, MD 20899, USA
2Joint Center for Quantum Information and Computer Science (QuICS), University of Maryland, College Park, MD 20742, USA
3Department of Mathematics and Statistics, Dalhousie University, Halifax, NS B3H 4R2, Canada

We introduce a framework for graphical security proofs in device-independent quantum cryptography using the methods of categorical quantum mechanics. We are optimistic that this approach will make some of the highly complex proofs in quantum cryptography more accessible, facilitate the discovery of new proofs, and enable automated proof verification. As an example of our framework, we reprove a previous result from device-independent quantum cryptography: any linear randomness expansion protocol can be converted into an unbounded randomness expansion protocol. We give a graphical proof of this result, and implement part of it in the Globular proof assistant.

► BibTeX data

► References

[1] R. Penrose, in Combinatorial Mathematics and its Applications, edited by D. Welsh (Academic Press, New York, 1971) pp. 221-244.

[2] A. Joyal and R. Street, Advances in Mathematics 88, 55 (1991).
https://doi.org/10.1016/0001-8708(91)90003-P

[3] P. Selinger, ``A Survey of Graphical Languages for Monoidal Categories,'' in New Structures for Physics (Springer Berlin Heidelberg, Berlin, Heidelberg, 2011) pp. 289-355.
https://doi.org/10.1007/978-3-642-12821-9_4

[4] S. Abramsky and B. Coecke, in Proceedings of the 19th Annual IEEE Symposium on Logic in Computer Science (LICS 2004) (2004) pp. 415-425.
https://doi.org/10.1109/LICS.2004.1319636

[5] J. Vicary, in Proceedings of the 28th Annual ACM/​IEEE Symposium on Logic in Computer Science (LICS 2013) (2013) pp. 93-102.
https://doi.org/10.1109/LICS.2013.14

[6] N. Chancellor, A. Kissinger, S. Zohren, and D. Horsman, ``Coherent Parity Check Construction for Quantum Error Correction,'' (2016).
arXiv:1611.08012

[7] B. Coecke, ``From Quantum Foundations via Natural Language Meaning to a Theory of Everything,'' (2016).
arXiv:1602.07618

[8] B. Coecke and A. Kissinger, Picturing Quantum Processes: A First Course in Quantum Theory and Diagrammatic Reasoning (Cambridge University Press, 2017).
https://doi.org/10.1017/9781316219317

[9] M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information (Cambridge University Press, 2002).
https://doi.org/10.1017/CBO9780511976667

[10] B. Coecke and S. Perdrix, in Computer Science Logic: 24th International Workshop, CSL 2010, 19th Annual Conference of the EACSL, Brno, Czech Republic, August 23-27, 2010. Proceedings (Springer Berlin Heidelberg, Berlin, Heidelberg, 2010) pp. 230-244,.
https://doi.org/10.1007/978-3-642-15205-4_20
arXiv:1004.1598

[11] B. Coecke, Q. Wang, B. Wang, Y. Wang, and Q. Zhang, in Proceedings of the 6th International Workshop on Quantum Physics and Logic (QPL 2009) (2011) pp. 231 - 249.
https://doi.org/10.1016/j.entcs.2011.01.034

[12] A. Hillebrand, in Proceedings of the 8th International Workshop on Quantum Physics and Logic (QPL 2011) (2012) pp. 103-121.
https://doi.org/10.4204/EPTCS.95.10

[13] K.-M. Chung, Y. Shi, and X. Wu, ``Physical Randomness Extractors: Generating Random Numbers with Minimal Assumptions,'' (2014).
arXiv:1402.4797

[14] C. Heunen, Logical Methods in Computer Science 4, 4 (2008).
https://doi.org/10.2168/LMCS-4(4:9)2008

[15] U. Maurer and R. Renner, in Innovations in Computer Science (Tsinghua University Press, 2011) pp. 1-21.

[16] D. Pavlovic, in Categories and Types in Logic, Language, and Physics - Essays Dedicated to Jim Lambek on the Occasion of His 90th Birthday, Vol. 8222 (2014).
https://doi.org/10.1007/978-3-642-54789-8_19

[17] M. Stay and J. Vicary, Electronic Notes in Theoretical Computer Science 298, 367 (2013), proceedings of the Twenty-ninth Conference on the Mathematical Foundations of Programming Semantics, MFPS XXIX.
https://doi.org/10.1016/j.entcs.2013.09.022

[18] D. Mayers and A. Yao, in Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280) (1998) pp. 503-509.
https://doi.org/10.1109/SFCS.1998.743501

[19] R. Arnon-Friedman, F. Dupuis, O. Fawzi, R. Renner, and T. Vidick, Nature Communications 9, 459 (2018).
https://doi.org/10.1038/s41467-017-02307-4

[20] R. Arnon-Friedman, R. Renner, and T. Vidick, ``Simple and Tight Device-Independent Security Proofs,'' (2016),.
https://doi.org/10.1137/18M1174726
arXiv:1607.01797

[21] P. Bierhorst, E. Knill, S. Glancy, A. Mink, S. Jordan, A. Rommal, Y.-K. Liu, B. Christensen, S. W. Nam, and L. K. Shalm, ``Experimentally Generated Random Numbers Certified by the Impossibility of Superluminal Signaling,'' (2017).
arXiv:1702.05178

[22] R. Colbeck, ``Quantum And Relativistic Protocols For Secure Multi-Party Computation,'' Ph.D. thesis, University of York (2007).
arXiv:0911.3814

[23] M. Coudron and H. Yuen, in Proceedings of the Forty-sixth Annual ACM Symposium on Theory of Computing, STOC '14 (ACM, New York, NY, USA, 2014) pp. 427-436.
https://doi.org/10.1145/2591796.2591873

[24] F. Dupuis, O. Fawzi, and R. Renner, ``Entropy Accumulation,'' (2016).
arXiv:1607.01796

[25] S. Fehr, R. Gelles, and C. Schaffner, Physical Review A 87 (2011), 10.1103/​PhysRevA.87.012335.
https://doi.org/10.1103/PhysRevA.87.012335

[26] E. Knill, Y. Zhang, and H. Fu, ``Quantum probability estimation for randomness with quantum side information,'' (2018),.
arXiv:1806.04553

[27] C. A. Miller and Y. Shi, SIAM Journal on Computing 46, 1304 (2017).
https://doi.org/10.1137/15M1044333

[28] C. A. Miller and Y. Shi, Journal of the ACM 63, 33:1 (2016).
https://doi.org/10.1145/2885493

[29] S. Pironio, A. Acín, S. Massar, A. Boyer de la Giroday, D. Matsukevich, P. Maunz, S. Olmschenk, D. Hayes, L. Luo, T. A Manning, and C. Monroe, Nature 464, 1021 (2010).
https://doi.org/10.1038/nature09008

[30] S. Pironio and S. Massar, Physical Review A 87 (2011), 10.1103/​PhysRevA.87.012336.
https://doi.org/10.1103/PhysRevA.87.012336

[31] S. Aaronson, American Scientist 102, 266 (2014).
https://doi.org/10.1511/2014.109.266

[32] National Institute of Standards and Technology (NIST), ``Randomness Beacon Program,'' https:/​/​www.nist.gov/​programs-projects/​nist-randomness-beacon, accessed: 2019-02-01.
https:/​/​www.nist.gov/​programs-projects/​nist-randomness-beacon

[33] M. Coudron and H. Yuen, ``Infinite Randomness Expansion and Amplification with a Constant Number of Devices,'' (2013).
arXiv:1310.6755

[34] K. Bar, A. Kissinger, and J. Vicary, Logical Methods in Computer Science 14 (2018).
https://doi.org/10.23638/LMCS-14(1:8)2018

[35] Globular, ``Video,'' Available as ancillary material at arxiv1705.09213 (2019a), accessed: 2019-04-25.
arXiv:1705.09213

[36] B. Coecke and A. Kissinger, ``Categorical Quantum Mechanics I: Causal Quantum Processes,'' (2015).
arXiv:1510.05468

[37] B. Coecke and A. Kissinger, ``Categorical Quantum Mechanics II: Classical-Quantum Interaction,'' (2016).
arXiv:1605.08617

[38] A. Kissinger, S. Tull, and B. Westerbaan, ``Picture-perfect Quantum Key Distribution,'' (2017).
arXiv:1704.08668

[39] J. Watrous, The Theory of Quantum Information (Cambridge University Press, 2018).
https://doi.org/10.1017/9781316848142

[40] A. K. Ekert, Phys. Rev. Lett. 67, 661 (1991).
https://doi.org/10.1103/PhysRevLett.67.661

[41] U. Vazirani and T. Vidick, in Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing, STOC '12 (ACM, New York, NY, USA, 2012) pp. 61-76.
https://doi.org/10.1145/2213977.2213984

[42] Globular, ``Proof,'' http:/​/​globular.science/​1904.001 (2019b), accessed: 2019-04-25.
http:/​/​globular.science/​1904.001

[43] A. De, C. Portmann, T. Vidick, and R. Renner, SIAM Journal on Computing 41, 915 (2012).
https://doi.org/10.1137/100813683

[44] F. Bonchi, P. Soboci'nski, and F. Zanasi, in CONCUR 2014 - Concurrency Theory, Lecture Notes in Computer Science, Vol. 8704 (2014) pp. 435-450.
https://doi.org/10.1007/978-3-662-44584-6_30

[45] A. Kissinger and S. Uijlen, in Proceedings of the 32nd Annual ACM/​IEEE Symposium on Logic in Computer Science (LICS 2017) (2017) pp. 1-12.
https://doi.org/10.1109/LICS.2017.8005095

Cited by

[1] Spencer Breiner, Amir Kalev, and Carl A. Miller, "Parallel Self-Testing of the GHZ State with a Proof by Diagrams", arXiv:1806.04744.

The above citations are from SAO/NASA ADS (last updated 2019-06-18 12:20:09). 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 2019-06-18 12:20:07).