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

Classical algorithms for quantum mean values

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Bravyi, Sergey Gosset, David Movassagh, Ramis IBM Research Yorktown HeightsNY10598 United States Institute for Quantum Computing University of Waterloo Canada Department of Combinatorics and Optimization University of Waterloo Canada IBM Research CambridgeMA02142 United States

We consider the task of estimating the expectation value of ann-qubit tensor product observableO1⊗O2⊗⋯⊗Onin the output state of a shallow quantum circuit. This task is a cornerstone of variational quantum algorithms for optimization, machine learning, and the simulation of quantum many-body systems. Here we study its computational complexity for constant-depth quantum circuits and three types of single-qubit observablesOjwhich are (a) close to the identity, (b) positive semidefinite, (c) arbitrary. It is shown that the mean value problem admits a classical approximation algorithm with runtime scaling aspoly(n)and2O~(n√)in cases (a,b) respectively. In case (c) we give a linear-time algorithm for geometrically local circuits on a two-dimensional grid. The mean value is approximated with a small relative error in case (a), while in cases (b,c) we satisfy a less demanding additive error bound. The algorithms are based on (respectively) Barvinok's polynomial interpolation method, a polynomial approximation for the OR function arising from quantum query complexity, and a Monte Carlo method combined with Matrix Product State techniques. We also prove a technical lemma characterizing a zero-free region for certain polynomials associated with a quantum circuit, which may be of independent interest. Copyright © 2019, The Authors. All rights reserved.

关键词： Approximation algorithms

ARKHIPOV'S THEOREM, GRAPH MINORS, AND LINEAR SYSTEM NONLOCAL GAMES

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Paddock, Connor Russo, Vincent Silverthorne, Turner Slofstra, William Institute for Quantum Computing University of Waterloo Canada Department of Combinatorics & Optimization University of Waterloo Canada Department of Pure Mathematics University of Waterloo Canada Department of Mathematics University of Toronto Canada Modellicity Inc. Canada Unitary Fund Canada

The perfect quantum strategies of a linear system game correspond to certain representations of its solution group. We study the solution groups of graph incidence games, which are linear system games in which the underlying linear system is the incidence system of a (non-properly) two-coloured graph. While it is undecidable to determine whether a general linear system game has a perfect quantum strategy, for graph incidence games this problem is solved by Arkhipov's theorem, which states that the graph incidence game of a connected graph has a perfect quantum strategy if and only if it either has a perfect classical strategy, or the graph is nonplanar. Arkhipov's criterion can be rephrased as a forbidden minor condition on connected two-coloured graphs. We extend Arkhipov's theorem by showing that, for graph incidence games of connected two-coloured graphs, every quotient closed property of the solution group has a forbidden minor characterization. We rederive Arkhipov's theorem from the group theoretic point of view, and then find the forbidden minors for two new properties: finiteness and abelianness. Our methods are entirely combinatorial, and finding the forbidden minors for other quotient closed properties seems to be an interesting combinatorial problem. Copyright © 2022, The Authors. All rights reserved.

关键词： Linear systems

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

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

学校读者我要写书评

暂无评论

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

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

Corrigendum to “Coined quantum walks lift the cospectrality of graphs and trees” [Pattern Recognition 42 (9) (2009) 1988–2002]

学校读者我要写书评

暂无评论

Pattern Recognition 2015年第4期48卷 1574-1575页

作者： David Emms Simone Severini Richard C. Wilson Edwin R. Hancock Department of Computer Science University of York York YO10 5DD UK Institute for Quantum Computing Department of Combinatorics and Optimization University of Waterloo 2133 Davis Centre Waterloo Ontario Canada N2L 3G1

Easy and hard functions for the Boolean hidden shift problem 8

学校读者我要写书评

暂无评论

Easy and hard functions for the Boolean hidden shift problem

8th Conference on the Theory of quantum Computation, Communication and Cryptography, TQC 2013

作者： Childs, Andrew M. Kothari, Robin Ozols, Maris Roetteler, Martin Department of Combinatorics and Optimization Institute for Quantum Computing University of Waterloo 200 University Avenue West WaterlooONN2L 3G1 Canada David R. Cheriton School of Computer Science Institute for Quantum Computing University of Waterloo 200 University Avenue West WaterlooONN2L 3G1 Canada IBM TJ Watson Research Center 1101 Kitchawan Road Yorktown HeightsNY10598 United States NEC Laboratories America 4 Independence Way PrincetonNJ08540 United States

ISBN: (纸本)9783939897552

We study the quantum query complexity of the Boolean hidden shift problem. Given oracle access to f(x + s) for a known Boolean function f, the task is to determine the n-bit string s. The quantum query complexity of this problem depends strongly on f. We demonstrate that the easiest instances of this problem correspond to bent functions, in the sense that an exact onequery algorithm exists if and only if the function is bent. We partially characterize the hardest instances, which include delta functions. Moreover, we show that the problem is easy for random functions, since two queries suffice. Our algorithm for random functions is based on performing the pretty good measurement on several copies of a certain state;its analysis relies on the Fourier transform. We also use this approach to improve the quantum rejection sampling approach to the Boolean hidden shift problem. © Andrew M. Childs, Robin Kothari, Maris Ozols, and Martin Roetteler.

关键词： Boolean functions

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

Reducing the CNOT count for Clifford+T circuits on NISQ architectures

学校读者我要写书评

暂无评论

TechRxiv

TechRxiv 2022年

作者： Mukhopadhyay, Priyanka Gheorghiu, Vlad Huang, Jiaxin Li, Sarah Meng Mosca, Michele Institute for Quantum Computing University of Waterloo WaterlooON Canada Department of Combinatorics and Optimization University of Waterloo WaterlooON Canada Perimeter Institute for Theoretical Physics WaterlooON Canada SoftwareQ Inc. KitchenerON Canada Faculty of Mathematics University of Waterloo Canada

While mapping a quantum circuit to the physical layer one has to consider the numerous constraints imposed by the underlying hardware architecture. Connectivity of the physical qubits is one such constraint that restricts two-qubit operations, such as CNOT, to "connected" qubits. SWAP gates can be used to place the logical qubits on admissible physical qubits, but they entail a significant increase in CNOT-count. In this paper we consider the problem of reducing the CNOT-count in Clifford+T circuits on connectivity constrained architectures, like noisy intermediate-scale quantum (NISQ) computing devices. We "slice" the circuit at the position of Hadamard gates and "build" the intermediate {CNOT, T} sub-circuits using Steiner trees, significantly improving on previous methods. We compared the performance of our algorithms while mapping different benchmark and random circuits to some well-known architectures such as 9-qubit square grid, 16-qubit square grid, Rigetti 16-qubit Aspen, 16-qubit IBM QX5 and 20-qubit IBM Tokyo. Our methods give less CNOT-count compared to Qiskit transpiler as well as using SWAP gates. Assuming most of the errors in a NISQ circuit implementation are due to CNOT errors, then our method would allow circuits with few times more CNOT gates be reliably implemented than the previous methods would permit. © 2022, CC BY-NC-SA.

关键词： Qubits

Theory of quantum computation, communication, and cryptography: Preface

学校读者我要写书评

暂无评论

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 2009年 5906 LNCS卷

作者： Childs, Andrew Mosca, Michele Institute for Quantum Computing Department of Combinatorics and Optimization University of Waterloo Waterloo ON N2L 3G1 Canada Perimeter Institute for Theoretical Physics 31 Caroline Street North Waterloo ON N2L 2Y5 Canada