@article {3308, title = {On the Two-sided Permutation Inversion Problem}, year = {2023}, month = {6/23/2023}, abstract = {

In the permutation inversion problem, the task is to find the preimage of some challenge value, given oracle access to the permutation. This is a fundamental problem in query complexity, and appears in many contexts, particularly cryptography. In this work, we examine the setting in which the oracle allows for quantum queries to both the forward and the inverse direction of the permutation -- except that the challenge value cannot be submitted to the latter. Within that setting, we consider two options for the inversion algorithm: whether it can get quantum advice about the permutation, and whether it must produce the entire preimage (search) or only the first bit (decision). We prove several theorems connecting the hardness of the resulting variations of the inversion problem, and establish a number of lower bounds. Our results indicate that, perhaps surprisingly, the inversion problem does not become significantly easier when the adversary is granted oracle access to the inverse, provided it cannot query the challenge itself.

}, url = {https://arxiv.org/abs/2306.13729}, author = {Gorjan Alagic and Chen Bai and Alexander Poremba and Kaiyan Shi} } @article {2931, title = {Post-Quantum Security of the Even-Mansour Cipher}, journal = {Eurocrypt}, year = {2022}, month = {12/14/2021}, abstract = {

The Even-Mansour cipher is a simple method for constructing a (keyed) pseudorandom permutation E from a public random permutation~P:{0,1}n\→{0,1}n. It is secure against classical attacks, with optimal attacks requiring qE queries to E and qP queries to P such that qE\⋅qP\≈2n. If the attacker is given \emph{quantum} access to both E and P, however, the cipher is completely insecure, with attacks using qE,qP=O(n) queries known. In any plausible real-world setting, however, a quantum attacker would have only \emph{classical} access to the keyed permutation~E implemented by honest parties, even while retaining quantum access to~P. Attacks in this setting with qE\⋅q2P\≈2n are known, showing that security degrades as compared to the purely classical case, but leaving open the question as to whether the Even-Mansour cipher can still be proven secure in this natural, \"post-quantum\" setting. We resolve this question, showing that any attack in that setting requires qE\⋅q2P+qP\⋅q2E\≈2n. Our results apply to both the two-key and single-key variants of Even-Mansour. Along the way, we establish several generalizations of results from prior work on quantum-query lower bounds that may be of independent interest.\ 

}, doi = {https://doi.org/10.48550/arXiv.2112.07530}, url = {https://arxiv.org/abs/2112.07530}, author = {Gorjan Alagic and Chen Bai and Jonathan Katz and Christian Majenz} } @article {3201, title = {Post-Quantum Security of the (Tweakable) FX Construction, and Applications}, year = {2022}, month = {8/29/2022}, abstract = {

The FX construction provides a way to increase the effective key length of a block cipher E. We prove security of a tweakable version of the FX construction in the post-quantum setting, i.e., against a quantum attacker given only classical access to the secretly keyed construction while retaining quantum access to E, a setting that seems to be the most relevant one for real-world applications. We then use our results to prove post-quantum security\—in the same model\—of the (plain) FX construction, Elephant (a finalist of NIST\&$\#$39;s lightweight cryptography standardization effort), and Chaskey (an ISO-standardized lightweight MAC

}, url = {https://eprint.iacr.org/2022/1097}, author = {Gorjan Alagic and Chen Bai and Jonathan Katz and Christian Majenz and Patrick Struck} } @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 {2307, title = {Can you sign a quantum state?}, journal = {v4: version for publication in Quantum, v5: CC license}, year = {2021}, month = {12/6/2021}, abstract = {

Cryptography with quantum states exhibits a number of surprising and counterintuitive features. In a 2002 work, Barnum et al. argued informally that these strange features should imply that digital signatures for quantum states are impossible (Barnum et al., FOCS 2002). In this work, we perform the first rigorous study of the problem of signing quantum states. We first show that the intuition of Barnum et al. was correct, by proving an impossibility result which rules out even very weak forms of signing quantum states. Essentially, we show that any non-trivial combination of correctness and security requirements results in negligible security. This rules out all quantum signature schemes except those which simply measure the state and then sign the outcome using a classical scheme. In other words, only classical signature schemes exist. We then show a positive result: it is possible to sign quantum states, provided that they are also encrypted with the public key of the intended recipient. Following classical nomenclature, we call this notion quantum signcryption. Classically, signcryption is only interesting if it provides superior efficiency to simultaneous encryption and signing. Our results imply that, quantumly, it is far more interesting: by the laws of quantum mechanics, it is the only signing method available. We develop security definitions for quantum signcryption, ranging from a simple one-time two-user setting, to a chosen-ciphertext-secure many-time multi-user setting. We also give secure constructions based on post-quantum public-key primitives. Along the way, we show that a natural hybrid method of combining classical and quantum schemes can be used to \"upgrade\" a secure classical scheme to the fully-quantum setting, in a wide range of cryptographic settings including signcryption, authenticated encryption, and chosen-ciphertext security.

}, url = {https://arxiv.org/abs/1811.11858}, author = {Gorjan Alagic and Tommaso Gagliardoni and Christian Majenz} } @article {2627, title = {Efficient Simulation of Random States and Random Unitaries}, journal = {In: Canteaut A., Ishai Y. (eds) Advances in Cryptology {\textendash} EUROCRYPT 2020. Lecture Notes in Computer Science, Springer, Cham}, volume = {12107}, year = {2020}, month = {5/1/2020}, pages = {759-787}, type = {inproceedings}, abstract = {

We consider the problem of efficiently simulating random quantum states and random unitary operators, in a manner which is convincing to unbounded adversaries with black-box oracle access.

This problem has previously only been considered for restricted adversaries. Against adversaries with an a priori bound on the number of queries, it is well-known that t-designs suffice. Against polynomial-time adversaries, one can use pseudorandom states (PRS) and pseudorandom unitaries (PRU), as defined in a recent work of Ji, Liu, and Song; unfortunately, no provably secure construction is known for PRUs.

In our setting, we are concerned with unbounded adversaries. Nonetheless, we are able to give stateful quantum algorithms which simulate the ideal object in both settings of interest. In the case of Haar-random states, our simulator is polynomial-time, has negligible error, and can also simulate verification and reflection through the simulated state. This yields an immediate application to quantum money: a money scheme which is information-theoretically unforgeable and untraceable. In the case of Haar-random unitaries, our simulator takes polynomial space, but simulates both forward and inverse access with zero error.

These results can be seen as the first significant steps in developing a theory of lazy sampling for random quantum objects.

}, doi = {https://doi.org/10.1007/978-3-030-45727-3_26}, author = {Gorjan Alagic and Christian Majenz and Alexander Russell} } @article {2625, title = {Impossibility of Quantum Virtual Black-Box Obfuscation of Classical Circuits}, year = {2020}, month = {5/13/2020}, abstract = {

Virtual black-box obfuscation is a strong cryptographic primitive: it encrypts a circuit while maintaining its full input/output functionality. A remarkable result by Barak et al. (Crypto 2001) shows that a general obfuscator that obfuscates classical circuits into classical circuits cannot exist. A promising direction that circumvents this impossibility result is to obfuscate classical circuits into quantum states, which would potentially be better capable of hiding information about the obfuscated circuit. We show that, under the assumption that learning-with-errors (LWE) is hard for quantum computers, this quantum variant of virtual black-box obfuscation of classical circuits is generally impossible. On the way, we show that under the presence of dependent classical auxiliary input, even the small class of classical point functions cannot be quantum virtual black-box obfuscated.

}, url = {https://arxiv.org/abs/2005.06432}, author = {Gorjan Alagic and Zvika Brakerski and Yfke Dulek and Christian Schaffner} } @article {2485, title = {Non-interactive classical verification of quantum computation}, journal = {Theory of Cryptography Conference (TCC)}, volume = {Lecture Notes in Computer Science 12552}, year = {2020}, month = {3/9/2020}, pages = {153-180}, abstract = {

In a recent breakthrough, Mahadev constructed an interactive protocol that enables a purely classical party to delegate any quantum computation to an untrusted quantum prover. In this work, we show that this same task can in fact be performed non-interactively and in zero-knowledge.
Our protocols result from a sequence of significant improvements to the original four-message protocol of Mahadev. We begin by making the first message instance-independent and moving it to an offline setup phase. We then establish a parallel repetition theorem for the resulting three-message protocol, with an asymptotically optimal rate. This, in turn, enables an application of the Fiat-Shamir heuristic, eliminating the second message and giving a non-interactive protocol. Finally, we employ classical non-interactive zero-knowledge (NIZK) arguments and classical fully homomorphic encryption (FHE) to give a zero-knowledge variant of this construction. This yields the first purely classical NIZK argument system for QMA, a quantum analogue of NP.
We establish the security of our protocols under standard assumptions in quantum-secure cryptography. Specifically, our protocols are secure in the Quantum Random Oracle Model, under the assumption that Learning with Errors is quantumly hard. The NIZK construction also requires circuit-private FHE.

}, url = {https://arxiv.org/abs/1911.08101}, author = {Gorjan Alagic and Andrew M. Childs and Alex B. Grilo and Shih-Han Hung} } @article {2626, title = {On Quantum Chosen-Ciphertext Attacks and Learning with Errors}, journal = {Cryptography}, volume = {4}, year = {2020}, month = {3/21/2020}, pages = {10}, abstract = {

Large-scale quantum computing poses a major threat to classical public-key cryptography. Recently, strong \“quantum access\” security models have shown that numerous symmetric-key cryptosystems are also vulnerable. In this paper, we consider classical encryption in a model that grants the adversary quantum oracle access to encryption and decryption, but where we restrict the latter to non-adaptive (i.e., pre-challenge) queries only. We formalize this model using appropriate notions of ciphertext indistinguishability and semantic security (which are equivalent by standard arguments) and call it QCCA1 in analogy to the classical CCA1 security model. We show that the standard pseudorandom function ( PRF )-based encryption schemes are QCCA1 -secure when instantiated with quantum-secure primitives. Our security proofs use a strong bound on quantum random-access codes with shared randomness. Revisiting plain IND\−CPA -secure Learning with Errors ( LWE ) encryption, we show that leaking only a single quantum decryption query (and no other leakage or queries of any kind) allows the adversary to recover the full secret key with constant success probability. Information-theoretically, full recovery of the key in the classical setting requires at least a linear number of decryption queries. Our results thus challenge the notion that LWE is unconditionally \“just as secure\” quantumly as it is classically. The algorithm at the core of our attack is a new variant of the well-known Bernstein\–Vazirani algorithm. Finally, we emphasize that our results should not be interpreted as a weakness of these cryptosystems in their stated security setting (i.e., post-quantum chosen-plaintext secrecy). Rather, our results mean that, if these cryptosystems are exposed to chosen-ciphertext attacks (e.g., as a result of deployment in an inappropriate real-world setting) then quantum attacks are even more devastating than classical ones.

}, doi = {https://doi.org/10.3390/cryptography4010010}, author = {Gorjan Alagic and Stacey Jeffery and Maris Ozols and Alexander Poremba} } @article {2628, title = {Quantum-Access-Secure Message Authentication via Blind-Unforgeability}, journal = {In: Canteaut A., Ishai Y. (eds) Advances in Cryptology {\textendash} EUROCRYPT 2020. Lecture Notes in Computer Science, Springer, Cham}, volume = {12-17}, year = {2020}, month = {5/1/2020}, pages = {788-817 }, type = {inproceedings}, abstract = {

Formulating and designing authentication of classical messages in the presence of adversaries with quantum query access has been a longstanding challenge, as the familiar classical notions of unforgeability do not directly translate into meaningful notions in the quantum setting. A particular difficulty is how to fairly capture the notion of \“predicting an unqueried value\” when the adversary can query in quantum superposition.

We propose a natural definition of unforgeability against quantum adversaries called blind unforgeability. This notion defines a function to be predictable if there exists an adversary who can use \“partially blinded\” oracle access to predict values in the blinded region. We support the proposal with a number of technical results. We begin by establishing that the notion coincides with EUF-CMA in the classical setting and go on to demonstrate that the notion is satisfied by a number of simple guiding examples, such as random functions and quantum-query-secure pseudorandom functions. We then show the suitability of blind unforgeability for supporting canonical constructions and reductions. We prove that the \“hash-and-MAC\” paradigm and the Lamport one-time digital signature scheme are indeed unforgeable according to the definition. To support our analysis, we additionally define and study a new variety of quantum-secure hash functions called Bernoulli-preserving.

Finally, we demonstrate that blind unforgeability is strictly stronger than a previous definition of Boneh and Zhandry [EUROCRYPT \’13, CRYPTO \’13] and resolve an open problem concerning this previous definition by constructing an explicit function family which is forgeable yet satisfies the definition.

}, doi = {https://doi.org/10.1007/978-3-030-45727-3_27}, author = {Gorjan Alagic and Christian Majenz and Alexander Russell and Fang Song} } @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 {2219, title = {On non-adaptive quantum chosen-ciphertext attacks and Learning with Errors}, journal = {14th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2019, June 3-5, 2019, University of Maryland, College Park, Maryland, USA}, year = {2019}, pages = {1:1-1:23 }, abstract = {

Large-scale quantum computing is a significant threat to classical public-key cryptography. In strong \"quantum access\" security models, numerous symmetric-key cryptosystems are also vulnerable. We consider classical encryption in a model which grants the adversary quantum oracle access to encryption and decryption, but where the latter is restricted to non-adaptive (i.e., pre-challenge) queries only. We define this model formally using appropriate notions of ciphertext indistinguishability and semantic security (which are equivalent by standard arguments) and call it QCCA1 in analogy to the classical CCA1 security model. Using a bound on quantum random-access codes, we show that the standard PRF- and PRP-based encryption schemes are QCCA1-secure when instantiated with quantum-secure primitives. We then revisit standard IND-CPA-secure Learning with Errors (LWE) encryption and show that leaking just one quantum decryption query (and no other queries or leakage of any kind) allows the adversary to recover the full secret key with constant success probability. In the classical setting, by contrast, recovering the key uses a linear number of decryption queries, and this is optimal. The algorithm at the core of our attack is a (large-modulus version of) the well-known Bernstein-Vazirani algorithm. We emphasize that our results should *not* be interpreted as a weakness of these cryptosystems in their stated security setting (i.e., post-quantum chosen-plaintext secrecy). Rather, our results mean that, if these cryptosystems are exposed to chosen-ciphertext attacks (e.g., as a result of deployment in an inappropriate real-world setting) then quantum attacks are even more devastating than classical ones.\ 

}, doi = {https://doi.org/10.4230/LIPIcs.TQC.2019.1}, url = {https://arxiv.org/abs/1808.09655}, author = {Gorjan Alagic and Stacey Jeffery and Maris Ozols and Alexander Poremba} } @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 {2308, title = {Quantum-secure message authentication via blind-unforgeability}, year = {2018}, abstract = {

Formulating and designing unforgeable authentication of classical messages in the presence of quantum adversaries has been a challenge, as the familiar classical notions of unforgeability do not directly translate into meaningful notions in the quantum setting. A particular difficulty is how to fairly capture the notion of \"predicting an unqueried value\" when the adversary can query in quantum superposition. In this work, we uncover serious shortcomings in existing approaches, and propose a new definition. We then support its viability by a number of constructions and characterizations. Specifically, we demonstrate a function which is secure according to the existing definition by Boneh and Zhandry, but is clearly vulnerable to a quantum forgery attack, whereby a query supported only on inputs that start with 0 divulges the value of the function on an input that starts with 1. We then propose a new definition, which we call \"blind-unforgeability\" (or BU.) This notion matches \"intuitive unpredictability\" in all examples studied thus far. It defines a function to be predictable if there exists an adversary which can use \"partially blinded\" oracle access to predict values in the blinded region. Our definition (BU) coincides with standard unpredictability (EUF-CMA) in the classical-query setting. We show that quantum-secure pseudorandom functions are BU-secure MACs. In addition, we show that BU satisfies a composition property (Hash-and-MAC) using \"Bernoulli-preserving\" hash functions, a new notion which may be of independent interest. Finally, we show that BU is amenable to security reductions by giving a precise bound on the extent to which quantum algorithms can deviate from their usual behavior due to the blinding in the BU security experiment.\ 

}, url = {https://arxiv.org/abs/1803.03761}, author = {Gorjan Alagic and Christian Majenz and Alexander Russell and Fang Song} } @article {1837, title = {Spectrum estimation of density operators with alkaline-earth atoms}, volume = {120}, year = {2018}, month = {2018/01/09}, abstract = {

We show that Ramsey spectroscopy of fermionic alkaline-earth atoms in a square-well trap provides an efficient and accurate estimate for the eigenspectrum of a density matrix whose n copies are stored in the nuclear spins of n such atoms. This spectrum estimation is enabled by the high symmetry of the interaction Hamiltonian, dictated, in turn, by the decoupling of the nuclear spin from the electrons and by the shape of the square-well trap. Practical performance of this procedure and its potential applications to quantum computing, quantum simulation, and time-keeping with alkalineearth atoms are discussed.

}, doi = {https://doi.org/10.1103/PhysRevLett.120.025301}, url = {http://arxiv.org/abs/1608.02045}, author = {Michael E. Beverland and Jeongwan Haah and Gorjan Alagic and Gretchen K. Campbell and Ana Maria Rey and Alexey V. Gorshkov} } @article {2622, title = {Unforgeable Quantum Encryption}, journal = {In: Nielsen J., Rijmen V. (eds) Advances in Cryptology {\textendash} EUROCRYPT 2018. Lecture Notes in Computer Science, Springer, Cham}, volume = {10822}, year = {2018}, abstract = {

We study the problem of encrypting and authenticating quantum data in the presence of adversaries making adaptive chosen plaintext and chosen ciphertext queries. Classically, security games use string copying and comparison to detect adversarial cheating in such scenarios. Quantumly, this approach would violate no-cloning. We develop new techniques to overcome this problem: we use entanglement to detect cheating, and rely on recent results for characterizing quantum encryption schemes. We give definitions for (i) ciphertext unforgeability, (ii) indistinguishability under adaptive chosen-ciphertext attack, and (iii) authenticated encryption. The restriction of each definition to the classical setting is at least as strong as the corresponding classical notion: (i) implies\ \  INT-CTXT , (ii) implies\ \  IND-CCA2 , and (iii) implies\ \  AE . All of our new notions also imply\ \  QIND-CPA\  privacy. Combining one-time authentication and classical pseudorandomness, we construct symmetric-key quantum encryption schemes for each of these new security notions, and provide several separation examples. Along the way, we also give a new definition of one-time quantum authentication which, unlike all previous approaches, authenticates ciphertexts rather than plaintexts.

}, doi = {https://doi.org/10.1007/978-3-319-78372-7_16}, author = {Gorjan Alagic and Tommaso Gagliardoni and Christian Majenz} } @article {2619, title = {3-manifold diagrams and NP vs P}, journal = {Quantum Information \& Computation }, volume = {17}, year = {2017}, pages = {125-141 }, abstract = {

The computational complexity class $\#$P captures the di_culty of counting the satisfying assignments to a boolean formula. In this work, we use basic tools from quantum computation to give a proof that the SO(3) Witten-Reshetikhin-Turaev (WRT) invariant of 3-manifolds is $\#$P-hard to calculate. We then apply this result to a question about the combinatorics of Heegaard splittings, motivated by analogous work on link diagrams by M. Freedman. We show that, if $\#$P \⊆ FPNP, then there exist infinitely many Heegaard splittings which cannot be made logarithmically thin by local WRT-preserving moves, except perhaps via a superpolynomial number of steps. We also outline two extensions of the above results. First, adapting a result of Kuperberg, we show that any presentation-independent approximation of WRT is also $\#$P-hard. Second, we sketch out how all of our results can be translated to the setting of triangulations and Turaev-Viro invariants.

}, url = {https://dl.acm.org/doi/abs/10.5555/3179483.3179491}, author = {Gorjan Alagic and C. Lo} } @article {2058, title = {Quantum Fully Homomorphic Encryption With Verification}, journal = {Proceedings of ASIACRYPT 2017}, year = {2017}, month = {2017/11/30}, pages = {438-467}, abstract = {

Fully-homomorphic encryption (FHE) enables computation on encrypted data while maintaining secrecy. Recent research has shown that such schemes exist even for quantum computation. Given the numerous applications of classical FHE (zero-knowledge proofs, secure two-party computation, obfuscation, etc.) it is reasonable to hope that quantum FHE (or QFHE) will lead to many new results in the quantum setting. However, a crucial ingredient in almost all applications of FHE is circuit verification. Classically, verification is performed by checking a transcript of the homomorphic computation. Quantumly, this strategy is impossible due to no-cloning. This leads to an important open question: can quantum computations be delegated and verified in a non-interactive manner? In this work, we answer this question in the affirmative, by constructing a scheme for QFHE with verification (vQFHE). Our scheme provides authenticated encryption, and enables arbitrary polynomial-time quantum computations without the need of interaction between client and server. Verification is almost entirely classical; for computations that start and end with classical states, it is completely classical. As a first application, we show how to construct quantum one-time programs from classical one-time programs and vQFHE.

}, doi = {10.1007/978-3-319-70694-8_16}, url = {https://arxiv.org/abs/1708.09156}, author = {Gorjan Alagic and Yfke Dulek and Christian Schaffner and Florian Speelman} } @article {2620, title = {Quantum Non-malleability and Authentication}, journal = {In: Katz J., Shacham H. (eds) Advances in Cryptology {\textendash} CRYPTO 2017. Lecture Notes in Computer Science. Springer, Cham}, volume = {10402}, year = {2017}, abstract = {

In encryption, non-malleability is a highly desirable property: it ensures that adversaries cannot manipulate the plaintext by acting on the ciphertext. In [6], Ambainis et al. gave a definition of non-malleability for the encryption of quantum data. In this work, we show that this definition is too weak, as it allows adversaries to \“inject\” plaintexts of their choice into the ciphertext. We give a new definition of quantum non-malleability which resolves this problem. Our definition is expressed in terms of entropic quantities, considers stronger adversaries, and does not assume secrecy. Rather, we prove that quantum non-malleability implies secrecy; this is in stark contrast to the classical setting, where the two properties are completely independent. For unitary schemes, our notion of non-malleability is equivalent to encryption with a two-design (and hence also to the definition of [6]).

Our techniques also yield new results regarding the closely-related task of quantum authentication. We show that \“total authentication\” (a notion recently proposed by Garg et al. [18]) can be satisfied with two-designs, a significant improvement over the eight-design construction of [18]. We also show that, under a mild adaptation of the rejection procedure, both total authentication and our notion of non-malleability yield quantum authentication as defined by Dupuis et al. [16].

}, doi = {https://doi.org/10.1007/978-3-319-63715-0_11}, author = {Gorjan Alagic and Christian Majenz} } @article {2621, title = {Quantum-Secure Symmetric-Key Cryptography Based on Hidden Shifts}, journal = {In: Coron JS., Nielsen J. (eds) Advances in Cryptology {\textendash} EUROCRYPT 2017. Lecture Notes in Computer Science, Springer, Cham}, volume = {10212}, year = {2017}, abstract = {

Recent results of Kaplan et al., building on work by Kuwakado and Morii, have shown that a wide variety of classically-secure symmetric-key cryptosystems can be completely broken by quantum chosen-plaintext attacks (qCPA). In such an attack, the quantum adversary has the ability to query the cryptographic functionality in superposition. The vulnerable cryptosystems include the Even-Mansour block cipher, the three-round Feistel network, the Encrypted-CBC-MAC, and many others.

In this article, we study simple algebraic adaptations of such schemes that replace\ \  (Z/2)n\  addition with operations over alternate finite groups\—such as\ \  Z/2n \—and provide evidence that these adaptations are qCPA-secure. These adaptations furthermore retain the classical security properties and basic structural features enjoyed by the original schemes.

We establish security by treating the (quantum) hardness of the well-studied Hidden Shift problem as a cryptographic assumption. We observe that this problem has a number of attractive features in this cryptographic context, including random self-reducibility, hardness amplification, and\—in many cases of interest\—a reduction from the \“search version\” to the \“decisional version.\” We then establish, under this assumption, the qCPA-security of several such Hidden Shift adaptations of symmetric-key constructions. We show that a Hidden Shift version of the Even-Mansour block cipher yields a quantum-secure pseudorandom function, and that a Hidden Shift version of the Encrypted CBC-MAC yields a collision-resistant hash function. Finally, we observe that such adaptations frustrate the direct Simon\’s algorithm-based attacks in more general circumstances, e.g., Feistel networks and slide attacks.

}, doi = {https://doi.org/10.1007/978-3-319-56617-7_3}, author = {Gorjan Alagic and Alexander Russell} } @article {2057, title = {Unforgeable Quantum Encryption}, year = {2017}, month = {2017/09/19}, abstract = {

We study the problem of encrypting and authenticating quantum data in the presence of adversaries making adaptive chosen plaintext and chosen ciphertext queries. Classically, security games use string copying and comparison to detect adversarial cheating in such scenarios. Quantumly, this approach would violate no-cloning. We develop new techniques to overcome this problem: we use entanglement to detect cheating, and rely on recent results for characterizing quantum encryption schemes. We give definitions for (i.) ciphertext unforgeability , (ii.) indistinguishability under adaptive chosen-ciphertext attack, and (iii.) authenticated encryption. The restriction of each definition to the classical setting is at least as strong as the corresponding classical notion: (i) implies INT-CTXT, (ii) implies IND-CCA2, and (iii) implies AE. All of our new notions also imply QIND-CPA privacy. Combining one-time authentication and classical pseudorandomness, we construct schemes for each of these new quantum security notions, and provide several separation examples. Along the way, we also give a new definition of one-time quantum authentication which, unlike all previous approaches, authenticates ciphertexts rather than plaintexts.

}, url = {https://arxiv.org/abs/1709.06539}, author = {Gorjan Alagic and Tommaso Gagliardoni and Christian Majenz} } @conference {1712, title = {Computational Security of Quantum Encryption}, booktitle = {Computational Security of Quantum Encryption. In: Nascimento A., Barreto P. (eds) Information Theoretic Security. }, year = {2016}, month = {2016/11/10}, abstract = {

Quantum-mechanical devices have the potential to transform cryptography. Most research in this area has focused either on the information-theoretic advantages of quantum protocols or on the security of classical cryptographic schemes against quantum attacks. In this work, we initiate the study of another relevant topic: the encryption of quantum data in the computational setting. In this direction, we establish quantum versions of several fundamental classical results. First, we develop natural definitions for private-key and public-key encryption schemes for quantum data. We then define notions of semantic security and indistinguishability, and, in analogy with the classical work of Goldwasser and Micali, show that these notions are equivalent. Finally, we construct secure quantum encryption schemes from basic primitives. In particular, we show that quantum-secure one-way functions imply IND-CCA1-secure symmetric-key quantum encryption, and that quantum-secure trapdoor one-way permutations imply semantically-secure public-key quantum encryption.

}, url = {https://link.springer.com/chapter/10.1007\%2F978-3-319-49175-2_3}, author = {Gorjan Alagic and Anne Broadbent and Bill Fefferman and Tommaso Gagliardoni and Christian Schaffner and Michael St. Jules} } @article {1713, title = {On Quantum Obfuscation}, year = {2016}, month = {2016/02/04}, abstract = {Encryption of data is fundamental to secure communication in the modern world. Beyond encryption of data lies obfuscation, i.e., encryption of functionality. It is well-known that the most powerful means of obfuscating classical programs, so-called {\textquoteleft}{\textquoteleft}black-box obfuscation{\textquoteright},{\textquoteright} is provably impossible [Barak et al {\textquoteright}12]. However, several recent results have yielded candidate schemes that satisfy a definition weaker than black-box, and yet still have numerous applications. In this work, we initialize the rigorous study of obfuscating programs via quantum-mechanical means. We define notions of quantum obfuscation which encompass several natural variants. The input to the obfuscator can describe classical or quantum functionality, and the output can be a circuit description or a quantum state. The obfuscator can also satisfy one of a number of obfuscation conditions: black-box, information-theoretic black-box, indistinguishability, and best possible; the last two conditions come in three variants: perfect, statistical, and computational. We discuss many applications, including CPA-secure quantum encryption, quantum fully-homomorphic encryption, and public-key quantum money. We then prove several impossibility results, extending a number of foundational papers on classical obfuscation to the quantum setting. We prove that quantum black-box obfuscation is impossible in a setting where adversaries can possess more than one output of the obfuscator. In particular, generic transformation of quantum circuits into black-box-obfuscated quantum circuits is impossible. We also show that statistical indistinguishability obfuscation is impossible, up to an unlikely complexity-theoretic collapse. Our proofs involve a new tool: chosen-ciphertext-secure encryption of quantum data, which was recently shown to be possible assuming quantum-secure one-way functions exist [Alagic et al {\textquoteright}16].}, url = {http://arxiv.org/abs/1602.01771}, author = {Gorjan Alagic and Bill Fefferman} } @article {1187, title = {Realizing Exactly Solvable SU(N) Magnets with Thermal Atoms}, journal = {Physical Review A}, volume = {93}, year = {2016}, month = {2016/05/06}, abstract = {

We show that n thermal fermionic alkaline-earth-metal atoms in a flat-bottom trap allow one to robustly implement a spin model displaying two symmetries: the Sn symmetry that permutes atoms occupying different vibrational levels of the trap and the SU(N) symmetry associated with N nuclear spin states. The symmetries make the model exactly solvable, which, in turn, enables the analytic study of dynamical processes such as spin diffusion in this SU(N) system. We also show how to use this system to generate entangled states that allow for Heisenberg-limited metrology. This highly symmetric spin model should be experimentally realizable even when the vibrational levels are occupied according to a high-temperature thermal or an arbitrary nonthermal distribution.

}, doi = {10.1103/PhysRevA.93.051601}, url = {http://journals.aps.org/pra/abstract/10.1103/PhysRevA.93.051601}, author = {Michael E. Beverland and Gorjan Alagic and Michael J. Martin and Andrew P. Koller and Ana M. Rey and Alexey V. Gorshkov} } @article {1393, title = {Yang-Baxter operators need quantum entanglement to distinguish knots}, journal = {Journal of Physics A}, volume = {49}, year = {2016}, month = {2016/01/12}, pages = {075203}, abstract = { Any solution to the Yang-Baxter equation yields a family of representations of braid groups. Under certain conditions, identified by Turaev, the appropriately normalized trace of these representations yields a link invariant. Any Yang-Baxter solution can be interpreted as a two-qudit quantum gate. Here we show that if this gate is non-entangling, then the resulting invariant of knots is trivial. We thus obtain a general connection between topological entanglement and quantum entanglement, as suggested by Kauffman et al. }, doi = {10.1088/1751-8113/49/7/075203}, url = {http://arxiv.org/abs/1507.05979}, author = {Gorjan Alagic and Michael Jarret and Stephen P. Jordan} } @article {1391, title = {Classical simulation of Yang-Baxter gates}, journal = {9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)}, volume = {27}, year = {2014}, month = {2014/07/05}, pages = {161-175}, abstract = { A unitary operator that satisfies the constant Yang-Baxter equation immediately yields a unitary representation of the braid group B n for every $n \ge 2$. If we view such an operator as a quantum-computational gate, then topological braiding corresponds to a quantum circuit. A basic question is when such a representation affords universal quantum computation. In this work, we show how to classically simulate these circuits when the gate in question belongs to certain families of solutions to the Yang-Baxter equation. These include all of the qubit (i.e., $d = 2$) solutions, and some simple families that include solutions for arbitrary $d \ge 2$. Our main tool is a probabilistic classical algorithm for efficient simulation of a more general class of quantum circuits. This algorithm may be of use outside the present setting. }, doi = {10.4230/LIPIcs.TQC.2014.161}, url = {http://arxiv.org/abs/1407.1361v1}, author = {Gorjan Alagic and Aniruddha Bapat and Stephen P. Jordan} } @proceedings {1388, title = {Partial-indistinguishability obfuscation using braids}, year = {2014}, month = {2014/08/21}, abstract = {

An obfuscator is an algorithm that translates circuits into functionally-equivalent similarly-sized circuits that are hard to understand. Efficient obfuscators would have many applications in cryptography. Until recently, theoretical progress has mainly been limited to no-go results. Recent works have proposed the first efficient obfuscation algorithms for classical logic circuits, based on a notion of indistinguishability against polynomial-time adversaries. In this work, we propose a new notion of obfuscation, which we call partial-indistinguishability. This notion is based on computationally universal groups with efficiently computable normal forms, and appears to be incomparable with existing definitions. We describe universal gate sets for both classical and quantum computation, in which our definition of obfuscation can be met by polynomial-time algorithms. We also discuss some potential applications to testing quantum computers. We stress that the cryptographic security of these obfuscators, especially when composed with translation from other gate sets, remains an open question.

}, url = {http://arxiv.org/abs/1212.6358}, author = {Gorjan Alagic and Stacey Jeffery and Stephen P. Jordan} } @article {2618, title = {Quantum Algorithms for Invariants of Triangulated Manifolds}, journal = {Quantum Info. Comput. Vol. }, volume = {12}, year = {2012}, pages = {843-863}, abstract = {

One of the apparent advantages of quantum computers over their classical counterparts is their ability to efficiently contract tensor networks. In this article, we study some implications of this fact in the case of topological tensor networks. The graph underlying these networks is given by the triangulation of a manifold, and the structure of the tensors ensures that the overall tensor is independent of the choice of internal triangulation. This leads to quantum algorithms for additively approximating certain invariants of triangulated manifolds. We discuss the details of this construction in two specific cases. In the first case, we consider triangulated surfaces, where the triangle tensor is defined by the multiplication operator of a finite group; the resulting invariant has a simple closed-form expression involving the dimensions of the irreducible representations of the group and the Euler characteristic of the surface. In the second case, we consider triangulated 3-manifolds, where the tetrahedral tensor is defined by the so-called Fibonacci anyon model; the resulting invariant is the well-known Turaev-Viro invariant of 3-manifolds.

}, url = {http://dl.acm.org/citation.cfm?id=2481580.2481588}, author = {Gorjan Alagic and E. A. Bering} } @proceedings {1387, title = {Approximating the Turaev-Viro Invariant of Mapping Tori is Complete for One Clean Qubit}, year = {2011}, month = {2011/05/31}, abstract = {

The Turaev-Viro invariants are scalar topological invariants of three-dimensional manifolds. Here we show that the problem of estimating the Fibonacci version of the Turaev-Viro invariant of a mapping torus is a complete problem for the one clean qubit complexity class (DQC1). This complements a previous result showing that estimating the Turaev-Viro invariant for arbitrary manifolds presented as Heegaard splittings is a complete problem for the standard quantum computation model (BQP). We also discuss a beautiful analogy between these results and previously known results on the computational complexity of approximating the Jones polynomial.

}, url = {http://arxiv.org/abs/1105.5100}, author = {Stephen P. Jordan and Gorjan Alagic} } @article {2617, title = {Spectral Concentration of Positive Functions on Compact Groups}, journal = {Journal of Fourier Analysis and Applications }, volume = {17}, year = {2011}, pages = {355-373}, abstract = {

The problem of understanding the Fourier-analytic structure of the cone of
positive functions on a group has a long history. In this article, we develop the first
quantitative spectral concentration results for such functions over arbitrary compact
groups. Specifically, we describe a family of finite, positive quadrature rules for the
Fourier coefficients of band-limited functions on compact groups. We apply these
quadrature rules to establish a spectral concentration result for positive functions:
given appropriately nested band limits A \⊂ B \⊂ G, we prove a lower bound on the
fraction of L2-mass that any B-band-limited positive function has in A. Our bounds
are explicit and depend only on elementary properties of A and B; they are the first
such bounds that apply to arbitrary compact groups. They apply to finite groups as
a special case, where the quadrature rule is given by the Fourier transform on the
smallest quotient whose dual contains the Fourier support of the function.

}, doi = {https://doi.org/10.1007/s00041-011-9174-5}, author = {Gorjan Alagic and Alexander Russell} } @article {1401, title = {Approximating Turaev-Viro 3-manifold invariants is universal for quantum computation }, journal = {Physical Review A}, volume = {82}, year = {2010}, month = {2010/10/8}, abstract = { The Turaev-Viro invariants are scalar topological invariants of compact, orientable 3-manifolds. We give a quantum algorithm for additively approximating Turaev-Viro invariants of a manifold presented by a Heegaard splitting. The algorithm is motivated by the relationship between topological quantum computers and (2+1)-D topological quantum field theories. Its accuracy is shown to be nontrivial, as the same algorithm, after efficient classical preprocessing, can solve any problem efficiently decidable by a quantum computer. Thus approximating certain Turaev-Viro invariants of manifolds presented by Heegaard splittings is a universal problem for quantum computation. This establishes a novel relation between the task of distinguishing non-homeomorphic 3-manifolds and the power of a general quantum computer. }, doi = {10.1103/PhysRevA.82.040302}, url = {http://arxiv.org/abs/1003.0923v1}, author = {Gorjan Alagic and Stephen P. Jordan and Robert Koenig and Ben W. Reichardt} } @article {2616, title = {Quantum Algorithms for Simon{\textquoteright}s Problem over Nonabelian Groups}, journal = {ACM Trans. Algorithms}, volume = {6}, year = {2010}, abstract = {

Daniel Simon\&$\#$39;s 1994 discovery of an efficient quantum algorithm for finding \“hidden shifts\” of Z2n provided the first algebraic problem for which quantum computers are exponentially faster than their classical counterparts. In this article, we study the generalization of Simon\&$\#$39;s problem to arbitrary groups. Fixing a finite group G, this is the problem of recovering an involution m = (m1,\…,mn) \∈ Gn from an oracle f with the property that f(x \⋅ y) = f(x) \⇔ y \∈ {1, m}. In the current parlance, this is the hidden subgroup problem (HSP) over groups of the form Gn, where G is a nonabelian group of constant size, and where the hidden subgroup is either trivial or has order two.

Although groups of the form Gn have a simple product structure, they share important representation--theoretic properties with the symmetric groups Sn, where a solution to the HSP would yield a quantum algorithm for Graph Isomorphism. In particular, solving their HSP with the so-called \“standard method\” requires highly entangled measurements on the tensor product of many coset states.

In this article, we provide quantum algorithms with time complexity 2O(\√n) that recover hidden involutions m = (m1,\…mn) \∈ Gn where, as in Simon\&$\#$39;s problem, each mi is either the identity or the conjugate of a known element m which satisfies κ(m) = \−κ(1) for some κ \∈ Gh. Our approach combines the general idea behind Kuperberg\&$\#$39;s sieve for dihedral groups with the \“missing harmonic\” approach of Moore and Russell. These are the first nontrivial HSP algorithms for group families that require highly entangled multiregister Fourier sampling.

}, doi = {https://doi.org/10.1145/1644015.1644034}, author = {Gorjan Alagic and Cristopher Moore and Alexander Russell} } @article {2615, title = {Uncertainty principles for compact groups}, journal = {Illinois J. Math. }, volume = {52}, year = {2008}, pages = {1315-1324}, abstract = {

We establish an uncertainty principle over arbitrary compact groups, generalizing several previous results. Specifically, we show that if P and R are operators on L2(G) such that P commutes with projection onto every measurable subset of G and R commutes with left-multiplication by elements of G, then ||PR||\≤||P\⋅χG||2||R||2, where χG:g↦1 is the characteristic function of G. As a consequence, we show that every nonzero function f in L2(G) satisfies μ(suppf)\⋅\∑ρ\∈G^dρrankf^(ρ)\≥1.

}, doi = {doi:10.1215/ijm/1258554365}, url = {http://projecteuclid.org/euclid.ijm/1258554365}, author = {Gorjan Alagic and Alexander Russell} } @article {2613, title = {Quantum Algorithms for Simon{\textquoteright}s Problem over General Groups}, journal = {SODA {\textquoteright}07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms}, year = {2007}, month = {1/25/2007}, pages = {1217{\textendash}1224}, abstract = {

Daniel Simon\&$\#$39;s 1994 discovery of an efficient quantum algorithm for solving the hidden subgroup problem (HSP) over Zn2 provided one of the first algebraic problems for which quantum computers are exponentially faster than their classical counterparts. In this paper, we study the generalization of Simon\&$\#$39;s problem to arbitrary groups. Fixing a finite group G, this is the problem of recovering an involution m = (m1,...,mn) ε Gn from an oracle f with the property that f(x) = f(x \· y) \⇔ y ε {1, m}. In the current parlance, this is the hidden subgroup problem (HSP) over groups of the form Gn, where G is a nonabelian group of constant size, and where the hidden subgroup is either trivial or has order two.

Although groups of the form Gn have a simple product structure, they share important representation-theoretic properties with the symmetric groups Sn, where a solution to the HSP would yield a quantum algorithm for Graph Isomorphism. In particular, solving their HSP with the so-called \"standard method\" requires highly entangled measurements on the tensor product of many coset states.

Here we give quantum algorithms with time complexity 2O(\√n log n) that recover hidden involutions m = (m1,..., mn) ε Gn where, as in Simon\&$\#$39;s problem, each mi is either the identity or the conjugate of a known element m and there is a character X of G for which X(m) = - X(1). Our approach combines the general idea behind Kuperberg\&$\#$39;s sieve for dihedral groups with the \"missing harmonic\" approach of Moore and Russell. These are the first nontrivial hidden subgroup algorithms for group families that require highly entangled multiregister Fourier sampling.

}, doi = {https://dl.acm.org/doi/10.5555/1283383.1283514}, url = {https://arxiv.org/abs/quant-ph/0603251}, author = {Gorjan Alagic and Cristopher Moore and Alexander Russell} } @article {2614, title = {Quantum Computing and the Hunt for Hidden Symmetry}, journal = {Bulletin of the EATCS}, volume = {93}, year = {2007}, pages = {53-75}, abstract = {

In 1994, Peter Shor gave e cient quantum algorithms for factoring integers and extracting discrete logarithms [20]. If we believe that nature will permit us to faithfully implement our current model of quantum computation, then these algorithms dramatically contradict the Strong Church-Turing thesis. The e ect is heightened by the fact that these algorithms solve computational problems with long histories of attention by the computational and mathematical communities alike. In this article we discuss the branch of quantum algorithms research arising from attempts to generalize the core quantum algorithmic aspects of Shor\&$\#$39;s algorithms. Roughly, this can be viewed as the problem of generalizing algorithms of Simon [21] and Shor [20], which work over abelian groups, to general nonabelian groups. The article is meant to be self-contained, assuming no knowledge of quantum computing or the representation theory of nite groups. We begin in earnest in Section 2, describing the problem of symmetry nding : given a function f : G \→ S on a group G, this is the problem of determining {g \∈ G | \∀x, f(x) = f(gx)}, the set of symmetries of f . We switch gears in Section 3, giving a short introduction to the circuit model of quantum computation. The connection between these two sections is eventually established in Section 4, where we discuss the representation theory of nite groups and the quantum Fourier transform a unitary transformation speci cally tuned to the symmetries of the underlying group. Section 4.2 is devoted to Fourier

}, url = {https://pdfs.semanticscholar.org/08f7/abc04ca0bd38c1351ee1179139d8b0fc172b.pdf?_ga=2.210619804.800377824.1595266095-1152452310.1595266095}, author = {Gorjan Alagic and Alexander Russell} } @article {2612, title = {Decoherence in Quantum Walks on the Hypercube }, journal = {Phys. Rev. A }, volume = {76}, year = {2005}, month = {12/5/2005}, pages = {062304}, abstract = {

We study a natural notion of decoherence on quantum random walks over the hypercube. We prove that in this model there is a decoherence threshold beneath which the essential properties of the hypercubic quantum walk, such as linear mixing times, are preserved. Beyond the threshold, we prove that the walks behave like their classical counterparts.

}, doi = {https://doi.org/10.1103/PhysRevA.72.062304}, url = {https://arxiv.org/abs/quant-ph/0501169}, author = {Gorjan Alagic and Alexander Russell} } @article {2611, title = {Strong Fourier Sampling Fails over Gn}, year = {2005}, month = {11/7/2005}, abstract = {

We present a negative result regarding the hidden subgroup problem on the powers Gn of a fixed group G. Under a condition on the base group G, we prove that strong Fourier sampling cannot distinguish some subgroups of Gn. Since strong sampling is in fact the optimal measurement on a coset state, this shows that we have no hope of efficiently solving the hidden subgroup problem over these groups with separable measurements on coset states (that is, using any polynomial number of single-register coset state experiments). Base groups satisfying our condition include all nonabelian simple groups. We apply our results to show that there exist uniform families of nilpotent groups whose normal series factors have constant size and yet are immune to strong Fourier sampling.

}, url = {https://arxiv.org/abs/quant-ph/0511054}, author = {Gorjan Alagic and Cristopher Moore and Alexander Russell} }