How to make unforgeable money in generalised probabilistic theories

John H. Selby and Jamie Sikora

Perimeter Institute for Theoretical Physics, Waterloo, Ontario, Canada, N2L 2Y5

We discuss the possibility of creating money that is physically impossible to counterfeit. Of course, "physically impossible" is dependent on the theory that is a faithful description of nature. Currently there are several proposals for quantum money which have their security based on the validity of quantum mechanics. In this work, we examine Wiesner's money scheme in the framework of generalised probabilistic theories. This framework is broad enough to allow for essentially any potential theory of nature, provided that it admits an operational description. We prove that under a quantifiable version of the no-cloning theorem, one can create physical money which has an exponentially small chance of being counterfeited. Our proof relies on cone programming, a natural generalisation of semidefinite programming. Moreover, we discuss some of the difficulties that arise when considering non-quantum theories.

► BibTeX data

► References

[1] Scott Aaronson and Paul Christiano. Quantum money from hidden subspaces. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 41-60. ACM, 2012. 10.1145/​2213977.2213983.
https://doi.org/10.1145/2213977.2213983

[2] Joonwoo Bae, Dai-Gyoung Kim, and Leong-Chuan Kwek. Structure of optimal state discrimination in generalized probabilistic theories. Entropy, 18 (2): 39, 2016. 10.3390/​e18020039.
https://doi.org/10.3390/e18020039

[3] Somshubhro Bandyopadhyay, Alessandro Cosentino, Nathaniel Johnston, Vincent Russo, John Watrous, and Nengkun Yu. Limitations on separable measurements by convex optimization. IEEE Transactions on Information Theory, 61 (6): 3593-3604, 2015. 10.1109/​TIT.2015.2417755.
https://doi.org/10.1109/TIT.2015.2417755

[4] Howard Barnum, Jonathan Barrett, Matthew Leifer, and Alexander Wilce. Generalized no-broadcasting theorem. Physical review letters, 99 (24): 240501, 2007. 10.1103/​PhysRevLett.99.240501.
https://doi.org/10.1103/PhysRevLett.99.240501

[5] Jonathan Barrett. Information processing in generalized probabilistic theories. Physical Review A, 75 (3): 032304, 2007. 10.1103/​PhysRevA.75.032304.
https://doi.org/10.1103/PhysRevA.75.032304

[6] Jonathan Barrett, Lucien Hardy, and Adrian Kent. No signaling and quantum key distribution. Physical review letters, 95 (1): 010503, 2005. 10.1007/​s11128-014-0880-1.
https://doi.org/10.1007/s11128-014-0880-1

[7] Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.

[8] Giulio Chiribella, Giacomo Mauro D'Ariano, and Paolo Perinotti. Probabilistic theories with purification. Physical Review A, 81 (6): 062348, 2010. 10.1103/​PhysRevA.81.062348.
https://doi.org/10.1103/PhysRevA.81.062348

[9] Bob Coecke. Terminality implies non-signalling. arXiv preprint arXiv:1405.3681, 2014.
arXiv:1405.3681

[10] Bob Coecke and Aleks Kissinger. Categorical quantum mechanics I: Causal quantum processes. arXiv preprint arXiv:1510.05468, 2015.
arXiv:1510.05468

[11] Bob Coecke and Aleks Kissinger. Picturing quantum processes. Cambridge University Press, 2017.

[12] E Brian Davies and John T Lewis. An operational approach to quantum probability. Communications in Mathematical Physics, 17 (3): 239-260, 1970. 10.1007/​BF01647093.
https://doi.org/10.1007/BF01647093

[13] Uriel Feige and László Lovász. Two-prover one-round proof systems: Their power and their problems. In Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, pages 733-744. ACM, 1992. 10.1145/​129712.129783.
https://doi.org/10.1145/129712.129783

[14] Samuel Fiorini, Serge Massar, Manas K Patra, and Hans Raj Tiwary. Generalized probabilistic theories and conic extensions of polytopes. Journal of Physics A: Mathematical and Theoretical, 48 (2): 025302, 2014. 10.1088/​1751-8113/​48/​2/​025302.
https://doi.org/10.1088/1751-8113/48/2/025302

[15] Dmitry Gavinsky. Quantum money with classical verification. In Computational Complexity (CCC), 2012 IEEE 27th Annual Conference on, pages 42-52. IEEE, 2012. 10.1063/​1.4903116.
https://doi.org/10.1063/1.4903116

