TY - JOUR T1 - Evaluating the security of CRYSTALS-Dilithium in the quantum random oracle model Y1 - 2023 A1 - Kelsey A. Jackson A1 - Carl Miller A1 - Daochen Wang AB -

In the wake of recent progress on quantum computing hardware, the National Institute of Standards and Technology (NIST) is standardizing cryptographic protocols that are resistant to attacks by quantum adversaries. The primary digital signature scheme that NIST has chosen is CRYSTALS-Dilithium. The hardness of this scheme is based on the hardness of three computational problems: Module Learning with Errors (MLWE), Module Short Integer Solution (MSIS), and SelfTargetMSIS. MLWE and MSIS have been well-studied and are widely believed to be secure. However, SelfTargetMSIS is novel and, though classically as hard as MSIS, its quantum hardness is unclear. In this paper, we provide the first proof of the hardness of SelfTargetMSIS via a reduction from MLWE in the Quantum Random Oracle Model (QROM). Our proof uses recently developed techniques in quantum reprogramming and rewinding. A central part of our approach is a proof that a certain hash function, derived from the MSIS problem, is collapsing. From this approach, we deduce a new security proof for Dilithium under appropriate parameter settings. Compared to the only other rigorous security proof for a variant of Dilithium, Dilithium-QROM, our proof has the advantage of being applicable under the condition q = 1 mod 2n, where q denotes the modulus and n the dimension of the underlying algebraic ring. This condition is part of the original Dilithium proposal and is crucial for the efficient implementation of the scheme. We provide new secure parameter sets for Dilithium under the condition q = 1 mod 2n, finding that our public key sizes and signature sizes are about 2.5 to 2.8 times larger than those of Dilithium-QROM for the same security levels.

UR - https://arxiv.org/abs/2312.16619 ER - TY - JOUR T1 - Lattice-Based Quantum Advantage from Rotated Measurements Y1 - 2022 A1 - Yusuf Alnawakhtha A1 - Mantri, Atul A1 - Carl Miller A1 - Wang, Daochen KW - Cryptography and Security (cs.CR) KW - Emerging Technologies (cs.ET) KW - FOS: Computer and information sciences KW - FOS: Physical sciences KW - Quantum Physics (quant-ph) AB -

Trapdoor claw-free functions (TCFs) are immensely valuable in cryptographic interactions between a classical client and a quantum server. Typically, a protocol has the quantum server prepare a superposition of two-bit strings of a claw and then measure it using Pauli-X or Z measurements. In this paper, we demonstrate a new technique that uses the entire range of qubit measurements from the XY-plane. We show the advantage of this approach in two applications. First, building on (Brakerski et al. 2018, Kalai et al. 2022), we show an optimized two-round proof of quantumness whose security can be expressed directly in terms of the hardness of the LWE (learning with errors) problem. Second, we construct a one-round protocol for blind remote preparation of an arbitrary state on the XY-plane up to a Pauli-Z correction.

UR - https://arxiv.org/abs/2210.10143 U5 - 10.48550/ARXIV.2210.10143 ER - TY - JOUR T1 - The Mathematics of Quantum Coin-Flipping JF - Notices of the American Mathematical Society Y1 - 2022 A1 - Carl Miller VL - 69 U4 - 1908-1917 UR - https://www.ams.org/notices/202211/rnoti-p1908.pdf CP - 11 J1 - Notices Amer. Math. Soc. U5 - https://doi.org/10.1090/noti2575 ER - TY - JOUR T1 - Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process JF - NIST Y1 - 2022 A1 - Gorjan Alagic A1 - Daniel Apon A1 - David Cooper A1 - Quynh Dang A1 - Thinh Dang A1 - John Kelsey A1 - Jacob Lichtinger A1 - Carl Miller A1 - Dustin Moody A1 - Rene Peralta A1 - Ray Perlner A1 - Angela Robinson AB -

