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

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

No-go theorem for one-way quantum computing on naturally occurring two-level systems

学校读者我要写书评

暂无评论

Physical Review A 2011年第5期83卷 050301(R)-050301(R)页

作者： Jianxin Chen Xie Chen Runyao Duan Zhengfeng Ji Bei Zeng Department of Computer Science and Technology Tsinghua National Laboratory for Information Science and Technology Tsinghua University Beijing China Department of Physics Massachusetts Institute of Technology Cambridge Massachusetts USA Centre for Quantum Computation and Intelligent Systems (QCIS) Faculty of Engineering and Information Technology University of Technology Sydney New South Wales Australia Perimeter Institute for Theoretical Physics Waterloo Ontario Canada State Key Laboratory of Computer Science Institute of Software Chinese Academy of Sciences Beijing China Institute for Quantum Computing and Department of Combinatorics and Optimization University of Waterloo Waterloo Ontario Canada

The ground states of some many-body quantum systems can serve as resource states for the one-way quantum computing model, achieving the full power of quantum computation. Such resource states are found, for example, in spin-52 and spin-32 systems. It is, of course, desirable to have a natural resource state in a spin-12, that is, qubit system. Here, we give a negative answer to this question for frustration-free systems with two-body interactions. In fact, it is shown to be impossible for any genuinely entangled qubit state to be a nondegenerate ground state of any two-body frustration-free Hamiltonian. What is more, we also prove that every spin-12 frustration-free Hamiltonian with two-body interaction always has a ground state that is a product of single- or two-qubit states. In other words, there cannot be any interesting entanglement features in the ground state of such a qubit Hamiltonian.

关键词： quantum computers quantum theory HAMILTONIAN operator HAMILTONIAN systems PHYSICS

Pauli partitioning with respect to gate sets

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Jena, Andrew Genin, Scott Mosca, Michele Department of Combinatorics and Optimization University of Waterloo Institute for Quantum Computing University of Waterloo OTI Lumionics TorontoON Canada Department of Combinatorics and Optimization University of Waterloo WaterlooON Canada Institute for Quantum Computing University of Waterloo WaterlooON Canada Perimeter Institute for Theoretical Physics WaterlooON Canada

Measuring the expectation value of Pauli operators on prepared quantum states is a fundamental task in a multitude of quantum algorithms. Simultaneously measuring sets of operators allows for fewer measurements and an overall speedup of the measurement process. We investigate the task of partitioning a random subset of Pauli operators into simultaneously-measurable parts. Using heuristics from coloring random graphs, we give an upper bound for the expected number of parts in our partition. We go on to conjecture that allowing arbitrary Clifford operators before measurement, rather than single-qubit operations, leads to a decrease in the number of parts which is linear with respect to the lengths of the operators. We give evidence to confirm this conjecture and comment on the importance of this result for a specific near-term application: speeding up the measurement process of the variational quantum eigensolver. Copyright © 2019, The Authors. All rights reserved.

关键词： Qubits

Dynamic Qubit Routing with CNOT Circuit Synthesis for quantum Compilation

学校读者我要写书评

暂无评论

arXiv 2022年

作者： de Griend, Arianne Meijer-Van Li, Sarah Meng Department of Computer Science University of Helsinki Finland Department of Combinatorics & Optimization Institute for Quantum Computing University of Waterloo Canada

Many quantum computers have constraints regarding which two-qubit operations are locally allowed. To run a quantum circuit under those constraints, qubits need to be mapped to different quantum registers, and multi-qubit gates need to be routed accordingly. Recent developments have shown that compiling strategies based on Steiner tree provide a competitive tool to route CNOTs. However, these algorithms require the qubit map to be decided before routing. Moreover, the qubit map is fixed throughout the computation, i.e. the logical qubit will not be moved to a different physical qubit register. This is inefficient with respect to the CNOT count of the resulting circuit. In this paper, we propose the algorithm PermRowCol for routing CNOTs in a quantum circuit. It dynamically remaps logical qubits during the computation, and thus results in fewer output CNOTs than the algorithms Steiner-Gauss [14] and RowCol [27]. Here we focus on circuits over CNOT only, but this method could be generalized to a routing and mapping strategy on Clifford+T circuits by slicing the quantum circuit into subcircuits composed of CNOTs and single-qubit gates. Additionally, PermRowCol can be used in place of Steiner-Gauss in the synthesis of phase polynomials as well as the extraction of quantum circuits from ZX-diagrams. © 2022, CC BY.

