01459nas a2200145 4500008004100000245005100041210004300092260001400135520105500149100001901204700001401223700002301237700001601260856003701276 2023 eng d00aOn the Two-sided Permutation Inversion Problem0 aTwosided Permutation Inversion Problem c6/23/20233 a

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.

1 aAlagic, Gorjan1 aBai, Chen1 aPoremba, Alexander1 aShi, Kaiyan uhttps://arxiv.org/abs/2306.1372901696nas a2200145 4500008004100000245005300041210005100094260001500145520127900160100001901439700001401458700001901472700002201491856003701513 2022 eng d00aPost-Quantum Security of the Even-Mansour Cipher0 aPostQuantum Security of the EvenMansour Cipher c12/14/20213 a

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. 

1 aAlagic, Gorjan1 aBai, Chen1 aKatz, Jonathan1 aMajenz, Christian uhttps://arxiv.org/abs/2112.0753001152nas a2200157 4500008004100000245007900041210006900120260001400189520065900203100001900862700001400881700001900895700002200914700002000936856003800956 2022 eng d00aPost-Quantum Security of the (Tweakable) FX Construction, and Applications0 aPostQuantum Security of the Tweakable FX Construction and Applic c8/29/20223 a

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's lightweight cryptography standardization effort), and Chaskey (an ISO-standardized lightweight MAC

1 aAlagic, Gorjan1 aBai, Chen1 aKatz, Jonathan1 aMajenz, Christian1 aStruck, Patrick uhttps://eprint.iacr.org/2022/109702778nas a2200241 4500008004100000245009900041210006900140260001100209520197600220100001902196700001702215700001802232700001602250700001602266700001702282700002202299700001702321700001802338700001802356700001702374700002102391856012402412 2022 eng d00aStatus Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process0 aStatus Report on the Third Round of the NIST PostQuantum Cryptog c7/20223 a

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.

1 aAlagic, Gorjan1 aApon, Daniel1 aCooper, David1 aDang, Quynh1 aDang, Thinh1 aKelsey, John1 aLichtinger, Jacob1 aMiller, Carl1 aMoody, Dustin1 aPeralta, Rene1 aPerlner, Ray1 aRobinson, Angela uhttps://www.quics.umd.edu/publications/status-report-third-round-nist-post-quantum-cryptography-standardization-process02266nas a2200133 4500008004100000245003400041210003300075260001400108520190700122100001902029700002502048700002202073856003702095 2021 eng d00aCan you sign a quantum state?0 aCan you sign a quantum state c12/6/20213 a

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.

1 aAlagic, Gorjan1 aGagliardoni, Tommaso1 aMajenz, Christian uhttps://arxiv.org/abs/1811.1185801905nas a2200157 4500008004100000245006300041210006300104260001300167300001200180490001000192520138200202100001901584700002201603700002301625856009901648 2020 eng d00aEfficient Simulation of Random States and Random Unitaries0 aEfficient Simulation of Random States and Random Unitaries c5/1/2020 a759-7870 v121073 a

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.

1 aAlagic, Gorjan1 aMajenz, Christian1 aRussell, Alexander uhttps://www.quics.umd.edu/publications/efficient-simulation-random-states-and-random-unitaries01375nas a2200145 4500008004100000245008100041210006900122260001400191520090600205100001901111700002101130700001601151700002501167856003701192 2020 eng d00aImpossibility of Quantum Virtual Black-Box Obfuscation of Classical Circuits0 aImpossibility of Quantum Virtual BlackBox Obfuscation of Classic c5/13/20203 a

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.

1 aAlagic, Gorjan1 aBrakerski, Zvika1 aDulek, Yfke1 aSchaffner, Christian uhttps://arxiv.org/abs/2005.0643201889nas a2200169 4500008004100000245006600041210006500107260001300172300001200185490004400197520136000241100001901601700002301620700002001643700001901663856003701682 2020 eng d00aNon-interactive classical verification of quantum computation0 aNoninteractive classical verification of quantum computation c3/9/2020 a153-1800 vLecture Notes in Computer Science 125523 a

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.

1 aAlagic, Gorjan1 aChilds, Andrew, M.1 aGrilo, Alex, B.1 aHung, Shih-Han uhttps://arxiv.org/abs/1911.0810102525nas a2200169 4500008004100000245006600041210006200107260001400169300000700183490000600190520198300196100001902179700002002198700001702218700002302235856009702258 2020 eng d00aOn Quantum Chosen-Ciphertext Attacks and Learning with Errors0 aQuantum ChosenCiphertext Attacks and Learning with Errors c3/21/2020 a100 v43 a

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.