The National Institute of Standards and Technology is in the process of selecting publickey cryptographic algorithms through a public, competition-like process. The new publickey cryptography standards will specify additional digital signature, public-key encryption, and key-establishment algorithms to augment Federal Information Processing Standard (FIPS) 186-4, Digital Signature Standard (DSS), as well as NIST Special Publication (SP) 800-56A Revision 3, Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography, and SP 800-56B Revision 2, Recommendation for Pair-Wise Key Establishment Using Integer Factorization Cryptography. It is intended that these algorithms will be capable of protecting sensitive information well into the foreseeable future, including after the advent of quantum computers.

This report describes the evaluation and selection process of the NIST Post-Quantum Cryptography Standardization process third-round candidates based on public feedback and internal review. The report summarizes each of the 15 third-round candidate algorithms and identifies those selected for standardization, as well as those that will continue to be evaluated in a fourth round of analysis. The public-key encryption and key-establishment algorithm that will be standardized is CRYSTALS–KYBER. The digital signatures that will be standardized are CRYSTALS–Dilithium, FALCON, and SPHINCS+. While there are multiple signature algorithms selected, NIST recommends CRYSTALS–Dilithium as the primary algorithm to be implemented. In addition, four of the alternate key-establishment candidate algorithms will advance to a fourth round of evaluation: BIKE, Classic McEliece, HQC, and SIKE. These candidates are still being considered for future standardization. NIST will also issue a new Call for Proposals for public-key digital signature algorithms to augment and diversify its signature portfolio.

U5 - https://doi.org/10.6028/NIST.IR.8413-upd1 ER - TY - JOUR T1 - Where we are with quantum JF - Nature Physics Y1 - 2022 A1 - Yusuf Alnawakhtha A1 - Carl Miller AB -

A theoretical analysis shows how a person’s location in space could be verified by the transmission of single photons. A vital application of quantum networks may be within reach.

J1 - Nat. Phys. U5 - https://doi.org/10.1038/s41567-022-01597-w ER - TY - JOUR T1 - The membership problem for constant-sized quantum correlations is undecidable Y1 - 2021 A1 - Honghao Fu A1 - Carl Miller A1 - William Slofstra AB -

When two spatially separated parties make measurements on an unknown entangled quantum state, what correlations can they achieve? How difficult is it to determine whether a given correlation is a quantum correlation? These questions are central to problems in quantum communication and computation. Previous work has shown that the general membership problem for quantum correlations is computationally undecidable. In the current work we show something stronger: there is a family of constant-sized correlations -- that is, correlations for which the number of measurements and number of measurement outcomes are fixed -- such that solving the quantum membership problem for this family is computationally impossible. Thus, the undecidability that arises in understanding Bell experiments is not dependent on varying the number of measurements in the experiment. This places strong constraints on the types of descriptions that can be given for quantum correlation sets. Our proof is based on a combination of techniques from quantum self-testing and from undecidability results of the third author for linear system nonlocal games.

UR - https://arxiv.org/abs/2101.11087 ER - TY - JOUR T1 - Experimental Low-Latency Device-Independent Quantum Randomness JF - Phys. Rev. Lett. Y1 - 2020 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 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.

VL - 124 UR - https://arxiv.org/abs/1812.07786 CP - 010505 U5 - https://doi.org/10.1103/PhysRevLett.124.010505 ER - TY - JOUR T1 - The impossibility of efficient quantum weak coin flipping JF - STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing Y1 - 2020 A1 - Carl Miller AB -

How can two parties with competing interests carry out a fair coin flip across a quantum communication channel? This problem (quantum weak coin-flipping) was formalized more than 15 years ago, and, despite some phenomenal theoretical progress, practical quantum coin-flipping protocols with vanishing bias have proved hard to find. In the current work we show that there is a reason that practical weak quantum coin-flipping is difficult: any quantum weak coin-flipping protocol with bias є must use at least exp( Ω (1/√є )) rounds of communication. This is a large improvement over the previous best known lower bound of Ω ( log log(1/є )) due to Ambainis from 2004. Our proof is based on a theoretical construction (the two-variable profile function) which may find further applications.

