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

Any AND-OR Formula of Size N can be Evaluated in time N^{1/2 + o(1)} on a quantum Computer

学校读者我要写书评

暂无评论

Any AND-OR Formula of Size N can be Evaluated in time N^{1/2...

Annual IEEE Symposium on Foundations of Computer Science

作者： Andris Ambainis Andrew M. Childs Ben W. Reichardt Robert Spalek Shengyu Zhang Department of Computer Science University of Latvia Department of Combinatorics & Optimization Institute for Quantum Computing University of Waterloo Institute for Quantum Information California Institute of Technology University of California Berkeley

For any AND-OR formula of size N, there exists a bounded-error N 1/2+o(1) -time quantum algorithm, based on a discrete-time quantum walk, that evaluates this formula on a black-box input. Balanced, or "approximately balanced," formulas can be evaluated in O(radicN) queries, which is optimal. It follows that the (2-o(1))th power of the quantum query complexity is a lower bound on the formula size, almost solving in the positive an open problem posed by Laplante, Lee and Szegedy.

关键词： quantum computing Computer science Spectral analysis Combinatorial mathematics History Databases Algorithms

Universal Computation by quantum Walk

学校读者我要写书评

暂无评论

Physical Review Letters 2009年第18期102卷 180501-180501页

作者： Andrew M. Childs Department of Combinatorics and Optimization and Institute for Quantum Computing University of Waterloo 200 University Avenue West Waterloo Ontario Canada N2L 3G1

In some of the earliest work on quantum computing, Feynman showed how to implement universal quantum computation with a time-independent Hamiltonian. I show that this remains possible even if the Hamiltonian is restricted to be the adjacency matrix of a low-degree graph. Thus quantum walk can be regarded as a universal computational primitive, with any quantum computation encoded in some graph. The main idea is to implement quantum gates by scattering processes.

关键词： quantum computers

When the asymptotic limit offers no advantage in the local-operations-and-classical-communication paradigm

学校读者我要写书评

暂无评论

Physical Review A 2014年第5期89卷 052310-052310页

作者： Honghao Fu Debbie Leung Laura Mančinska Institute for Quantum Computing and Department of Combinatorics and Optimization University of Waterloo Waterloo Ontario N2L 3G1 Canada Centre for Quantum Technologies National University of Singapore Singapore 119077

We consider bipartite LOCC, the class of operations implementable by local quantum operations and classical communication between two parties. Surprisingly, there are operations that can be approximated to arbitrary precision but are impossible to implement exactly if only a finite number of messages are exchanged. This significantly complicates the analysis of what can or cannot be approximated with LOCC. Toward alleviating this problem, we exhibit two scenarios in which allowing vanishing error does not help. The first scenario is implementation of projective measurements with product measurement operators. The second scenario is the discrimination of unextendable product bases on two three-dimensional systems.

关键词： quantum communication quantum operators quantum systems quantum states quantum gates quantum information theory

Additive entanglemement measures cannot be more than asymptotically continuous

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Coladangelo, Andrea Leung, Debbie Computing and Mathematical Sciences Caltech PasadenaCA United States Institute for Quantum Computing Department of Combinatorics and Optimization University of Waterloo Perimeter Institute WaterlooON Canada

In this short note, we show that any non-constant quantity defined on density matrices that is additive on tensor products and invariant under permutations cannot be "more than asymptotically continuous". The proof can be adapted to show that any additive entanglement measure (on any number of parties) that is invariant under local unitary operations also cannot be more than asymptotically continuous. The proof is a direct consequence of generalizing a protocol in [1] for embezzling entanglement. Copyright © 2019, The Authors. All rights reserved.

关键词： Additives

Capacity approaching coding for low noise interactive quantum communication part I: Large alphabets

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Leung, Debbie Nayak, Ashwin Shayeghi, Ala Touchette, Dave Yao, Penghui Yu, Nengkun Department of Combinatorics and Optimization Institute for Quantum Computing University of Waterloo and Perimeter Institute Department of Combinatorics and Optimization Institute for Quantum Computing University of Waterloo Department of Computer Science Institut Quantique Université de Sherbrooke Institute for Quantum Computing University of Waterloo Perimeter Institute State Key Laboratory for Novel Software Technology Nanjing University Centre for Quantum Software and Information Faculty of Engineering and Information Technology University of Technology Sydney

We consider the problem of implementing two-party interactive quantum communication over noisy channels, a necessary endeavor if we wish to fully reap quantum advantages for communication. For an arbitrary protocol with n messages, designed for a noiseless qudit channel over a poly (n) size alphabet, our main result is a simulation method that fails with probability less than 2-θ(n∈) and uses a qudit channel over the same alphabet n(1 + θ(√∈)) times, of which an ∈ fraction can be corrupted adversarially. The simulation is thus capacity achieving to leading order, and we conjecture that it is optimal up to a constant factor in the √ ∈ term. Furthermore, the simulation is in a model that does not require pre-shared resources such as randomness or entanglement between the communicating parties. Our work improves over the best previously known quantum result where the overhead is a non-explicit large constant [Brassard et al., FOCS'14] for low ∈. Copyright © 2020, The Authors. All rights reserved.

关键词： quantum communication

AN OPERATOR-ALGEBRAIC FORMULATION OF SELF-TESTING

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Paddock, Connor Slofstra, William Zhao, Yuming Zhou, Yangchen Institute for Quantum Computing University of Waterloo Canada Department of Combinatorics & Optimization University of Waterloo Canada Department of Pure Mathematics University of Waterloo Canada

We give a new definition of self-testing for correlations in terms of states on C∗-algebras. We show that this definition is equivalent to the standard definition for any class of finite-dimensional quantum models which is closed, provided that the correlation is extremal and has a full-rank model in the class. This last condition automatically holds for the class of POVM quantum models, but does not necessarily hold for the class of projective models by a result of Baptista, Chen, Kaniewski, Lolck, Mančinska, Gabelgaard Nielsen, and Schmidt. For extremal binary correlations and for extremal synchronous correlations, we show that any self-test for projective models is a self-test for POVM models. The question of whether there is a self-test for projective models which is not a self-test for POVM models remains open. An advantage of our new definition is that it extends naturally to commuting operator models. We show that an extremal correlation is a self-test for finite-dimensional quantum models if and only if it is a self-test for finite-dimensional commuting operator models, and also observe that many known finite-dimensional self-tests are in fact self-tests for infinite-dimensional commuting operator models. Copyright © 2023, The Authors. All rights reserved.

关键词： Algebra

A polynomial time and space heuristic algorithm for T-count

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Mosca, Michele Mukhopadhyay, Priyanka Institute for Quantum Computing University of Waterloo Canada Department of Combinatorics and Optimization University of Waterloo Canada Perimeter Institute for Theoretical Physics Waterloo Canada

An important part of reaping computational advantage from a quantum computer is to reduce the quantum resources needed to implement a desired quantum algorithm. quantum algorithms that are too large to be practical on noisy intermediate scale quantum (NISQ) devices will require fault-tolerant error correction. This work focuses on reducing the physical cost of implementing quantum algorithms when using the state-of-the-art fault-tolerant quantum error correcting codes, in particular, those for which implementing the T gate consumes vastly more resources than the other gates in the gate set. More specifically, in this paper we consider the group of unitaries that can be exactly implemented by a quantum circuit consisting of the Clifford+T gate set. The Clifford+T gate set is a universal gate set and in this group, using state-of-the-art surface codes, the T gate is by far the most expensive component to implement fault-tolerantly. So it is important to minimize the number of T gates necessary for a fault-tolerant implementation. Our primary interest is to compute a circuit for a given n-qubit unitary U, using the minimum possible number of T gates (called the T-count of unitary U). We consider the problem COUNT-T, the optimization version of which aims to find the T-count of U. In its decision version the goal is to decide if the T-count is at most some positive integer m. Given an oracle for COUNT-T, we can compute a T-count-optimal circuit in time polynomial in the T-count and dimension of U. We give a provable classical algorithm that solves COUNT-T (decision) in time O (Equation presented), where N = 2n and c ≥ 2. This gives a space-time trade-off for solving this problem with variants of meet-in-the-middle techniques. We also introduce an asymptotically faster multiplication method that shaves a factor of N0.7457 off of the overall complexity. Lastly, beyond our improvements to the rigorous algorithm, we give a heuristic algorithm that outputs a T-count-optimal

关键词： Heuristic algorithms

The flow of information in interactive quantum protocols : the cost of forgetting

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Laurière, Mathieu Touchette, Dave NYU-ECNU Institute of Mathematical Sciences at Nyu Shanghai Department of Combinatorics and Optimization Institute for Quantum Computing University of Waterloo Perimeter Institute for Theoretical Physics

In the context of two-party interactive quantum communication protocols, we study a recently defined notion of quantum information cost (QIC), which possesses most of the important properties of its classical analogue, see Ref. [Tou15]. Notably, its link with amortized quantum communication complexity has been used in Ref. [BGKK+15] to prove an (almost) tight lower bound on the bounded round quantum complexity of Disjointness. However, the only known characterization of QIC was through a notion of purification of the input state. Although this definition has the advantage to be valid for fully quantum inputs and tasks, its interpretation for classical tasks remained rather obscure. Also, the link between this new notion and other notions of information cost for quantum protocols that had previously appeared in the literature (e.g. in Refs. [JRS03, JN14, KLLGR15]) was not clear, if existent at all. We settle both these issues: For quantum communication with classical inputs, we provide an alternate characterization of QIC in terms of information about the input registers, avoiding any reference to the notion of a purification of the classical input state. We provide an exact operational interpretation of this alternative characterization as the sum of the cost of transmitting information about the classical inputs and the cost of forgetting information about these inputs. To obtain this characterization, we prove a general lemma, the Information Flow Lemma, assessing exactly the transfer of information in general interactive quantum processes. Specializing this lemma to interactive quantum protocols accomplishing classical tasks, we are also able to demystify the link between QIC and these other previous notions of information cost in quantum protocols. Furthermore, we clarify the link between QIC and IC of classical protocols by simulating quantumly classical protocols. Finally, we apply these concepts to argue that any quantum protocol that does not forget informat

关键词： Purification

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