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.

VL - 3 UR - https://arxiv.org/abs/1705.09213 CP - 146 U5 - https://doi.org/10.22331/q-2019-05-27-146 ER - TY - JOUR T1 - Parallel Self-Testing of the GHZ State with a Proof by Diagrams JF - EPTCS Y1 - 2019 A1 - Spencer Breiner A1 - Amir Kalev A1 - Carl Miller AB -Quantum 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.

VL - 287 U4 - 43-66 UR - https://arxiv.org/abs/1806.04744 U5 - https://doi.org/10.4204/EPTCS.287.3 ER - TY - JOUR T1 - Experimental Low-Latency Device-Independent Quantum Randomness Y1 - 2018 A1 - Yanbao Zhang A1 - Lynden K. Shalm A1 - Joshua C. Bienfang A1 - Martin J. Stevens A1 - Michael D. Mazurek A1 - Sae Woo Nam A1 - Carlos Abellán A1 - Waldimar Amaya A1 - Morgan W. Mitchell A1 - Honghao Fu A1 - Carl A. Miller A1 - Alan Mink A1 - Emanuel Knill AB -Applications of randomness such as private key generation and public randomness beacons require small blocks of certified random bits on demand. Device-independent quantum random number generators can produce such random bits, but existing quantum-proof protocols and loophole-free implementations suffer from high latency, requiring many hours to produce any random bits. We demonstrate device-independent quantum randomness generation from a loophole-free Bell test with a more efficient quantum-proof protocol, obtaining multiple blocks of 512 bits with an average experiment time of less than 5 min per block and with certified error bounded by 2−64≈5.42×10−20.

UR - https://arxiv.org/abs/1812.07786 ER - TY - JOUR T1 - Keyring models: an approach to steerability JF - Journal of Mathematical Physics Y1 - 2018 A1 - Carl Miller A1 - Roger Colbeck A1 - Yaoyun Shi AB -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/π.

VL - 59 U4 - 022103 UR - http://aip.scitation.org/doi/full/10.1063/1.5006199 U5 - 10.1063/1.5006199 ER - TY - JOUR T1 - Local randomness: Examples and application JF - Phys. Rev. A Y1 - 2018 A1 - Honghao Fu A1 - Carl Miller AB -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).

U4 - 032324 UR - https://arxiv.org/abs/1708.04338 CP - 97 U5 - https://doi.org/10.1103/PhysRevA.97.032324 ER - TY - JOUR T1 - An Elementary Proof of Private Random Number Generation from Bell Inequalities Y1 - 2017 A1 - Carl A. Miller AB -The field of device-independent quantum cryptography has seen enormous success in the past several years, including security proofs for key distribution and random number generation that account for arbitrary imperfections in the devices used. Full security proofs in the field so far are long and technically deep. In this paper we show that the concept of the mirror adversary can be used to simplify device-independent proofs. We give a short proof that any bipartite Bell violation can be used to generate private random numbers. The proof is based on elementary techniques and is self-contained.

UR - https://arxiv.org/abs/1707.06597 ER - TY - JOUR T1 - Parallel Device-Independent Quantum Key Distribution Y1 - 2017 A1 - Rahul Jain A1 - Carl Miller A1 - Yaoyun Shi AB -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' 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.

UR - https://arxiv.org/abs/1703.05426 ER - TY - JOUR T1 - Randomness in nonlocal games between mistrustful players JF - Quantum Information and Computation Y1 - 2017 A1 - Carl Miller A1 - Yaoyun Shi AB -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'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.

VL - 17 U4 - 0595-0610 UR - https://arxiv.org/abs/1706.04984 CP - 7&8 ER - TY - JOUR T1 - Rigidity of the magic pentagram game JF - Quantum Science and Technology Y1 - 2017 A1 - Amir Kalev A1 - Carl Miller AB -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.

VL - 3 U4 - 015002 UR - http://iopscience.iop.org/article/10.1088/2058-9565/aa931d/meta CP - 1 ER - TY - JOUR T1 - Universal Security for Randomness Expansion from the Spot-Checking Protocol JF - SIAM Journal on Computing Y1 - 2017 A1 - Carl Miller A1 - Yaoyun Shi AB -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).

VL - 46 UR - http://epubs.siam.org/doi/10.1137/15M1044333 CP - 4 U5 - 10.1137/15M1044333 ER - TY - JOUR T1 - Robust Protocols for Securely Expanding Randomness and Distributing Keys Using Untrusted Quantum Devices JF - Journal of the ACM Y1 - 2016 A1 - Carl Miller A1 - Yaoyun Shi KW - key distribution KW - nonlocal games KW - privacy KW - quantum cryptography KW - random-number generation KW - untrusted device AB -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é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.

VL - 63 U4 - 33:1–33:63 UR - http://doi.acm.org/10.1145/2885493 CP - 4 U5 - 10.1145/2885493 ER - TY - JOUR T1 - Evasiveness of Graph Properties and Topological Fixed-Point Theorems JF - Foundations and Trends in Theoretical Computer Science Y1 - 2013 A1 - Carl Miller AB -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.

VL - 7 U4 - 337-415 UR - http://dx.doi.org/10.1561/0400000055 U5 - 10.1561/0400000055 ER - TY - JOUR T1 - Optimal entanglement-assisted one-shot classical communication JF - Physical Review A Y1 - 2013 A1 - Hemenway, Brett A1 - Carl Miller A1 - Shi, Yaoyun A1 - Wootters, Mary AB -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.

JA - 8th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2013 PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing VL - 22 U4 - 254–262 U5 - 10.4230/LIPIcs.TQC.2013.254 ER - TY - JOUR T1 - Deciding Unitary Equivalence Between Matrix Polynomials and Sets of Bipartite Quantum States JF - Quantum Information and Computation Y1 - 2011 A1 - Chitambar, Eric A1 - Carl Miller A1 - Shi, Yaoyun KW - matrix polynomials KW - Schwartz-Zippel lemma KW - unitary transformations AB -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 é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.

VL - 4 U4 - 21 - 45 UR - http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.648.3584 CP - 1 J1 - ANT ER - TY - JOUR T1 - Matrix pencils and entanglement classification JF - Journal of Mathematical Physics Y1 - 2010 A1 - Chitambar, Eric A1 - Carl Miller A1 - Shi, Yaoyun AB -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.

VL - 51 U4 - 072205 UR - http://scitation.aip.org/content/aip/journal/jmp/51/7/10.1063/1.3459069 CP - 7 J1 - J. Math. Phys. U5 - 10.1063/1.3459069 ER - TY - JOUR T1 - Exponential iterated integrals and the relative solvable completion of the fundamental group of a manifold JF - Topology Y1 - 2005 A1 - Carl Miller AB -We 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.