U4 - 916-929 U5 - https://doi.org/10.1145/3357713.3384276 ER - TY - JOUR T1 - Parallel Device-Independent Quantum Key Distribution JF - IEEE Transactions on Information Theory Y1 - 2020 A1 - Rahul Jain A1 - Carl Miller A1 - Yaoyun Shi AB -

A prominent application of quantum cryptography is the distribution of cryptographic keys that are provably secure. Such security proofs were 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 the security of a protocol where all games are executed in parallel. Besides decreasing the number of time-steps necessary for key generation, this result reduces the security requirements for DI-QKD by allowing arbitrary information leakage of each user’s inputs within his or her lab. 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.

VL - 66 U4 - 5567-5584 UR - https://arxiv.org/abs/1703.05426 CP - 9 U5 - https://doi.org/10.1109/TIT.2020.2986740 ER - TY - JOUR T1 - Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process JF - NISTIR 8309 Y1 - 2020 A1 - Gorjan Alagic A1 - Jacob Alperin-Sheriff A1 - Daniel Apon A1 - David Cooper A1 - Quynh Dang A1 - John Kelsey A1 - Yi-Kai Liu A1 - Carl Miller A1 - Dustin Moody A1 - Rene Peralta A1 - Ray Perlner A1 - Angela Robinson A1 - Daniel Smith-Tone AB -

The National Institute of Standards and Technology is in the process of selecting one or more public-key cryptographic algorithms through a public, competition-like process. The new public-key cryptography standards will specify one or more additional digital signatures, public-key encryption, and key-establishment algorithms to augment Federal Information Processing Standard (FIPS) 186-4, Digital Signature Standard (DSS), as well as NIST Special Publication (SP) 800-56A Revision 3, Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography, and SP 800-56B Revision 2, Recommendation for Pair-Wise Key Establishment Using Integer Factorization Cryptography. It is intended that these algorithms will be capable of protecting sensitive information well into the foreseeable future, including after the advent of quantum computers.

The NIST Post-Quantum Cryptography Standardization Process began in 2017 with 69 candidate algorithms that met both the minimum acceptance criteria and submission requirements. The first round lasted until January 2019, during which candidate algorithms were evaluated based on their security, performance, and other characteristics. NIST selected 26 algorithms to advance to the second round for more analysis. This report describes the evaluation and selection process, based on public feedback and internal review, of the second-round candidates. The report summarizes the 26 second-round candidate algorithms and identifies those selected to move forward to the third round of the competition. The third-round finalist public-key encryption and key-establishment algorithms are Classic McEliece, CRYSTALS-KYBER, NTRU, and SABER. The third-round finalists for digital signatures are CRYSTALS-DILITHIUM, FALCON, and Rainbow. These finalists will be considered for standardization at the end of the third round. In addition, eight alternate candidate algorithms will also advance to the third round: BIKE, FrodoKEM, HQC, NTRU Prime, SIKE, GeMSS, Picnic, and SPHINCS+. These additional candidates are still being considered for standardization, although this is unlikely to occur at the end of the third round. NIST hopes that the announcement of these finalists and additional candidates will serve to focus the cryptographic community’s attention during the next round.

U5 - https://doi.org/10.6028/NIST.IR.8309 ER - TY - JOUR T1 - Graphical Methods in Device-Independent Quantum Cryptography JF - Quantum Y1 - 2019 A1 - Spencer Breiner A1 - Carl Miller A1 - Neil J. Ross AB -

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 - Status Report on the First Round of the NIST Post-Quantum Cryptography Standardization Process JF - School: National Institute for Standards and Technology Y1 - 2019 A1 - Gorjan Alagic A1 - J. Alperin-Sheriff A1 - D. Apon A1 - D. Cooper A1 - Q. Dang A1 - Carl Miller A1 - D. Moody A1 - R. Peralta A1 - R. Perlner A1 - A. Robinson A1 - D. Smith-Tone A1 - Yi-Kai Liu AB -