1 aAlagic, Gorjan1 aJeffery, Stacey1 aOzols, Maris1 aPoremba, Alexander uhttps://www.quics.umd.edu/publications/quantum-chosen-ciphertext-attacks-and-learning-errors02359nas a2200169 4500008004100000245007400041210006900115260001300184300001300197490001000210520178100220100001902001700002202020700002302042700001502065856010902080 2020 eng d00aQuantum-Access-Secure Message Authentication via Blind-Unforgeability0 aQuantumAccessSecure Message Authentication via BlindUnforgeabili c5/1/2020 a788-817 0 v12-173 a

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.

1 aAlagic, Gorjan1 aMajenz, Christian1 aRussell, Alexander1 aSong, Fang uhttps://www.quics.umd.edu/publications/quantum-access-secure-message-authentication-blind-unforgeability03210nas a2200253 4500008004100000245010000041210006900141260001200210520236500222100001902587700002702606700001702633700001802650700001602668700001702684700001602701700001702717700001802734700001802752700001702770700002102787700002302808856012502831 2020 eng d00aStatus Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process0 aStatus Report on the Second Round of the NIST PostQuantum Crypto c07/20203 a

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.

1 aAlagic, Gorjan1 aAlperin-Sheriff, Jacob1 aApon, Daniel1 aCooper, David1 aDang, Quynh1 aKelsey, John1 aLiu, Yi-Kai1 aMiller, Carl1 aMoody, Dustin1 aPeralta, Rene1 aPerlner, Ray1 aRobinson, Angela1 aSmith-Tone, Daniel uhttps://www.quics.umd.edu/publications/status-report-second-round-nist-post-quantum-cryptography-standardization-process02399nas a2200145 4500008004100000245007900041210006900120300001400189520193400203100001902137700002002156700001702176700002302193856003702216 2019 eng d00aOn non-adaptive quantum chosen-ciphertext attacks and Learning with Errors0 anonadaptive quantum chosenciphertext attacks and Learning with E a1:1-1:23 3 a

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. 

1 aAlagic, Gorjan1 aJeffery, Stacey1 aOzols, Maris1 aPoremba, Alexander uhttps://arxiv.org/abs/1808.0965502754nas a2200229 4500008004100000245009900041210006900140520205300209100001902262700002402281700001302305700001502318700001302333700001702346700001402363700001602377700001602393700001702409700001902426700001602445856006302461 2019 eng d00aStatus Report on the First Round of the NIST Post-Quantum Cryptography Standardization Process0 aStatus Report on the First Round of the NIST PostQuantum Cryptog3 a

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

1 aAlagic, Gorjan1 aAlperin-Sheriff, J.1 aApon, D.1 aCooper, D.1 aDang, Q.1 aMiller, Carl1 aMoody, D.1 aPeralta, R.1 aPerlner, R.1 aRobinson, A.1 aSmith-Tone, D.1 aLiu, Yi-Kai uhttps://nvlpubs.nist.gov/nistpubs/ir/2019/NIST.IR.8240.pdf02448nas a2200133 4500008004100000245006700041210006500108520202500173100001902198700002202217700002302239700001502262856003702277 2018 eng d00aQuantum-secure message authentication via blind-unforgeability0 aQuantumsecure message authentication via blindunforgeability3 a

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. 

1 aAlagic, Gorjan1 aMajenz, Christian1 aRussell, Alexander1 aSong, Fang uhttps://arxiv.org/abs/1803.0376101204nas a2200181 4500008004100000245007100041210006900112260001500181490000800196520064500204100002700849700001900876700001900895700002700914700002000941700002500961856003600986 2018 eng d00aSpectrum estimation of density operators with alkaline-earth atoms0 aSpectrum estimation of density operators with alkalineearth atom c2018/01/090 v1203 a

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.

1 aBeverland, Michael, E.1 aHaah, Jeongwan1 aAlagic, Gorjan1 aCampbell, Gretchen, K.1 aRey, Ana, Maria1 aGorshkov, Alexey, V. uhttp://arxiv.org/abs/1608.0204501724nas a2200133 4500008004100000245003500041210003500076490001000111520132700121100001901448700002501467700002201492856007601514 2018 eng d00aUnforgeable Quantum Encryption0 aUnforgeable Quantum Encryption0 v108223 a

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.

1 aAlagic, Gorjan1 aGagliardoni, Tommaso1 aMajenz, Christian uhttps://www.quics.umd.edu/publications/unforgeable-quantum-encryption-001312nas a2200133 4500008004100000245003600041210003500077300001300112490000700125520096100132100001901093700001101112856005501123 2017 eng d00a3-manifold diagrams and NP vs P0 a3manifold diagrams and NP vs P a125-141 0 v173 a

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.

1 aAlagic, Gorjan1 aLo, C. uhttps://dl.acm.org/doi/abs/10.5555/3179483.317949101898nas a2200157 4500008004100000245005900041210005900100260001500159300001200174520143500186100001901621700001601640700002501656700002201681856003701703 2017 eng d00aQuantum Fully Homomorphic Encryption With Verification0 aQuantum Fully Homomorphic Encryption With Verification c2017/11/30 a438-4673 a

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.