[16] Sevag Gharibian, Jamie Sikora, and Sarvagya Upadhyay. QMA variants with polynomially many provers. Quantum Information & Computation, 13 (1&2): 0135-0157, 2013.

[17] Lucien Hardy. Quantum theory from five reasonable axioms. arXiv preprint arXiv:quant-ph/​0101012, 2001.
arXiv:quant-ph/0101012

[18] Lucien Hardy. Reformulating and reconstructing quantum theory. arXiv preprint arXiv:1104.2066, 2011.
arXiv:1104.2066

[19] Anna Jenčová and Martin Plávala. Conditions on the existence of maximally incompatible two-outcome measurements in general probabilistic theory. Physical Review A, 96: 022113, 2017. 10.1103/​PhysRevA.96.022113.
https://doi.org/10.1103/PhysRevA.96.022113

[20] Aleks Kissinger, Matty Hoban, and Bob Coecke. Equivalence of relativistic causal structure and process terminality. arXiv preprint arXiv:1708.04118, 2017.
arXiv:1708.04118

[21] Ludovico Lami, Carlos Palazuelos, and Andreas Winter. Ultimate data hiding in quantum mechanics and beyond. Communications in Mathematical Physics, pages 1-48, 2017. 10.1007/​s00220-018-3154-4.
https://doi.org/10.1007/s00220-018-3154-4

[22] Monique Laurent and Teresa Piovesan. Conic approach to quantum graph parameters using linear optimization over the completely positive semidefinite cone. Siam J. Optim., 25 (4): 2461-2493, 2015. 10.1137/​14097865X.
https://doi.org/10.1137/14097865X

[23] G. Ludwig. An Axiomatic Basis of Quantum Mechanics. 1. Derivation of Hilbert Space. Springer-Verlag, 1985.

[24] G. W. Mackey. The mathematical foundations of quantum mechanics. W. A. Benjamin, New York, 1963.

[25] Abel Molina, Thomas Vidick, and John Watrous. Optimal counterfeiting attacks and generalizations for Wiesner's quantum money. In Proceedings of the 7th Conference on Theory of Quantum Computation, Communication, and Cryptography, volume 7582 of Lecture Notes in Computer Science, pages 45-64, 2013. 10.1007/​978-3-642-35656-8_4.
https://doi.org/10.1007/978-3-642-35656-8_4

[26] Ashwin Nayak, Jamie Sikora, and Levent Tunçel. A search for quantum coin-flipping protocols using optimization techniques. Mathematical Programming, 156 (1-2): 581-613, 2016. 10.1007/​s10107-015-0909-y.
https://doi.org/10.1007/s10107-015-0909-y

[27] C. Piron. Axiomatique quantique. Helvetia Physica Acta, 37: 439-468, 1964.

[28] CH Randall and DJ Foulis. An approach to empirical logic. The American Mathematical Monthly, 77 (4): 363-374, 1970. 10.2307/​2316143.
https://doi.org/10.2307/2316143

[29] John H Selby. A process theoretic triptych. PhD thesis, Imperial College London, 2017.

[30] John H Selby, Carlo Maria Scandolo, and Bob Coecke. Reconstructing quantum theory from diagrammatic postulates. arXiv preprint arXiv:1802.00367, 2018.
arXiv:1802.00367

[31] Jamie Sikora and John H Selby. A simple proof of the impossibility of bit-commitment in generalised probabilistic theories using cone programming. Physical Review A, 97: 042302, 2018. 10.1103/​PhysRevA.97.042302.
https://doi.org/10.1103/PhysRevA.97.042302

[32] Jamie Sikora and Antonios Varvitsiotis. Linear conic formulations for two-party correlations and values of nonlocal games. Mathematical Programming, 162 (1-2): 431-463, 2017. 10.1007/​s10107-016-1049-8.
https://doi.org/10.1007/s10107-016-1049-8

[33] Stephen Wiesner. Conjugate coding. SIGACT News, 15 (1): 78-88, 1983. 10.1145/​1008908.1008920.
https://doi.org/10.1145/1008908.1008920

► Cited by (beta)

Crossref's cited-by service has no data on citing works. Unfortunately not all publishers provide suitable citation data.