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

Faster Provable Sieving Algorithms for the Shortest Vector Problem and the Closest Vector Problem on Lattices in p Norm

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Mukhopadhyay, Priyanka Institute for Quantum Computing University of Waterloo WaterlooON Canada Dept. of Combinatorics and Optimization University of Waterloo WaterlooON Canada

In this work, we give provable sieving algorithms for the Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP) on lattices in lp norm (1 ≤ p ≤ ∞). The running time we obtain is better than existing provable sieving algorithms. We give a new linear sieving procedure that works for all p norm (1 ≤ p ≤ ∞). The main idea is to divide the space into hypercubes such that each vector can be mapped efficiently to a sub-region. We achieve a time complexity of 22.751n+o(n), which is much less than the 23.849n+o(n) complexity of the previous best algorithm. We also introduce a mixed sieving procedure, where a point is mapped to a hypercube within a ball and then a quadratic sieve is performed within each hypercube. This improves the running time, especially in the 2 norm, where we achieve a time complexity of 22.25n+o(n), while the List Sieve Birthday algorithm has a running time of 22.465n+o(n). We adopt our sieving techniques to approximation algorithms for SVP and CVP in lp norm (1 ≤ p ≤ ∞) and show that our algorithm has a running time of 22.001n+o(n), while previous algorithms have a time complexity of 23.169n+o(n) © 2019, CC BY-NC-ND.

关键词： Geometry

Universal Adiabatic quantum Computation via the Space-Time Circuit-to-Hamiltonian Construction

学校读者我要写书评

暂无评论

Physical Review Letters 2015年第14期114卷 140501-140501页

作者： David Gosset Barbara M. Terhal Anna Vershynina Institute for Quantum Computing and Dept. of Combinatorics and Optimization University of Waterloo Ontario N2L 3G1 Canada JARA Institute for Quantum Information RWTH Aachen University 52056 Aachen North Rhine-Westphalia Germany

We show how to perform universal adiabatic quantum computation using a Hamiltonian which describes a set of particles with local interactions on a two-dimensional grid. A single parameter in the Hamiltonian is adiabatically changed as a function of time to simulate the quantum circuit. We bound the eigenvalue gap above the unique ground state by mapping our model onto the ferromagnetic XXZ chain with kink boundary conditions; the gap of this spin chain was computed exactly by Koma and Nachtergaele using its q-deformed version of SU(2) symmetry. We also discuss a related time-independent Hamiltonian which was shown by Janzing to be capable of universal computation. We observe that in the limit of large system size, the time evolution is equivalent to the exactly solvable quantum walk on Young’s lattice.

关键词： HAMILTONIAN systems FERROMAGNETIC materials DYNAMICAL systems MAGNETIC materials quantum theory

A (quasi-)polynomial time heuristic algorithm for synthesizing T-dept. 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-dept. optimal quantum circuits over the Clifford+T gate set. First we construct a special subset of T-dept. 1 unitaries, such that it is possible to express the T-dept.-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 dept.-optimal and T-dept.-optimal circuits for exactly implementable unitaries. Specifically, for synthesizing T-dept.-optimal circuits, we get an algorithm with space and time complexity (Equation presented) and (Equation presented) respectively, where d is the minimum T-dept. 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-dept.-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

T-count and T-dept. 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-dept. of any multi-qubit unitary and the complexity has exponential dependence on n and ∈-T-dept.. This is the first algorithm that gives T-count or T-dept. of any multi-qubit (n ≥ 1) unitary. For small enough ∈, we can synthesize the T-count and T-dept.-optimal circuits. Our results can be used to determine the minimum count (or dept.) 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

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

Synthesis and Arithmetic of Single Qutrit Circuits

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Kalra, Amolak Ratan Mosca, Michele Valluri, Dinesh Institute for Quantum Computing University of Waterloo WaterlooON Canada David R. Cheriton School of Computer Science University of Waterloo WaterlooON Canada Perimeter Institute for Theoretical Physics WaterlooON Canada Dept. of Combinatorics & Optimization University of Waterloo WaterlooON Canada

In this paper we study single qutrit circuits consisting of words over the Clifford+D cyclotomic gate set, where D = diag(±ξa, ±ξb, ±ξc), ξ is a primitive 9-th root of unity and a, b, c are integers. We characterize classes of qutrit unit vectors z with entries in [ξ, χ1 ] based on the possibility of reducing their smallest denominator exponent (sde) with respect to χ := 1 − ξ, by acting an appropriate gate in Clifford+D. We do this by studying the notion of ‘derivatives mod 3’ of an arbitrary element of [ξ] and using it to study the smallest denominator exponent of HDz where H is the qutrit Hadamard gate and D ∈ D. In addition, we reduce the problem of finding all unit vectors of a given sde to that of finding integral solutions of a positive definite quadratic form along with some additional constraints. As a consequence we prove that the Clifford+D gates naturally arise as gates with sde 0 and 3 in the group U(3, [ξ, χ1 ]) of 3 × 3 unitaries with entries in [ξ, χ1 ]. We illustrate the general applicability of these methods to obtain an exact synthesis algorithm for Clifford+R and recover the previous exact synthesis algorithm in [14]. The framework developed to formulate qutrit gate synthesis for Clifford+D extends to qudits of arbitrary prime power. © 2023, CC BY.

关键词： Digital arithmetic

SICS and algebraic number theory

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Appleby, Marcus Flammia, Steven McConnell, Gary Yard, Jon Centre for Engineered Quantum Systems School of Physics University of Sydney Sydney Australia Center for Theoretical Physics Massachusetts Institute of Technology Cambridge United States Controlled Dynamics Theory Group Imperial College London United Kingdom Institute for Quantum Computing Dept. of Combinatorics and Optimization University of Waterloo Perimeter Institute for Theoretical Physics Waterloo Canada

We give an overview of some remarkable connections between symmetric informationally complete measurements (SIC-POVMs, or SICs) and algebraic number theory, in particular, a connection with Hilbert's 12th problem. The paper is meant to be intelligible to a physicist who has no prior knowledge of either Galois theory or algebraic number theory. Copyright © 2017, The Authors. All rights reserved.

关键词： Number theory

Multi-qutrit exact synthesis

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Kalra, Amolak Ratan Saikia, Manimugdha Valluri, Dinesh Winnick, Sam Yard, Jon Institute for Quantum Computing University of Waterloo WaterlooON Canada David R. Cheriton School of Computer Science University of Waterloo WaterlooON Canada Dept. of Combinatorics & Optimization University of Waterloo WaterlooON Canada Perimeter Institute for Theoretical Physics WaterlooON Canada Department of Mathematics University of Western Ontario LondonON Canada

We present an exact synthesis algorithm for qutrit unitaries in U3n([1/3, e2πi/3]) over the Clifford+T gate set with at most one ancilla. This extends the already known result of qutrit metaplectic gates being a subset of Clifford+T gate set with one ancilla. As an intermediary step, we construct an algorithm to convert 3-level unitaries into multiply-controlled gates, analogous to Gray codes converting 2-level unitaries into multiply-controlled gates. Finally, using catalytic embeddings, we present an algorithm to exactly synthesize unitaries U3n([1/3, e2πi/9]) over the Clifford+T gate set with at most 2 ancillas. This, in particular, gives an exact synthesis algorithm of single-qutrit Clifford+D over the multi-qutrit Clifford+T gate set with at most two ancillas. Copyright © 2024, The Authors. All rights reserved.

关键词：