1 aAlagic, Gorjan1 aDulek, Yfke1 aSchaffner, Christian1 aSpeelman, Florian uhttps://arxiv.org/abs/1708.0915601828nas a2200121 4500008004100000245004800041210004700089490001000136520143200146100001901578700002201597856008701619 2017 eng d00aQuantum Non-malleability and Authentication0 aQuantum Nonmalleability and Authentication0 v104023 a

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

1 aAlagic, Gorjan1 aMajenz, Christian uhttps://www.quics.umd.edu/publications/quantum-non-malleability-and-authentication02297nas a2200121 4500008004100000245006900041210006700110490001000177520184100187100001902028700002302047856010502070 2017 eng d00aQuantum-Secure Symmetric-Key Cryptography Based on Hidden Shifts0 aQuantumSecure SymmetricKey Cryptography Based on Hidden Shifts0 v102123 a

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.

1 aAlagic, Gorjan1 aRussell, Alexander uhttps://www.quics.umd.edu/publications/quantum-secure-symmetric-key-cryptography-based-hidden-shifts01731nas a2200133 4500008004100000245003500041210003500076260001500111520136800126100001901494700002501513700002201538856003701560 2017 eng d00aUnforgeable Quantum Encryption0 aUnforgeable Quantum Encryption c2017/09/193 a

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.

1 aAlagic, Gorjan1 aGagliardoni, Tommaso1 aMajenz, Christian uhttps://arxiv.org/abs/1709.0653901599nas a2200169 4500008004100000245004900041210004900090260001500139520107400154100001901228700002001247700002001267700002501287700002501312700002401337856006801361 2016 eng d00aComputational Security of Quantum Encryption0 aComputational Security of Quantum Encryption c2016/11/103 a

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.

1 aAlagic, Gorjan1 aBroadbent, Anne1 aFefferman, Bill1 aGagliardoni, Tommaso1 aSchaffner, Christian1 aJules, Michael, St. uhttps://link.springer.com/chapter/10.1007%2F978-3-319-49175-2_302209nas a2200121 4500008004100000245002700041210002400068260001500092520190500107100001902012700002002031856003602051 2016 eng d00aOn Quantum Obfuscation0 aQuantum Obfuscation c2016/02/043 aEncryption 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 ``black-box obfuscation',' is provably impossible [Barak et al '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 '16].1 aAlagic, Gorjan1 aFefferman, Bill uhttp://arxiv.org/abs/1602.0177101353nas a2200181 4500008004100000245006400041210006200105260001500167490000700182520077900189100002700968700001900995700002401014700002301038700001701061700002501078856006801103 2016 eng d00aRealizing Exactly Solvable SU(N) Magnets with Thermal Atoms0 aRealizing Exactly Solvable SUN Magnets with Thermal Atoms c2016/05/060 v933 a

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.

1 aBeverland, Michael, E.1 aAlagic, Gorjan1 aMartin, Michael, J.1 aKoller, Andrew, P.1 aRey, Ana, M.1 aGorshkov, Alexey, V. uhttp://journals.aps.org/pra/abstract/10.1103/PhysRevA.93.05160101014nas a2200157 4500008004100000245007300041210006900114260001500183300001100198490000700209520054100216100001900757700002000776700002400796856003600820 2016 eng d00aYang-Baxter operators need quantum entanglement to distinguish knots0 aYangBaxter operators need quantum entanglement to distinguish kn c2016/01/12 a0752030 v493 a 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. 1 aAlagic, Gorjan1 aJarret, Michael1 aJordan, Stephen, P. uhttp://arxiv.org/abs/1507.0597901280nas a2200157 4500008004100000245004600041210004500087260001500132300001200147490000700159520085500166100001901021700002101040700002401061856003701085 2014 eng d00aClassical simulation of Yang-Baxter gates0 aClassical simulation of YangBaxter gates c2014/07/05 a161-1750 v273 a 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. 1 aAlagic, Gorjan1 aBapat, Aniruddha1 aJordan, Stephen, P. uhttp://arxiv.org/abs/1407.1361v101518nas a2200133 4500008004100000245005800041210005700099260001500156520111500171100001901286700002001305700002401325856003501349 2014 eng d00aPartial-indistinguishability obfuscation using braids0 aPartialindistinguishability obfuscation using braids c2014/08/213 a

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.

1 aAlagic, Gorjan1 aJeffery, Stacey1 aJordan, Stephen, P. uhttp://arxiv.org/abs/1212.635801584nas a2200133 4500008004100000245006400041210006400105300001200169490000700181520117000188100001901358700001901377856005401396 2012 eng d00aQuantum Algorithms for Invariants of Triangulated Manifolds0 aQuantum Algorithms for Invariants of Triangulated Manifolds a843-8630 v123 a

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.

