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

On the CNOT-complexity of CNOT-phase circuits

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Amy, Matthew Azimzadeh, Parsiad Mosca, Michele Institute for Quantum Computing University of Waterloo Canada David R. Cheriton School of Computer Science University of Waterloo Canada Department of Combinatorics & Optimization University of Waterloo Canada Perimeter Institute for Theoretical Physics Waterloo Canada Canadian Institute for Advanced Research Toronto Canada

We study the problem of CNOT-optimal quantum circuit synthesis over gate sets consisting of CNOT and Z-basis rotations of arbitrary angles. We show that the circuit-polynomial correspondence relates such circuits to Fourier expansions of pseudo-Boolean functions, and that for certain classes of functions this expansion uniquely determines the minimum CNOT cost of an implementation. As a corollary we prove that CNOT minimization over CNOT and phase gates is at least as hard as synthesizing a CNOT-optimal circuit computing a set of parities of its inputs. We then show that this problem is NP-complete for two restricted cases where all CNOT gates are required to have the same target, and where the circuit inputs are encoded in a larger state space. The latter case has applications to CNOT optimization over more general Clifford+T circuits. We further present an efficient heuristic algorithm for synthesizing circuits over CNOT and Z-basis rotations with small CNOT cost. Our experiments show a 23% reduction of CNOT gates on average across a suite of Clifford+T benchmark circuits, with a maximum reduction of 43%. Copyright © 2017, The Authors. All rights reserved.

关键词： Timing circuits

Spectral properties of tensor products of channels

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Jaques, Sam Rahaman, Mizanur Department of Combinatorics and Optimization University of Waterloo WaterlooONN2L 3G1 Canada Department of Pure Mathematics Institute for Quantum Computing University of Waterloo WaterlooONN2L 3G1 Canada

We investigate spectral properties of the tensor products of two completely positive and trace preserving linear maps (also known as quantum channels) acting on matrix algebras. This leads to an important question of when an arbitrary subalgebra can split into the tensor product of two subalgebras. We show that for two unital quantum channels the multiplicative domain of their tensor product splits into the tensor product of the individual multiplicative domains. Consequently, we fully describe the fixed points and peripheral eigen operators of the tensor product of channels. Through a structure theorem of maximal unital proper ∗-subalgebras (MUPSA) of a matrix algebra we provide a non-trivial upper bound of the recentlyintroduced multiplicative index of a unital channel. This bound gives a criteria on when a channel cannot be factored into a product of two different channels. We construct examples of channels which cannot be realized as a tensor product of two channels in any way. With these techniques and results, we found some applications in quantum information theory. Copyright © 2017, The Authors. All rights reserved.

关键词： quantum entanglement

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

Lower bound on expected communication cost of quantum Huffman coding 11

学校读者我要写书评

暂无评论

Lower bound on expected communication cost of quantum Huffma...

11th Conference on the Theory of quantum Computation, Communication and Cryptography, TQC 2016

作者： Anshu, Anurag Garg, Ankit Harrow, Aram W. Yao, Penghui Centre for Quantum Technologies National University of Singapore Singapore Microsoft Research New England United States Center for Theoretical Physics Massachusetts Institute of Technology United States Institute for Quantum Computing University of Waterloo Canada Department of Combinatorics and Optimization University of Waterloo Canada

ISBN: (纸本)9783959770194

Data compression is a fundamental problem in quantum and classical information theory. A typical version of the problem is that the sender Alice receives a (classical or quantum) state from some known ensemble and needs to transmit them to the receiver Bob with average error below some specified bound. We consider the case in which the message can have a variable length and the goal is to minimize its expected length. For classical messages this problem has a well-known solution given by Huffman coding. In this scheme, the expected length of the message is equal to the Shannon entropy of the source (with a constant additive factor) and the scheme succeeds with zero error. This is a single-shot result which implies the asymptotic result, viz. Shannon's source coding theorem, by encoding each state sequentially. For the quantum case, the asymptotic compression rate is given by the von-Neumann entropy. However, we show that there is no one-shot scheme which is able to match this rate, even if interactive communication is allowed. This is a relatively rare case in quantum information theory when the cost of a quantum task is significantly different than the classical analogue. Our result has implications for direct sum theorems in quantum communication complexity and one-shot formulations of quantum Reverse Shannon theorem. © Anurag Anshu, Ankit Garg, Aram Harrow, and Penghui Yao;licensed under Creative Commons License CC-BY.

