@article {3394, title = {Evaluating the security of CRYSTALS-Dilithium in the quantum random oracle model}, year = {2023}, month = {12/17/2023}, abstract = {

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.

}, url = {https://arxiv.org/abs/2312.16619}, author = {Kelsey A. Jackson and Carl Miller and Daochen Wang} } @article {3154, title = {Lattice-Based Quantum Advantage from Rotated Measurements}, year = {2022}, month = {10/18/2022}, abstract = {

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.

}, keywords = {Cryptography and Security (cs.CR), Emerging Technologies (cs.ET), FOS: Computer and information sciences, FOS: Physical sciences, Quantum Physics (quant-ph)}, doi = {10.48550/ARXIV.2210.10143}, url = {https://arxiv.org/abs/2210.10143}, author = {Yusuf Alnawakhtha and Mantri, Atul and Carl Miller and Wang, Daochen} } @article {3202, title = {The Mathematics of Quantum Coin-Flipping}, journal = {Notices of the American Mathematical Society}, volume = {69}, year = {2022}, month = {12/2022}, pages = {1908-1917}, issn = {0002-9920}, doi = {https://doi.org/10.1090/noti2575}, url = {https://www.ams.org/notices/202211/rnoti-p1908.pdf}, author = {Carl Miller} } @article {3063, title = {Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process}, journal = {NIST}, year = {2022}, month = {7/2022}, abstract = {

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.

}, doi = {https://doi.org/10.6028/NIST.IR.8413-upd1}, author = {Gorjan Alagic and Daniel Apon and David Cooper and Quynh Dang and Thinh Dang and John Kelsey and Jacob Lichtinger and Carl Miller and Dustin Moody and Rene Peralta and Ray Perlner and Angela Robinson} } @article {3043, title = {Where we are with quantum}, journal = {Nature Physics}, year = {2022}, month = {4/28/2022}, abstract = {

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.

}, issn = {1745-2473}, doi = {https://doi.org/10.1038/s41567-022-01597-w}, author = {Yusuf Alnawakhtha and Carl Miller} } @article {2780, title = {The membership problem for constant-sized quantum correlations is undecidable}, year = {2021}, month = {1/26/2021}, abstract = {

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.

}, url = {https://arxiv.org/abs/2101.11087}, author = {Honghao Fu and Carl Miller and William Slofstra} } @article {2329, title = {Experimental Low-Latency Device-Independent Quantum Randomness}, journal = {Phys. Rev. Lett. }, volume = {124}, year = {2020}, month = {12/24/2019}, abstract = {

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.

}, doi = {https://doi.org/10.1103/PhysRevLett.124.010505}, url = {https://arxiv.org/abs/1812.07786}, author = {Yanbao Zhang and Lynden K. Shalm and Joshua C. Bienfang and Martin J. Stevens and Michael D. Mazurek and Sae Woo Nam and Carlos Abell{\'a}n and Waldimar Amaya and Morgan W. Mitchell and Honghao Fu and Carl Miller and Alan Mink and Emanuel Knill} } @article {2629, title = {The impossibility of efficient quantum weak coin flipping}, journal = {STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing }, year = {2020}, month = {6/2020}, pages = {916-929}, abstract = {

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.

}, doi = {https://doi.org/10.1145/3357713.3384276}, author = {Carl Miller} } @article {1951, title = {Parallel Device-Independent Quantum Key Distribution}, journal = {IEEE Transactions on Information Theory}, volume = {66}, year = {2020}, month = {09/2020}, pages = {5567-5584}, abstract = {

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.

}, doi = {https://doi.org/10.1109/TIT.2020.2986740}, url = {https://arxiv.org/abs/1703.05426}, author = {Rahul Jain and Carl Miller and Yaoyun Shi} } @article {2676, title = {Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process}, journal = {NISTIR 8309}, year = {2020}, month = {07/2020}, abstract = {

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.

}, doi = {https://doi.org/10.6028/NIST.IR.8309}, author = {Gorjan Alagic and Jacob Alperin-Sheriff and Daniel Apon and David Cooper and Quynh Dang and John Kelsey and Yi-Kai Liu and Carl Miller and Dustin Moody and Rene Peralta and Ray Perlner and Angela Robinson and Daniel Smith-Tone} } @article {1995, title = {Graphical Methods in Device-Independent Quantum Cryptography}, journal = {Quantum}, volume = {3}, year = {2019}, month = {05/20/2019}, abstract = {

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 {2624, title = {Status Report on the First Round of the NIST Post-Quantum Cryptography Standardization Process}, journal = {School: National Institute for Standards and Technology }, year = {2019}, type = {techreport}, abstract = {

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+.

}, url = {https://nvlpubs.nist.gov/nistpubs/ir/2019/NIST.IR.8240.pdf}, author = {Gorjan Alagic and J. Alperin-Sheriff and D. Apon and D. Cooper and Q. Dang and Carl Miller and D. Moody and R. Peralta and R. Perlner and A. Robinson and D. Smith-Tone and Yi-Kai Liu} } @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 {2051, title = {An Elementary Proof of Private Random Number Generation from Bell Inequalities}, year = {2017}, month = {2017/07/20}, abstract = {

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.

}, url = {https://arxiv.org/abs/1707.06597}, author = {Carl Miller} } @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.

}, doi = {10.1103/PhysRevA.87.062301}, url = {http://link.aps.org/doi/10.1103/PhysRevA.87.062301}, author = {Hemenway, Brett and Carl Miller and Shi, Yaoyun and Wootters, Mary} } @inbook {1863, title = {Optimal robust self-testing by binary nonlocal XOR games}, booktitle = {8th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2013}, volume = {22}, year = {2013}, pages = {254{\textendash}262}, publisher = {Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing}, organization = {Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing}, abstract = {

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.\ 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.

}, keywords = {matrix polynomials, Schwartz-Zippel lemma, unitary transformations}, issn = {1533-7146}, url = {http://dl.acm.org/citation.cfm?id=2230936.2230942}, author = {Chitambar, Eric and Carl Miller and Shi, Yaoyun} } @article {1867, title = {An Euler{\textendash}Poincar{\'e} bound for equicharacteristic {\'e}tale sheaves}, journal = {Algebra \& Number Theory}, volume = {4}, year = {2010}, month = {2010/01/14}, pages = {21 - 45}, abstract = {

The Grothendieck\–Ogg\–Shafarevich formula expresses the Euler characteristic of an {\'e}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.

}, 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.

}, issn = {00409383}, doi = {10.1016/j.top.2004.10.005}, url = {http://www.sciencedirect.com/science/article/pii/S0040938304000795}, author = {Carl Miller} }