1 aAlagic, Gorjan1 aBering, E., A. uhttp://dl.acm.org/citation.cfm?id=2481580.248158801079nas a2200121 4500008004100000245009300041210006900134260001500203520066100218100002400879700001900903856003500922 2011 eng d00aApproximating the Turaev-Viro Invariant of Mapping Tori is Complete for One Clean Qubit0 aApproximating the TuraevViro Invariant of Mapping Tori is Comple c2011/05/313 a

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.

1 aJordan, Stephen, P.1 aAlagic, Gorjan uhttp://arxiv.org/abs/1105.510001537nas a2200133 4500008004100000245006700041210006700108300001200175490000700187520106700194100001901261700002301280856010001303 2011 eng d00aSpectral Concentration of Positive Functions on Compact Groups0 aSpectral Concentration of Positive Functions on Compact Groups a355-3730 v173 a

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.

1 aAlagic, Gorjan1 aRussell, Alexander uhttps://www.quics.umd.edu/publications/spectral-concentration-positive-functions-compact-groups01327nas a2200157 4500008004100000245009200041210006900133260001400202490000700216520082400223100001901047700002401066700001901090700002301109856003701132 2010 eng d00aApproximating Turaev-Viro 3-manifold invariants is universal for quantum computation 0 aApproximating TuraevViro 3manifold invariants is universal for q c2010/10/80 v823 a 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. 1 aAlagic, Gorjan1 aJordan, Stephen, P.1 aKoenig, Robert1 aReichardt, Ben, W. uhttp://arxiv.org/abs/1003.0923v102230nas a2200133 4500008004100000245006800041210006600109490000600175520174200181100001901923700002201942700002301964856010901987 2010 eng d00aQuantum Algorithms for Simon’s Problem over Nonabelian Groups0 aQuantum Algorithms for Simon s Problem over Nonabelian Groups0 v63 a

Daniel Simon'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'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's problem, each mi is either the identity or the conjugate of a known element m which satisfies κ(m) = −κ(1) for some κ ∈ Ĝ. Our approach combines the general idea behind Kuperberg'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.

1 aAlagic, Gorjan1 aMoore, Cristopher1 aRussell, Alexander uhttps://www.quics.umd.edu/publications/quantum-algorithms-simon%E2%80%99s-problem-over-nonabelian-groups00912nas a2200133 4500008004100000245004600041210004600087300001400133490000700147520053100154100001900685700002300704856005100727 2008 eng d00aUncertainty principles for compact groups0 aUncertainty principles for compact groups a1315-13240 v523 a

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.

1 aAlagic, Gorjan1 aRussell, Alexander uhttp://projecteuclid.org/euclid.ijm/125855436502185nas a2200145 4500008004100000245006500041210006300106260001400169300001600183520173300199100001901932700002201951700002301973856004301996 2007 eng d00aQuantum Algorithms for Simon’s Problem over General Groups0 aQuantum Algorithms for Simon s Problem over General Groups c1/25/2007 a1217–12243 a

Daniel Simon'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'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'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'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.

1 aAlagic, Gorjan1 aMoore, Cristopher1 aRussell, Alexander uhttps://arxiv.org/abs/quant-ph/060325102060nas a2200133 4500008004100000245005500041210005500096300001000151490000700161520157400168100001901742700002301761856014201784 2007 eng d00aQuantum Computing and the Hunt for Hidden Symmetry0 aQuantum Computing and the Hunt for Hidden Symmetry a53-750 v933 a

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'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

1 aAlagic, Gorjan1 aRussell, Alexander uhttps://pdfs.semanticscholar.org/08f7/abc04ca0bd38c1351ee1179139d8b0fc172b.pdf?_ga=2.210619804.800377824.1595266095-1152452310.159526609500765nas a2200145 4500008004100000245005100041210005000092260001400142300001100156490000700167520036000174100001900534700002300553856004300576 2005 eng d00aDecoherence in Quantum Walks on the Hypercube 0 aDecoherence in Quantum Walks on the Hypercube c12/5/2005 a0623040 v763 a

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.

1 aAlagic, Gorjan1 aRussell, Alexander uhttps://arxiv.org/abs/quant-ph/050116901168nas a2200133 4500008004100000245004200041210004200083260001400125520078800139100001900927700002200946700002300968856004300991 2005 eng d00aStrong Fourier Sampling Fails over Gn0 aStrong Fourier Sampling Fails over Gn c11/7/20053 a

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.

1 aAlagic, Gorjan1 aMoore, Cristopher1 aRussell, Alexander uhttps://arxiv.org/abs/quant-ph/0511054