关键词： quantum communication

Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields 16

学校读者我要写书评

暂无评论

Efficient quantum algorithms for computing class groups and ...

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete Algorithms

作者： Jean-Francois Biasse Fang Song Department of Mathematics and Statistics University of South Florida Department of Combinatorics & Optimization and Institute for Quantum Computing University of Waterloo

ISBN: (纸本)9781510819672

This paper gives polynomial time quantum algorithms for computing the ideal class group (CGP) under the Generalized Riemann Hypothesis and solving the principal ideal problem (PIP) in number fields of arbitrary degree. These are are fundamental problems in number theory and they are connected to many unproven conjectures in both analytic and algebraic number theory. Previously the best known algorithms by Hallgren [20] only allowed to solve these problems in quantum polynomial time for number fields of constant degree. In a recent breakthrough, Eisentrager et al. [11] showed how to compute the unit group in arbitrary fields, thus opening the way to the resolution of CGP and PIP in the general case. For example, Biasse and Song [3] pointed out how to directly apply this result to solve PIP in classes of cyclotomic fields of arbitrary degree. The methods we introduce in this paper run in quantum polynomial time in arbitrary classes of number fields. They can be applied to solve other problems in computational number theory as well including computing the ray class group and solving relative norm equations. They are also useful for ongoing cryptanalysis of cryptographic schemes based on ideal lattices [5, 10]. Our algorithms generalize the quantum algorithm for computing the (ordinary) unit group [11]. We first show that CGP and PIP reduce naturally to the computation of S-unit groups, which is another fundamental problem in number theory. Then we show an efficient quantum reduction from computing S-units to the continuous hidden subgroup problem introduced in [11]. This step is our main technical contribution, which involves careful analysis of the metrical properties of lattices to prove the correctness of the reduction. In addition, we show how to convert the output into an exact compact representation, which is convenient for further algebraic manipulations.

关键词： Number theory PIP gene Polynomial time Riemann hypothesis Number field Arbitrary algorithms Fields quanta Ideal crystal lattices

Comparison of memory thresholds for planar qudit geometries

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Marks, Jacob Jochym-O'Connor, Tomas Gheorghiu, Vlad Department of Physics Yale University New HavenCT06520 United States Institute for Quantum Computing University of Waterloo WaterlooONN2L 3G1 Canada Department of Physics and Astronomy University of Waterloo WaterlooONN2L 3G1 Canada Walter Burke Institute for Theoretical Physics Institute for Quantum Information and Matter California Institute of Technology PasadenaCA91125 United States Department of Combinatorics and Optimization University of Waterloo WaterlooONN2L 3G1 Canada

We introduce and analyze a new type of decoding algorithm called General Color Clustering (GCC), based on renormalization group methods, to be used in qudit color codes. The performance of this decoder is analyzed under a generalized bit flip error model, and is used to obtain the first memory threshold estimates for qudit 6-6-6 color codes. The proposed decoder is compared with similar decoding schemes for qudit surface codes as well as the current leading qubit decoders for both sets of codes. We find that, as with surface codes, clustering performs sub-optimally for qubit color codes, giving a threshold of 5.6% compared to the 8.0% obtained through surface projection decoding methods. However, the threshold rate increases by up to 112% for large qudit dimensions, plateauing around 11.9%. All the analysis is performed using QTop, a new open-source software for simulating and visualizing topological quantum error correcting codes. Copyright © 2017, The Authors. All rights reserved.

关键词： Color

New one shot quantum protocols with application to communication complexity

学校读者我要写书评

暂无评论

New one shot quantum protocols with application to communica...

作者： Anshu, Anurag Jain, Rahul Mukhopadhyay, Priyanka Shayeghi, Ala Yao, Penghui Centre for Quantum Technologies National University of Singapore Singapore117543 Singapore Centre for Quantum Technologies Department of Computer Science National University of Singapore Singapore117543 Singapore MajuLab CNRS-UNS-NUS-NTU International Joint Research Unit UMI 3654 Singapore Singapore Institute for Quantum Computing Combinatorics and Optimization Department University of Waterloo WaterlooONN2L 3G1 Canada Joint Center for Quantum Information and Computer Science University of Maryland College ParkMD20742-2420 United States

