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 recent result from device-independent quantum cryptography: any linear randomness expansion protocol can be converted into an unbounded randomness expansion protocol. We give a graphical exposition of a proof of this result and implement parts of it in the Globular proof assistant.

}, doi = {https://doi.org/10.22331/q-2019-05-27-146}, url = {https://arxiv.org/abs/1705.09213}, author = {Spencer Breiner and Carl Miller and Neil J. Ross} } @article {2223, title = {Parallel Self-Testing of the GHZ State with a Proof by Diagrams}, journal = {EPTCS }, volume = {287}, year = {2019}, month = {01/29/2019}, pages = {43-66}, abstract = {Quantum self-testing addresses the following question: is it possible to verify the existence of a multipartite state even when one\&$\#$39;s measurement devices are completely untrusted? This problem has seen abundant activity in the last few years, particularly with the advent of parallel self-testing (i.e., testing several copies of a state at once), which has applications not only to quantum cryptography but also quantum computing. In this work we give the first error-tolerant parallel self-test in a three-party (rather than two-party) scenario, by showing that an arbitrary number of copies of the GHZ state can be self-tested. In order to handle the additional complexity of a three-party setting, we use a diagrammatic proof based on categorical quantum mechanics, rather than a typical symbolic proof. The diagrammatic approach allows for manipulations of the complicated tensor networks that arise in the proof, and gives a demonstration of the importance of picture-languages in quantum information.

}, doi = {https://doi.org/10.4204/EPTCS.287.3}, url = {https://arxiv.org/abs/1806.04744}, author = {Spencer Breiner and Amir Kalev and Carl Miller} } @article {1994, title = {Keyring models: an approach to steerability}, journal = {Journal of Mathematical Physics}, volume = {59}, year = {2018}, month = {2018/01/02}, pages = {022103}, abstract = {If a measurement is made on one half of a bipartite system then, conditioned on the outcome, the other half has a new reduced state. If these reduced states defy classical explanation \— that is, if shared randomness cannot produce these reduced states for all possible measurements \— the bipartite state is said to be steerable. Determining which states are steerable is a challenging problem even for low dimensions. In the case of two-qubit systems a criterion is known for T-states (that is, those with maximally mixed marginals) under projective measurements. In the current work we introduce the concept of keyring models \— a special class of local hidden state model. When the measurements made correspond to real projectors, these allow us to study steerability beyond T-states. Using keyring models, we completely solve the steering problem for real projective measurements when the state arises from mixing a pure two-qubit state with uniform noise. We also give a partial solution in the case when the uniform noise is replaced by independent depolarizing channels. Our results imply that Werner states, which are a special case of the previous states, are unsteerable under real projective measurements if and only if their efficiency is at most 2/π.

}, doi = {10.1063/1.5006199}, url = {http://aip.scitation.org/doi/full/10.1063/1.5006199}, author = {Carl Miller and Roger Colbeck and Yaoyun Shi} } @article {2222, title = {Local randomness: Examples and application}, journal = {Phys. Rev. A}, year = {2018}, month = {03/2018}, pages = {032324}, abstract = {When two players achieve a superclassical score at a nonlocal game, their outputs must contain intrinsic randomness. This fact has many useful implications for quantum cryptography. Recently it has been observed [C. Miller and Y. Shi, Quantum Inf. Computat. 17, 0595 (2017)] that such scores also imply the existence of local randomness\—that is, randomness known to one player but not to the other. This has potential implications for cryptographic tasks between two cooperating but mistrustful players. In the current paper we bring this notion toward practical realization, by offering near-optimal bounds on local randomness for the CHSH game, and also proving the security of a cryptographic application of local randomness (single-bit certified deletion).

}, doi = {https://doi.org/10.1103/PhysRevA.97.032324}, url = {https://arxiv.org/abs/1708.04338}, author = {Honghao Fu and Carl Miller} } @article {1951, title = {Parallel Device-Independent Quantum Key Distribution}, year = {2017}, month = {2017/03/15}, abstract = {A prominent application of quantum cryptography is the distribution of cryptographic keys with unconditional security. Recently, such security was extended by Vazirani and Vidick (Physical Review Letters, 113, 140501, 2014) to the device-independent (DI) scenario, where the users do not need to trust the integrity of the underlying quantum devices. The protocols analyzed by them and by subsequent authors all require a sequential execution of N multiplayer games, where N is the security parameter. In this work, we prove unconditional security of a protocol where all games are executed in parallel. Our result further reduces the requirements for QKD (allowing for arbitrary information leakage within each players\&$\#$39; lab) and opens the door to more efficient implementation. To the best of our knowledge, this is the first parallel security proof for a fully device-independent QKD protocol. Our protocol tolerates a constant level of device imprecision and achieves a linear key rate.

}, url = {https://arxiv.org/abs/1703.05426}, author = {Rahul Jain and Carl Miller and Yaoyun Shi} } @article {1982, title = {Randomness in nonlocal games between mistrustful players}, journal = {Quantum Information and Computation}, volume = {17}, year = {2017}, month = {2017/06/15}, pages = {0595-0610}, abstract = {If two quantum players at a nonlocal game G achieve a superclassical score, then their measurement outcomes must be at least partially random from the perspective of any third player. This is the basis for device-independent quantum cryptography. In this paper we address a related question: does a superclassical score at G guarantee that one player has created randomness from the perspective of the other player? We show that for complete-support games, the answer is yes: even if the second player is given the first player\&$\#$39;s input at the conclusion of the game, he cannot perfectly recover her output. Thus some amount of local randomness (i.e., randomness possessed by only one player) is always obtained when randomness is certified from nonlocal games with quantum strategies. This is in contrast to non-signaling game strategies, which may produce global randomness without any local randomness. We discuss potential implications for cryptographic protocols between mistrustful parties.

}, url = {https://arxiv.org/abs/1706.04984}, author = {Carl Miller and Yaoyun Shi} } @article {1996, title = {Rigidity of the magic pentagram game}, journal = {Quantum Science and Technology}, volume = {3}, year = {2017}, month = {2017/11/02}, pages = {015002}, abstract = {A game is rigid if a near-optimal score guarantees, under the sole assumption of the validity of quantum mechanics, that the players are using an approximately unique quantum strategy. Rigidity has a vital role in quantum cryptography as it permits a strictly classical user to trust behavior in the quantum realm. This property can be traced back as far as 1998 (Mayers and Yao) and has been proved for multiple classes of games. In this paper we prove ridigity for the magic pentagram game, a simple binary constraint satisfaction game involving two players, five clauses and ten variables. We show that all near-optimal strategies for the pentagram game are approximately equivalent to a unique strategy involving real Pauli measurements on three maximally-entangled qubit pairs.

}, url = {http://iopscience.iop.org/article/10.1088/2058-9565/aa931d/meta}, author = {Amir Kalev and Carl Miller} } @article {2036, title = {Universal Security for Randomness Expansion from the Spot-Checking Protocol}, journal = {SIAM Journal on Computing}, volume = {46}, year = {2017}, month = {2017/08/01}, abstract = {Colbeck (Thesis, 2006) proposed using Bell inequality violations to generate certified random numbers. While full quantum-security proofs have been given, it remains a major open problem to identify the broadest class of Bell inequalities and lowest performance requirements to achieve such security. In this paper, working within the broad class of spot-checking protocols, we prove exactly which Bell inequality violations can be used to achieve full security. Our result greatly improves the known noise tolerance for secure randomness expansion: for the commonly used CHSH game, full security was only known with a noise tolerance of 1.5\%, and we improve this to 10.3\%. We also generalize our results beyond Bell inequalities and give the first security proof for randomness expansion based on Kochen-Specker inequalities. The central technical contribution of the paper is a new uncertainty principle for the Schatten norm, which is based on the uniform convexity inequality of Ball, Carlen, and Lieb (Inventiones mathematicae, 115:463-482, 1994).

}, doi = {10.1137/15M1044333}, url = {http://epubs.siam.org/doi/10.1137/15M1044333}, author = {Carl Miller and Yaoyun Shi} } @article {1883, title = {Robust Protocols for Securely Expanding Randomness and Distributing Keys Using Untrusted Quantum Devices}, journal = {Journal of the ACM}, volume = {63}, year = {2016}, month = {2016/10/26}, pages = {33:1{\textendash}33:63}, abstract = {Randomness is a vital resource for modern-day information processing, especially for cryptography. A wide range of applications critically rely on abundant, high-quality random numbers generated securely. Here, we show how to expand a random seed at an exponential rate without trusting the underlying quantum devices. Our approach is secure against the most general adversaries, and has the following new features: cryptographic level of security, tolerating a constant level of imprecision in devices, requiring only unit size quantum memory (for each device component) in an honest implementation, and allowing a large natural class of constructions for the protocol. In conjunction with a recent work by Chung et al. [2014], it also leads to robust unbounded expansion using just 2 multipart devices. When adapted for distributing cryptographic keys, our method achieves, for the first time, exponential expansion combined with cryptographic security and noise tolerance. The proof proceeds by showing that the R{\'e}nyi divergence of the outputs of the protocol (for a specific bounding operator) decreases linearly as the protocol iterates. At the heart of the proof are a new uncertainty principle on quantum measurements and a method for simulating trusted measurements with untrusted devices.

}, keywords = {key distribution, nonlocal games, privacy, quantum cryptography, random-number generation, untrusted device}, issn = {0004-5411}, doi = {10.1145/2885493}, url = {http://doi.acm.org/10.1145/2885493}, author = {Carl Miller and Yaoyun Shi} } @article {1864, title = {Evasiveness of Graph Properties and Topological Fixed-Point Theorems}, journal = {Foundations and Trends in Theoretical Computer Science}, volume = {7}, year = {2013}, month = {2013/05/16}, pages = {337-415}, abstract = {Many graph properties (e.g., connectedness, containing a complete subgraph) are known to be difficult to check. In a decision-tree model, the cost of an algorithm is measured by the number of edges in the graph that it queries. R. Karp conjectured in the early 1970s that all monotone graph properties are evasive -- that is, any algorithm which computes a monotone graph property must check all edges in the worst case. This conjecture is unproven, but a lot of progress has been made. Starting with the work of Kahn, Saks, and Sturtevant in 1984, topological methods have been applied to prove partial results on the Karp conjecture. This text is a tutorial on these topological methods. I give a fully self-contained account of the central proofs from the paper of Kahn, Saks, and Sturtevant, with no prior knowledge of topology assumed. I also briefly survey some of the more recent results on evasiveness.

}, issn = {1551-305X}, doi = {10.1561/0400000055}, url = {http://dx.doi.org/10.1561/0400000055}, author = {Carl Miller} } @article {1865, title = {Optimal entanglement-assisted one-shot classical communication}, journal = {Physical Review A}, volume = {87}, year = {2013}, month = {2013/06/03}, pages = {062301}, abstract = {The\ *one-shot success probability*\ of a noisy classical channel for transmitting one classical bit is the optimal probability with which the bit can be successfully sent via a single use of the channel. Prevedel\ *et al.*\ [Phys. Rev. Lett.\ 106, 110505 (2011)] recently showed that for a specific channel, this quantity can be increased if the parties using the channel share an entangled quantum state. In this paper, we characterize the optimal entanglement-assisted protocols in terms of the radius of a set of operators associated with the channel. This characterization can be used to construct optimal entanglement-assisted protocols for a given classical channel and to prove the limits of such protocols. As an example, we show that the Prevedel\ *et al.*\ protocol is optimal for two-qubit entanglement. We also prove some tight upper bounds on the improvement that can be obtained from quantum and nonsignaling correlations.

Self-testing a quantum apparatus means verifying the existence of a certain quantum state as well as the effect of the associated measuring devices based only on the statistics of the measurement outcomes. Robust (i.e., error-tolerant) self-testing quantum apparatuses are critical building blocks for quantum cryptographic protocols that rely on imperfect or untrusted devices. We devise a general scheme for proving optimal robust self-testing properties for tests based on nonlocal binary XOR games. We offer some simplified proofs of known results on self-testing, and also prove some new results.

}, keywords = {nonlocal games, quantum cryptography, Random number generation, Self-testing}, doi = {10.4230/LIPIcs.TQC.2013.254}, author = {Carl Miller and Yaoyun Shi} } @article {1866, title = {Deciding Unitary Equivalence Between Matrix Polynomials and Sets of Bipartite Quantum States}, journal = {Quantum Information and Computation}, volume = {11}, year = {2011}, month = {2001/09/01}, pages = {813{\textendash}819}, abstract = {In this brief report, we consider the equivalence between two sets of\ *m*\ + 1 bipartite quantum states under local unitary transformations. For pure states, this problem corresponds to the matrix algebra question of whether two degree m matrix polynomials are unitarily equivalent; i.e.\ *UA iV*\† =\

The Grothendieck\–Ogg\–Shafarevich formula expresses the Euler characteristic of an {\'e}tale sheaf on a characteristic-\ curve in terms of local data. The purpose of this paper is to prove an equicharacteristic version of this formula (a bound, rather than an equality). This follows work of R.\ Pink.

The basis for the proof of this result is the characteristic-\ Riemann\–Hilbert correspondence, which is a functorial relationship between two different types of sheaves on a characteristic-\ scheme. In the paper we prove a one-dimensional version of this correspondence, considering both local and global settings.

}, issn = {1937-0652}, url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.648.3584}, author = {Carl Miller} } @article {1868, title = {Matrix pencils and entanglement classification}, journal = {Journal of Mathematical Physics}, volume = {51}, year = {2010}, month = {2010/01/01}, pages = {072205}, abstract = {Quantum entanglement plays a central role in quantum information processing. A main objective of the theory is to classify different types of entanglement according to their interconvertibility through manipulations that do not require additional entanglement to perform. While bipartite entanglement is well understood in this framework, the classification of entanglements among three or more subsystems is inherently much more difficult. In this paper, we study pure state entanglement in systems of dimension\ 2\⊗m\⊗n. Two states are considered equivalent if they can be reversibly converted from one to the other with a nonzero probability using only local quantum resources and classical communication (SLOCC). We introduce a connection between entanglement manipulations in these systems and the well-studied theory of matrix pencils. All previous attempts to study general SLOCC equivalence in such systems have relied on somewhat contrived techniques which fail to reveal the elegant structure of the problem that can be seen from the matrix pencil approach. Based on this method, we report the first polynomial-time algorithm for deciding when two2\⊗m\⊗n\ states are SLOCC equivalent. We then proceed to present a canonical form for all\ 2\⊗m\⊗n\ states based on the matrix pencil construction such that two states are equivalent if and only if they have the same canonical form. Besides recovering the previously known 26 distinct SLOCC equivalence classes in\ 2\⊗3\⊗n\ systems, we also determine the hierarchy between these classes.

}, issn = {00222488}, doi = {10.1063/1.3459069}, url = {http://scitation.aip.org/content/aip/journal/jmp/51/7/10.1063/1.3459069}, author = {Chitambar, Eric and Carl Miller and Shi, Yaoyun} } @article {1869, title = {Exponential iterated integrals and the relative solvable completion of the fundamental group of a manifold}, journal = {Topology}, volume = {44}, year = {2005}, month = {2005/03/01}, pages = {351 - 373}, abstract = {We develop a class of integrals on a manifold\ *M*\ called\ *exponential iterated integrals \ *, an extension of K.T. Chen\&$\#$39;s iterated integrals. It is shown that the matrix entries of any upper triangular representation of\ π_{1}(M,x)\ can be expressed via these new integrals. The ring of exponential iterated integrals contains the coordinate rings for a class of universal representations, called the\ *relative solvable completions \ *\ of\ π_{1}(M,x). We consider exponential iterated integrals in the particular case of fibered knot complements, where the fundamental group always has a faithful relative solvable completion.