检索结果-内蒙古大学图书馆

Beyond quadratic speedups in quantum attacks on symmetric schemes

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Bonnetain, Xavier Schrottenloher, André Sibleyras, Ferdinand Institute for Quantum Computing Department of Combinatorics and Optimization University of Waterloo WaterlooON Canada Université de Lorraine CNRS Inria Nancy France Cryptology Group CWI Amsterdam Netherlands NTT Social Informatics Laboratories

In this paper, we report the first quantum key-recovery attack on a symmetric block cipher design, using classical queries only, with a more than quadratic time speedup compared to the best classical attack. We study the 2XOR-Cascade construction of Gaži and Tessaro (EUROCRYPT 2012). It is a key length extension technique which provides an n-bit block cipher with 5n/2 bits of security out of an n-bit block cipher with 2n bits of key, with a security proof in the ideal model. We show that the offline-Simon algorithm of Bonnetain et al. (ASIACRYPT 2019) can be extended to, in particular, attack this construction in quantum time Õ(2n), providing a 2.5 quantum speedup over the best classical attack. Regarding post-quantum security of symmetric ciphers, it is commonly assumed that doubling the key sizes is a sufficient precaution. This is because Grover's quantum search algorithm, and its derivatives, can only reach a quadratic speedup at most. Our attack shows that the structure of some symmetric constructions can be exploited to overcome this limit. In particular, the 2XOR-Cascade cannot be used to generically strengthen block ciphers against quantum adversaries, as it would offer only the same security as the block cipher itself. Copyright © 2021, The Authors. All rights reserved.

关键词： quantum cryptography

Limitations of the Macaulay matrix approach for using the HHL algorithm to solve multivariate polynomial systems

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Ding, Jintai Gheorghiu, Vlad Gilyén, András Hallgren, Sean Li, Jianqiang University of Cincinnati OH United States Institute for Quantum Computing Dept. of Combinatorics & Optimization University of Waterloo ON Canada Institute for Quantum Information and Matter Caltech PasadenaCA United States Department of Computer Science and Engineering Pennsylvania State University PA United States

Recently Chen and Gao [CG21] proposed a new quantum algorithm for Boolean polynomial system solving, motivated by the cryptanalysis of some post-quantum cryptosystems. The key idea of their approach is to apply a quantum Linear System (QLS) algorithm to a Macaulay linear system over C, which is derived from the Boolean polynomial system. The efficiency of their algorithm depends on the condition number of the Macaulay matrix. In this paper, we give a strong lower bound on the condition number as a function of the Hamming weight of the Boolean solution, and show that in many (if not all) cases a Grover-based exhaustive search algorithm outperforms their algorithm. Then, we improve upon Chen and Gao’s algorithm by introducing the Boolean Macaulay linear system over C by reducing the original Macaulay linear system. This improved algorithm could potentially significantly outperform the brute-force algorithm, when the Hamming weight of the solution is logarithmic in the number of Boolean variables. © 2021, CC BY.

关键词： Linear systems

A (quasi-)polynomial time heuristic algorithm for synthesizing T-depth optimal circuits

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Gheorghiu, Vlad Mosca, Michele Mukhopadhyay, Priyanka Institute for Quantum Computing University of Waterloo WaterlooON Canada softwareQ Inc. KitchenerON Canada Dept. of Combinatorics and Optimization University of Waterloo WaterlooON Canada Perimeter Institute for Theoretical Physics WaterlooON Canada

We investigate the problem of synthesizing T-depth optimal quantum circuits over the Clifford+T gate set. First we construct a special subset of T-depth 1 unitaries, such that it is possible to express the T-depth-optimal decomposition of any unitary as product of unitaries from this subset and a Clifford (up to global phase). The cardinality of this subset is at most n·25.6n. We use nested meet-in-the-middle (MITM) technique to develop algorithms for synthesizing provably depth-optimal and T-depth-optimal circuits for exactly implementable unitaries. Specifically, for synthesizing T-depth-optimal circuits, we get an algorithm with space and time complexity (Equation presented) and (Equation presented) respectively, where d is the minimum T-depth and c ≥ 2 is a constant. This is much better than the complexity of the algorithm by Amy et al.(2013), the previous best with a complexity (Equation presented), where k > 2.5 is a constant. We design an even more efficient algorithm for synthesizing T-depth-optimal circuits. The claimed efficiency and optimality depends on some conjectures, which have been inspired from the work of Mosca and Mukhopadhyay (2020). To the best of our knowledge, the conjectures are not related to the previous work. Our algorithm has space and time complexity poly(n, 25.6n, d) (or poly(nlog n, 25.6n, d) under some weaker assumptions). © 2021, CC BY-NC-ND.