关键词： Qubits

Qudit quantum Programming with Projective Cliffords

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Paykin, Jennifer Winnick, Sam Intel Labs Intel Corporation United States Institute for Quantum Computing Department of Combinatorics & Optimization University of Waterloo Canada

This paper introduces a novel abstraction for programming quantum operations, specifically projective Cliffords, as functions over the qudit Pauli group. We define a categorical semantics for projective Cliffords based on Pauli encodings in terms of Zd-linear maps. We then introduce a type system and lambda calculus for both Zd-linear maps and projective Cliffords, and prove that these type systems have a sound denotational semantics in terms of the relevant categories. Finally, we explore what it means to program with projective Cliffords through a number of examples and programming constructions. Copyright © 2024, The Authors. All rights reserved.

关键词： Semantics

Inverting a Permutation is as Hard as Unordered Search

学校读者我要写书评

暂无评论

Theory of computing 2011年 7卷 19-25页

作者： Nayak, Ashwin Department of Combinatorics and Optimization Institute for Quantum Computing University of Waterloo Canada Perimeter Institute for Theoretical Physics WaterlooON Canada

We show how an algorithm for the problem of inverting a permutation may be used to design one for the problem of unordered search (with a unique solution). Since there is a straightforward reduction in the reverse direction, the problems are essentially equivalent. The reduction we present helps us bypass the hybrid argument due to Bennett, Bernstein, Brassard, and Vazirani (1997) and the quantum adversary method due to Ambainis (2002) that were earlier used to derive lower bounds on the quantum query complexity of the problem of inverting permutations. It directly implies that the quantum query complexity of the problem is asymptotically the same as that for unordered search, namely in Θ(√n). © 2011, University of Chicago, department of Computer Science. All rights reserved.

关键词： Computational complexity

Condensed Encodings of Projective Clifford Operations in Arbitrary Dimension

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Winnick, Sam Paykin, Jennifer Institute for Quantum Computing Department of Combinatorics & Optimization University of Waterloo Canada Intel Labs Intel Corporation United States

We provide a careful analysis of the structure theorem for the n-qudit projective Clifford group and various encoding schemes for its elements. In particular, we derive formulas for evaluation, composition, and inversion. Our results apply to all integers d ≥ 2, most notably the even case. Copyright © 2024, The Authors. All rights reserved.

关键词： Encoding (symbols)

An exponential separation between the entanglement and communication capacities of a bipartite unitary interaction

学校读者我要写书评

暂无评论

An exponential separation between the entanglement and commu...

International Conference on quantum Information, ICQI 2008

作者： Harrow, Aram W. Leung, Debbie W. Department of Computer Science University of Bristol Bristol BS8 1UB United Kingdom Department of Combinatorics and Optimization Institute for Quantum Computing University of Waterloo Waterloo Ontario N2L 3G1 Canada

We consider asymptotic capacities of bipartite unitary gates. We present a gate with exponen- tially larger entanglement capacity than the total communication capacity. The key tool is a communication- efficient metho... 详细信息

关键词： quantum optics

Linear programming hierarchies suffice for directed steiner tree

学校读者我要写书评

暂无评论

17th International Conference on Integer Programming and Combinatorial optimization, IPCO 2014

作者： Friggstad, Zachary Könemann, Jochen Kun-Ko, Young Louis, Anand Shadravan, Mohammad Tulsiani, Madhur Department of Computing Science University of Alberta Canada Department of Combinatorics and Optimization University of Waterloo Canada Department of Computer Science Princeton University United States College of Computing Georgia Tech. United States Toyota Technical Institute at Chicago United States

ISBN: (纸本)9783319075563

We demonstrate that rounds of the Sherali-Adams hierarchy and 2 rounds of the Lovász-Schrijver hierarchy suffice to reduce the integrality gap of a natural LP relaxation for Directed Steiner Tree in -layered graphs from ω (√k) to O(·logk) where k is the number of terminals. This is an improvement over Rothvoss' result that 2 rounds of the considerably stronger Lasserre SDP hierarchy reduce the integrality gap of a similar formulation to O(·logk). We also observe that Directed Steiner Tree instances with 3 layers of edges have only an O(logk) integrality gap in the standard LP relaxation, complementing the known fact that the gap can be as large as ω (√k) in graphs with 4 layers. © 2014 Springer International Publishing Switzerland.

关键词： Linear programming