In this paper, we present the following quantum compression protocol ' P ' Let ρ ,σ be quantum states, such that mathrm S left ( ρ σ right ) stackrel mathrm def= mathrm Tr (ρ log ρ - ρ log σ ) , the relative entropy between ρ and σ , is finite. Alice gets to know the eigendecomposition of ρ . Bob gets to know the eigendecomposition of σ . Both Alice and Bob know mathrm S left ( ρ σ right ) and an error parameter varepsilon . Alice and Bob use shared entanglement and after communication of mathcal O(( mathrm S left ( ρ σ right )+1) 4 bits from Alice to Bob, Bob ends up with a quantum state tilde ρ , such that mathrm F(ρ , tilde ρ ) geq 1 - 5 varepsilon , where mathrm F(c) represents fidelity. This result can be considered as a non-commutative generalization of a result due to Braverman and Rao where they considered the special case when ρ and σ are classical probability distributions (or commute with each other) and use shared randomness instead of shared entanglement. We use P to obtain an alternate proof of a direct-sum result for entanglement assisted quantum one-way communication complexity for all relations, which was first shown by Jain et al.. We also present a variant of protocol P in which Bob has some side information about the state with Alice. We show that in such a case, the amount of communication can be further reduced, based on the side information that Bob has. Our second result provides a quantum analog of the widely used classical correlated-sampling protocol. For example, Holenstein used the classical correlated-sampling protocol in his proof of a parallel-repetition theorem for two-player one-round games. © 1963-2012 IEEE.

关键词： Probability distributions

Making existential-unforgeable signatures strongly unforgeable in the quantum random-oracle model 10

学校读者我要写书评

暂无评论

Making existential-unforgeable signatures strongly unforgeab...

10th Conference on the Theory of quantum Computation, Communication and Cryptography, TQC 2015

作者： Eaton, Edward Song, Fang Department of Combinatorics and Optimization University of Waterloo Waterloo Canada Institute for Quantum Computing University of Waterloo Waterloo Canada

ISBN: (纸本)9783939897965

Strongly unforgeable signature schemes provide a more stringent security guarantee than the standard existential unforgeability. It requires that not only forging a signature on a new message is hard, it is infeasible as well to produce a new signature on a message for which the adversary has seen valid signatures before. Strongly unforgeable signatures are useful both in practice and as a building block in many cryptographic constructions. This work investigates a generic transformation that compiles any existential-unforgeable scheme into a strongly unforgeable one, which was proposed by Teranishi et al. [30] and was proven in the classical random-oracle model. Our main contribution is showing that the transformation also works against quantum adversaries in the quantum random-oracle model. We develop proof techniques such as adaptively programming a quantum random-oracle in a new setting, which could be of independent interest. Applying the transformation to an existential-unforgeable signature scheme due to Cash et al. [10], which can be shown to be quantum-secure assuming certain lattice problems are hard for quantum computers, we get an efficient quantum-secure strongly unforgeable signature scheme in the quantum random-oracle model. © Edward Eaton and Fang Song.

关键词： quantum computers

The Bose-Hubbard model is QMA-Complete

学校读者我要写书评

暂无评论

Theory of computing 2015年 11卷 491-603页

作者： Childs, Andrew M. Gosset, David Webb, Zak Department of Combinatorics and Optimization and Institute for Quantum Computing University of Waterloo Canada Department of Physics and Astronomy and Institute for Quantum Computing University of Waterloo Canada

The Bose-Hubbard model is a system of interacting bosons that live on the vertices of a graph. The particles can move between adjacent vertices and experience a repulsive on-site interaction. The Hamiltonian is determined by a choice of graph that specifies the geometry in which the particles move and interact. We prove that approximating the ground energy of the Bose-Hubbard model on a graph at fixed particle number is QMAcomplete. In our QMA-hardness proof, we encode the history of an n-qubit computation in the subspace with at most one particle per site (i. e., hard-core bosons). This feature, along with the well-known mapping between hard-core bosons and spin systems, lets us prove a related result for a class of 2-local Hamiltonians defined by graphs that generalizes the XY model. By avoiding the use of perturbation theory in our analysis, we circumvent the need to multiply terms in the Hamiltonian by large coefficients. © 2015 Aleksandrs Belovs and Eric Blais.

关键词： Hamiltonians