The National Institute of Standards and Technology is in the process of selecting one or more
public-key cryptographic algorithms through a public competition-like process. The new publickey cryptography standards will specify one or more additional digital signature, public-key
encryption, and key-establishment algorithms to augment FIPS 186-4, Digital Signature Standard
(DSS), as well as special publications SP 800-56A Revision 2, Recommendation for Pair-Wise
Key Establishment Schemes Using Discrete Logarithm Cryptography, and SP 800-56B,
Recommendation for Pair-Wise Key-Establishment Schemes Using Integer Factorization. It is
intended that these algorithms will be capable of protecting sensitive information well into the
foreseeable future, including after the advent of quantum computers.
In November 2017, 82 candidate algorithms were submitted to NIST for consideration. Among
these, 69 met both the minimum acceptance criteria and our submission requirements, and were
accepted as First-Round Candidates on Dec. 20, 2017, marking the beginning of the First Round
of the NIST Post-Quantum Cryptography Standardization Process. This report describes the
evaluation criteria and selection process, based on public feedback and internal review of the
first-round candidates, and summarizes the 26 candidate algorithms announced on January 30,
2019 for moving forward to the second round of the competition. The 17 Second-Round
Candidate public-key encryption and key-establishment algorithms are BIKE, Classic McEliece,
CRYSTALS-KYBER, FrodoKEM, HQC, LAC, LEDAcrypt (merger of LEDAkem/LEDApkc),
NewHope, NTRU (merger of NTRUEncrypt/NTRU-HRSS-KEM), NTRU Prime, NTS-KEM,
ROLLO (merger of LAKE/LOCKER/Ouroboros-R), Round5 (merger of Hila5/Round2), RQC,
SABER, SIKE, and Three Bears. The 9 Second-Round Candidates for digital signatures are
CRYSTALS-DILITHIUM, FALCON, GeMSS, LUOV, MQDSS, Picnic, qTESLA, Rainbow,
and SPHINCS+.

UR - https://nvlpubs.nist.gov/nistpubs/ir/2019/NIST.IR.8240.pdf 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 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 - 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.

VL - 87 U4 - 062301 UR - http://link.aps.org/doi/10.1103/PhysRevA.87.062301 U5 - 10.1103/PhysRevA.87.062301 ER - TY - CHAP T1 - Optimal robust self-testing by binary nonlocal XOR games T2 - 8th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2013 Y1 - 2013 A1 - Carl Miller A1 - Yaoyun Shi KW - nonlocal games KW - quantum cryptography KW - Random number generation KW - Self-testing AB -

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. UAiV† = Bi for 0 ≤ i ≤ m where U and V are unitary and (Ai, Bi) are arbitrary pairs of rectangular matrices. We present a randomized polynomial-time algorithm that solves this problem with an arbitrarily high success probability and outputs transforming matrices U and V.

VL - 11 U4 - 813–819 UR - http://dl.acm.org/citation.cfm?id=2230936.2230942 CP - 9-10 ER - TY - JOUR T1 - An Euler–Poincaré bound for equicharacteristic étale sheaves JF - Algebra & Number Theory Y1 - 2010 A1 - Carl Miller AB -

The Grothendieck–Ogg–Shafarevich formula expresses the Euler characteristic of an étale sheaf on a characteristic-p 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-p Riemann–Hilbert correspondence, which is a functorial relationship between two different types of sheaves on a characteristic-p 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 2mn. 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 two2mstates are SLOCC equivalent. We then proceed to present a canonical form for all 2mstates 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 23systems, 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.

VL - 44 U4 - 351 - 373 UR - http://www.sciencedirect.com/science/article/pii/S0040938304000795 CP - 2 J1 - Topology U5 - 10.1016/j.top.2004.10.005 ER -