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.

1 aBreiner, Spencer1 aMiller, Carl1 aRoss, Neil, J. uhttps://arxiv.org/abs/1705.0921301481nas a2200157 4500008004100000245006800041210006700109260001500176300001000191490000800201520102300209100002101232700001601253700001701269856003701286 2019 eng d00aParallel Self-Testing of the GHZ State with a Proof by Diagrams0 aParallel SelfTesting of the GHZ State with a Proof by Diagrams c01/29/2019 a43-660 v2873 aQuantum self-testing addresses the following question: is it possible to verify the existence of a multipartite state even when one'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.

1 aBreiner, Spencer1 aKalev, Amir1 aMiller, Carl uhttps://arxiv.org/abs/1806.0474401727nas a2200157 4500008004100000245004800041210004700089260001500136300001100151490000700162520129200169100001701461700001901478700001601497856005601513 2018 eng d00aKeyring models: an approach to steerability0 aKeyring models an approach to steerability c2018/01/02 a0221030 v593 aIf 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/π.

1 aMiller, Carl1 aColbeck, Roger1 aShi, Yaoyun uhttp://aip.scitation.org/doi/full/10.1063/1.500619901139nas a2200133 4500008004100000245004700041210004600088260001200134300001100146520077800157100001600935700001700951856003700968 2018 eng d00aLocal randomness: Examples and application0 aLocal randomness Examples and application c03/2018 a0323243 aWhen 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).

1 aFu, Honghao1 aMiller, Carl uhttps://arxiv.org/abs/1708.0433801513nas a2200133 4500008004100000245005700041210005600098260001500154520112400169100001601293700001701309700001601326856003701342 2017 eng d00aParallel Device-Independent Quantum Key Distribution0 aParallel DeviceIndependent Quantum Key Distribution c2017/03/153 aA 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' 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.

1 aJain, Rahul1 aMiller, Carl1 aShi, Yaoyun uhttps://arxiv.org/abs/1703.0542601545nas a2200145 4500008004100000245006100041210006100102260001500163300001400178490000700192520113000199100001701329700001601346856003701362 2017 eng d00aRandomness in nonlocal games between mistrustful players0 aRandomness in nonlocal games between mistrustful players c2017/06/15 a0595-06100 v173 aIf 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'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.

1 aMiller, Carl1 aShi, Yaoyun uhttps://arxiv.org/abs/1706.0498401315nas a2200145 4500008004100000245004100041210004100082260001500123300001100138490000600149520091300155100001601068700001701084856006801101 2017 eng d00aRigidity of the magic pentagram game0 aRigidity of the magic pentagram game c2017/11/02 a0150020 v33 aA 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.

1 aKalev, Amir1 aMiller, Carl uhttp://iopscience.iop.org/article/10.1088/2058-9565/aa931d/meta01611nas a2200133 4500008004100000245008000041210006900121260001500190490000700205520118300212100001701395700001601412856004901428 2017 eng d00aUniversal Security for Randomness Expansion from the Spot-Checking Protocol0 aUniversal Security for Randomness Expansion from the SpotCheckin c2017/08/010 v463 aColbeck (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).

1 aMiller, Carl1 aShi, Yaoyun uhttp://epubs.siam.org/doi/10.1137/15M104433302103nas a2200229 4500008004100000022001400041245010900055210006900164260001500233300001700248490000700265520140200272653002101674653001901695653001201714653002501726653002901751653002101780100001701801700001601818856003901834 2016 eng d a0004-541100aRobust Protocols for Securely Expanding Randomness and Distributing Keys Using Untrusted Quantum Devices0 aRobust Protocols for Securely Expanding Randomness and Distribut c2016/10/26 a33:1–33:630 v633 aRandomness 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é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.

10akey distribution10anonlocal games10aprivacy10aquantum cryptography10arandom-number generation10auntrusted device1 aMiller, Carl1 aShi, Yaoyun uhttp://doi.acm.org/10.1145/288549301475nas a2200145 4500008004100000022001400041245007300055210006900128260001500197300001200212490000600224520104100230100001701271856004101288 2013 eng d a1551-305X00aEvasiveness of Graph Properties and Topological Fixed-Point Theorems0 aEvasiveness of Graph Properties and Topological FixedPoint Theor c2013/05/16 a337-4150 v73 aMany 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.

1 aMiller, Carl uhttp://dx.doi.org/10.1561/040000005503288nas a2200169 4500008004100000245006700041210006500108260001500173300001100188490000700199520278500206100002002991700001703011700001603028700001903044856005503063 2013 eng d00aOptimal entanglement-assisted one-shot classical communication0 aOptimal entanglementassisted oneshot classical communication c2013/06/03 a0623010 v873 aThe *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.

10anonlocal games10aquantum cryptography10aRandom number generation10aSelf-testing1 aMiller, Carl1 aShi, Yaoyun uhttps://quics.umd.edu/publications/optimal-robust-self-testing-binary-nonlocal-xor-games03224nas a2200205 4500008004100000022001400041245009700055210006900152260001500221300001400236490000700250520257700257653002302834653002602857653002802883100002002911700001702931700001602948856005402964 2011 eng d a1533-714600aDeciding Unitary Equivalence Between Matrix Polynomials and Sets of Bipartite Quantum States0 aDeciding Unitary Equivalence Between Matrix Polynomials and Sets c2001/09/01 a813–8190 v113 aIn 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 é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.

1 aMiller, Carl uhttp://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.648.358408283nas a2200169 4500008004100000022001300041245005100054210005100105260001500156300001100171490000700182520779500189100002007984700001708004700001608021856007608037 2010 eng d a0022248800aMatrix pencils and entanglement classification0 aMatrix pencils and entanglement classification c2010/01/01 a0722050 v513 aQuantum 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.

1 aChitambar, Eric1 aMiller, Carl1 aShi, Yaoyun uhttp://scitation.aip.org/content/aip/journal/jmp/51/7/10.1063/1.345906906219nas a2200145 4500008004100000022001300041245011100054210006900165260001500234300001400249490000700263520571500270100001705985856007106002 2005 eng d a0040938300aExponential iterated integrals and the relative solvable completion of the fundamental group of a manifold0 aExponential iterated integrals and the relative solvable complet c2005/03/01 a351 - 3730 v443 aWe develop a class of integrals on a manifold *M* called *exponential iterated integrals *, an extension of K.T. Chen'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.