关键词： Heuristic algorithms

Interactive quantum advantage with noisy, shallow Clifford circuits

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Grier, Daniel Ju, Nathan Schaeffer, Luke Institute for Quantum Computing University of Waterloo Canada Cheriton School of Computer Science University of Waterloo Canada Department of Computer Science University of Illinois Urbana-ChampaignIL United States Department of Combinatorics and Optimization University of Waterloo Canada

Recent work by Bravyi et al. constructs a relation problem that a noisy constant-depth quantum circuit (QNC0) can solve with near certainty (probability 1 − o(1)), but that any bounded fan-in constant-depth classical circuit (NC0) fails with some constant probability. We show that this robustness to noise can be achieved in the other low-depth quantum/classical circuit separations in this area. In particular, we show a general strategy for adding noise tolerance to the interactive protocols of Grier and Schaeffer. As a consequence, we obtain an unconditional separation between noisy QNC0 circuits and AC0[p] circuits for all primes p ≥ 2, and a conditional separation between noisy QNC0 circuits and log-space classical machines under a plausible complexity-theoretic conjecture. A key component of this reduction is showing average-case hardness for the classical simulation tasks—that is, showing that a classical simulation of the quantum interactive task is still powerful even if it is allowed to err with constant probability over a uniformly random input. We show this is true even for quantum interactive tasks which are L-hard to simulate. To do this, we borrow techniques from randomized encodings used in cryptography. Copyright © 2021, The Authors. All rights reserved.

关键词： Timing circuits

Generating graph states with a single quantum emitter and the minimum number of fusions

学校读者我要写书评

暂无评论

Physical Review A 2025年第5期111卷 052604-052604页

作者： Matthias C. Löbl Love A. Pettersson Andrew Jena Luca Dellantonio Stefano Paesani Anders S. Sørensen Department of Combinatorics and Optimization University of Waterloo and Institute for Quantum Computing University of Waterloo Ontario Canada Department of Physics and Astronomy University of Exeter Stocker Road Exeter EX4 4QL United Kingdom NNF Quantum Computing Programme Niels Bohr Institute University of Copenhagen Blegdamsvej 17 DK-2100 Copenhagen Ø Denmark

Graph states are the key resources for measurement- and fusion-based quantum computing with photons, yet their creation is experimentally challenging. We optimize a hybrid graph-state generation scheme using a single quantum emitter and linear optics Bell-state measurements called fusions. We first generate a restricted class of states from a single quantum emitter and then apply fusions to create a target graph state, where we use a dynamic programming approach to find the construction that requires the lowest possible number of fusions. Our analysis yields a lookup table for constructing ≈2.8×107 nonisomorphic graph states with the minimum number of fusions. The lookup table covers all graph states with up to eight qubits and several other ones with up to 14 qubits. We present construction protocols of selected graph states and provide the lookup table. For large graph states that are not in the lookup table, we derive bounds for the required number of fusions using graph-theoretic properties. Finally, we use the lookup table to search for the best graph codes for loss-tolerant encodings, given a fixed number of fusions for their construction.

关键词： Qubits

T-count and T-depth of any multi-qubit unitary

学校读者我要写书评

暂无评论

arXiv 2021年

While implementing a quantum algorithm it is crucial to reduce the quantum resources, in order to obtain the desired computational advantage. For most fault-tolerant quantum error-correcting codes the cost of implementing the non-Clifford gate is the highest among all the gates in a universal fault-tolerant gate set. In this paper we design an algorithm to determine the (minimum possible) T-count of any n-qubit (n ≥ 1) unitary W of size 2n × 2n, over the Clifford+T gate set. The space and time complexity of our algorithm are O (22n) and O (22nT∈(W)+4n) respectively. T∈(W) (∈-T-count) is the (minimum possible) T-count of an exactly implementable unitary U i.e. T (U), such that d(U, W) ≤ ∈ and T (U) ≤ T (U0) where U0 is any exactly implementable unitary with d(U0, W) ≤ ∈. d(., .) is the global phase invariant distance. Our algorithm can also be used to determine the (minimum possible) T-depth of any multi-qubit unitary and the complexity has exponential dependence on n and ∈-T-depth. This is the first algorithm that gives T-count or T-depth of any multi-qubit (n ≥ 1) unitary. For small enough ∈, we can synthesize the T-count and T-depth-optimal circuits. Our results can be used to determine the minimum count (or depth) of non-Clifford gates required to implement any multi-qubit unitary with a finite universal gate set consisting of Clifford and non-Clifford gates like Clifford+CS, Clifford+V, etc. To the best of our knowledge, there were no such optimal-synthesis algorithms for arbitrary multi-qubit unitaries in any universal gate set, considering any distance metric. © 2021, CC BY.

关键词： Qubits

quantum period finding against symmetric primitives in practice

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Bonnetain, Xavier Jaques, Samuel Institute for Quantum Computing Department of Combinatorics and Optimization University of Waterloo Canada Department of Materials University of Oxford United Kingdom

We present the first complete implementation of the offline Simon’s algorithm, and estimate its cost to attack the MAC Chaskey, the block cipher PRINCE and the NIST lightweight candidate AEAD scheme Elephant. These attacks require a reasonable amount of qubits, comparable to the number of qubits required to break RSA-2048. They are faster than other collision algorithms, and the attacks against PRINCE and Chaskey are the most efficient known to date. As Elephant has a key smaller than its state size, the algorithm is less efficient and ends up more expensive than exhaustive search. We also propose an optimized quantum circuit for boolean linear algebra as well as complete reversible implementations of PRINCE, Chaskey, spongent and Keccak which are of independent interest for quantum cryptanalysis. We stress that our attacks could be applied in the future against today’s communications, and recommend caution when choosing symmetric constructions for cases where long-term security is expected. Copyright © 2020, The Authors. All rights reserved.

关键词： Qubits

Improved upper bounds on the stabilizer rank of magic states

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Qassim, Hammam Pashayan, Hakop Gosset, David Institute for Quantum Computing University of Waterloo WaterlooON Canada Department of Physics and Astronomy University of Waterloo WaterlooON Canada Keysight Technologies Canada Inc. Canada Department of Combinatorics and Optimization University of Waterloo ON Canada Perimeter Institute for Theoretical Physics WaterlooON Canada

In this work we improve the runtime of recent classical algorithms for strong simulation of quantum circuits composed of Clifford and T gates. The improvement is obtained by establishing a new upper bound on the stabilizer rank of m copies of the magic state T = √2-1(|0i + eiπ/4|1i) in the limit of large m. In particular, we show that T⊗m can be exactly expressed as a superposition of at most O(2αm) stabilizer states, where α ≤ 0.3963, improving on the best previously known bound α ≤ 0.463. This furnishes, via known techniques, a classical algorithm which approximates output probabilities of an n-qubit 'Clifford + T' circuit U with m uses of the T gate to within a given inverse polynomial relative error using a runtime poly(n,m)2αm. We also provide improved upper bounds on the stabilizer rank of symmetric product states ψ ⊗m more generally;as a consequence we obtain a strong simulation algorithm for circuits consisting of Clifford gates and m instances of any (fixed) single-qubit Z-rotation gate with runtime poly(n,m)2m/2. We suggest a method to further improve the upper bounds by constructing linear codes with certain properties. © 2021, CC BY.

关键词： Inverse problems

Mutually Unbiased Measurements, Hadamard Matrices, and Superdense Coding

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Farkas, Máté Kaniewski, Jędrzej Nayak, Ashwin ICFO-Institut de Ciencies Fotoniques The Barcelona Institute of Science and Technology Castelldefels08860 Spain Faculty of Physics University of Warsaw Pasteura 5 Warsaw02-093 Poland Department of Combinatorics and Optimization Institute for Quantum Computing University of Waterloo 200 University Ave. W. WaterlooONN2L 3G1 Canada

Mutually unbiased bases (MUBs) are highly symmetric bases on complex Hilbert spaces, and the corresponding rank-1 projective measurements are ubiquitous in quantum information theory. In this work, we study a recently introduced generalisation of MUBs called mutually unbiased measurements (MUMs). These measurements inherit the essential property of complementarity from MUBs, but the Hilbert space dimension is no longer required to match the number of outcomes. This operational complementarity property renders MUMs highly useful for device-independent quantum information processing. It has been shown that MUMs are strictly more general than MUBs. In this work we provide a complete proof of the characterisation of MUMs that are direct sums of MUBs. We then construct new examples of MUMs that are not direct sums of MUBs. A crucial technical tool for this construction is a correspondence with quaternionic Hadamard matrices, which allows us to map known examples of such matrices to MUMs that are not direct sums of MUBs. Furthermore, we show that—in stark contrast with MUBs—the number of MUMs for a fixed outcome number is unbounded. Next, we focus on the use of MUMs in quantum communication. We demonstrate how any pair of MUMs with d outcomes defines a d-dimensional superdense coding protocol. Using MUMs that are not direct sums of MUBs, we disprove a recent conjecture due to Nayak and Yuen on the rigidity of superdense coding, for infinitely many dimensions. The superdense coding protocols arising in the refutation reveal how shared entanglement may be used in a manner heretofore unknown. © 2022, CC BY.

关键词： Hilbert spaces