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

Rate Reduction of Blind quantum Data Compression with Local Approximations Based on Unstable Structure of quantum States

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Kuroiwa, Kohdai Leung, Debbie Institute for Quantum Computing University of Waterloo ONN2L 3G1 Canada Department of Physics and Astronomy University of Waterloo Canada Department of Combinatorics and Optimization University of Waterloo Canada Perimeter Institute for Theoretical Physics ONN2L 2Y5 Canada

In this paper, we propose a new protocol for a data compression task, blind quantum data compression, with finite local approximations. The rate of blind data compression is susceptible to approximations even when the approximations are diminutive. This instability originates from the sensitivity of a structure of quantum states against approximations, which makes the analysis of blind compression in the presence of approximations intractable. In this paper, we constructed a protocol that takes advantage of the instability to reduce the compression rate substantially. Our protocol shows a significant reduction in rate for specific examples we examined. Moreover, we apply our methods to diagonal states, and propose two types of approximation methods in this special case. We perform numerical experiments and observe that one of these two approximation methods performs significantly better than the other. Thus, our analysis makes a first step toward general investigation of blind quantum data compression with the allowance of approximations towards further investigation of approximation-rate trade-off of blind quantum data compression. Copyright © 2022, The Authors. All rights reserved.

关键词： Numerical methods

Deterministic Algorithms for the Hidden Subgroup Problem

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Nayak, Ashwin Department of Combinatorics and Optimization Institute for Quantum Computing University of Waterloo 200 University Ave.W. WaterlooONN2L 3G1 Canada

We present deterministic algorithms for theHidden Subgroup Problem. The first algorithm, for abelian groups, achieves the same asymptotic worst-case query complexity as the optimal randomized algorithm, namely O(√n ), where n is the order of the group. The analogous algorithm for non-abelian groups comes within a √log n factor of the optimal randomized query complexity. The best known randomized algorithm for the Hidden Subgroup Problem has expected query complexity that is sensitive to the input, namely O(√n/m ), where m is the order of the hidden subgroup. In the first version of this article [10, Sec. 5], we asked if there is a deterministic algorithm whose query complexity has a similar dependence on the order of the hidden subgroup. Prompted by this question, Ye and Li [14] present deterministic algorithms for abelian groups which solve the problem with O(√n/m ) queries, and find the hidden subgroup with O(√n(logm)/m + logm) queries. Moreover, they exhibit instances which show that in general, the deterministic query complexity of the problem may be o(√n/m ), and that of finding the entire subgroup may also be o(√n/m ) or even ω(√n/m ). We present a different deterministic algorithm for the Hidden Subgroup Problem that also has query complexity O(√n/m ) for abelian groups. The algorithm is arguably simpler. Moreover, it works for non-abelian groups, and has query complexity O(√(n/m) log(n/m) ) for a large class of instances, such as those over supersolvable groups. We build on this to design deterministic algorithms to find the hidden subgroup for all abelian and some non-abelian instances, at the cost of a logm multiplicative factor increase in the query *** Codes 68Q25, 68Q12 (Primary) 20D99 (Secondary) © 2021, CC BY.

关键词： Group theory

Averaging gate approximation error and performance of Unitary Coupled Cluster ansatz in Pre-FTQC Era

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Kuroiwa, Kohdai Nakagawa, Yuya O. Institute for Quantum Computing University of Waterloo ONN2L 3G1 Canada Department of Combinatorics and Optimization University of Waterloo Canada Perimeter Institute for Theoretical Physics ONN2L 2Y5 Canada QunaSys Inc. Aqua Hakusan Building 9F 1-13-7 Hakusan Bunkyo Tokyo113-0001 Japan

Fault-tolerant quantum computation (FTQC) is essential to implement quantum algorithms in a noise-resilient way, and thus to enjoy advantages of quantum computers even with presence of noise. In FTQC, a quantum circuit is decomposed into universal gates that can be fault-tolerantly implemented, for example, Clifford+T gates. Here, T gate is usually regarded as an essential resource for quantum computation because its action cannot be simulated efficiently on classical computers and it is experimentally difficult to implement fault-tolerantly. Practically, it is highly likely that only a limited number of T gates are available in the near future. In this Pre-FTQC era, due to the constraint on available resources, it is vital to precisely estimate the decomposition error of a whole circuit. In this paper, we propose that the Clifford+T decomposition error for a given quantum circuit containing a large number of quantum gates can be modeled as the depolarizing noise by averaging the decomposition error for each quantum gate in the circuit, and our model provides more accurate error estimation than the naive estimation. We exemplify this by taking unitary coupled-cluster (UCC) ansatz used in the applications of quantum computers to quantum chemistry as an example. We theoretically evaluate the approximation error of UCC ansatz when decomposed into Clifford+T gates, and the numerical simulation for a wide variety of molecules verified that our model well explains the total decomposition error of the ansatz. Our results enable the precise and efficient usage of quantum resources in the early-stage applications of quantum computers and fuel further research towards what quantum computation can achieve in the upcoming future. © 2023, CC BY.

关键词： quantum computers

How to simulate quantum measurement without computing marginals

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Bravyi, Sergey Gosset, David Liu, Yinchen IBM Quantum IBM T.J. Watson Research Center United States Department of Combinatorics and Optimization University of Waterloo Canada Institute for Quantum Computing University of Waterloo Canada Perimeter Institute for Theoretical Physics Waterloo Canada

We describe and analyze algorithms for classically simulating measurement of an n-qubit quantum state ψ in the standard basis, that is, sampling a bit string x from the probability distribution |〈x|ψ〉|2. Our algorithms reduce the sampling task to computing poly(n) amplitudes of n-qubit states;unlike previously known techniques they do not require computation of marginal probabilities. First we consider the case where |ψ〉 = U|0n〉is the output state of an m-gate quantum circuit U. We propose an exact sampling algorithm which involves computing O(m) amplitudes of n-qubit states generated by subcircuits of U spanned by the first t = 1, 2,..., m gates. We show that our algorithm can significantly accelerate quantum circuit simulations based on tensor network contraction methods or low-rank stabilizer decompositions. As another striking consequence we obtain an efficient classical simulation algorithm for measurement-based quantum computation with the surface code resource state on any planar graph, generalizing a previous algorithm which was known to be efficient only under restrictive topological constraints on the ordering of single-qubit measurements. Second, we consider the case in which ψ is the unique ground state of a local Hamiltonian with a spectral gap that is lower bounded by an inverse polynomial function of n. We prove that a simple Metropolis-Hastings Markov Chain mixes rapidly to the desired probability distribution provided that ψ obeys a certain technical condition, which we show is satisfied for all sign-problem free Hamiltonians. This gives a sampling algorithm which involves computing poly(n) amplitudes of ψ. Copyright © 2021, The Authors. All rights reserved.

关键词： Probability distributions

An area law for 2D frustration-free spin systems

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Anshu, Anurag Arad, Itai Gosset, David School of Engineering and Applied Sciences Harvard University Cambridge United States Physics Department Technion Israel Institute for Quantum Computing University of Waterloo Canada Department of Combinatorics and Optimization University of Waterloo Canada

We prove that the entanglement entropy of the ground state of a locally gapped frustration-free 2D lattice spin system satisfies an area law with respect to a vertical bipartition of the lattice into left and right regions. We first establish that the ground state projector of any locally gapped frustration-free 1D spin system can be approximated to within error ϵ by a degree O(√n log(ϵ-1)) multivariate polynomial in the interaction terms of the Hamiltonian. This generalizes the optimal bound on the approximate degree of the boolean AND function, which corresponds to the special case of commuting Hamiltonian terms. For 2D spin systems we then construct an approximate ground state projector (AGSP) that employs the optimal 1D approximation in the vicinity of the boundary of the bipartition of interest. This AGSP has sufficiently low entanglement and error to establish the area law using a known technique. Copyright © 2021, The Authors. All rights reserved.

关键词： Ground state

Improved approximation algorithms for bounded-degree local Hamiltonians

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Anshu, Anurag Gosset, David Morenz Korol, Karen J. Soleimanifar, Mehdi Department of EECS Challenge Institute for Quantum Computation University of California Berkeley United States Simons Institute for the Theory of Computing BerkeleyCA United States Department of Combinatorics Optimization and Institute for Quantum Computing University of Waterloo Canada Department of Chemistry University of Toronto Canada Center for Theoretical Physics Massachusetts Institute of Technology United States

We consider the task of approximating the ground state energy of two-local quantum Hamiltonians on bounded-degree graphs. Most existing algorithms optimize the energy over the set of product states. Here we describe a family of shallow quantum circuits that can be used to improve the approximation ratio achieved by a given product state. The algorithm takes as input an n-qubit product state |vi with mean energy e0 = hv|H|vi and variance Var = hv|(H −e0)2|vi, and outputs a state with an energy that is lower than e0 by an amount proportional to Var2/n. In a typical case, we have Var = Ω(n) and the energy improvement is proportional to the number of edges in the graph. When applied to an initial random product state, we recover and generalize the performance guarantees of known algorithms for bounded-occurrence classical constraint satisfaction problems. We extend our results to k-local Hamiltonians and entangled initial states. Copyright © 2021, The Authors. All rights reserved.

关键词： Constraint satisfaction problems

Fast Estimation of Outcome Probabilities for quantum Circuits

学校读者我要写书评

暂无评论

PRX quantum 2022年第2期3卷 020361-020361页

作者： Hakop Pashayan Oliver Reardon-Smith Kamil Korzekwa Stephen D. Bartlett Institute for Quantum Computing and Department of Combinatorics and Optimization University of Waterloo Ontario N2L 3G1 Canada Perimeter Institute for Theoretical Physics Waterloo Ontario N2L 2Y5 Canada Faculty of Physics Astronomy and Applied Computer Science Jagiellonian University Kraków 30-348 Poland Centre for Engineered Quantum Systems School of Physics The University of Sydney Sydney New South Wales 2006 Australia

We present two classical algorithms for the simulation of universal quantum circuits on n qubits constructed from c instances of Clifford gates and t arbitrary-angle Z-rotation gates such as T gates. Our algorithms complement each other by performing best in different parameter regimes. The Estimate algorithm produces an additive precision estimate of the Born-rule probability of a chosen measurement outcome with the only source of run-time inefficiency being a linear dependence on the stabilizer extent (with scaling approximately equal to 1.17t for T gates). Our algorithm is state of the art for this task: as an example, in approximately 13 h (on a standard desktop computer), we estimate the Born-rule probability to within an additive error of 0.03, for a 50-qubit, 60 non-Clifford gate quantum circuit with more than 2000 Clifford gates. Our second algorithm, Compute, calculates the probability of a chosen measurement outcome to machine precision with run time O(2t−rt), where r is an efficiently computable, circuit-specific quantity. With high probability, r is very close to min{t,n−w} for random circuits with many Clifford gates, where w is the number of measured qubits. Compute can be effective in surprisingly challenging parameter regimes, e.g., we can randomly sample Clifford+T circuits with n=55, w=5, c=105, and t=80T gates, and then compute the Born-rule probability with a run time consistently less than 10 min using a single core of a standard desktop computer. We provide a C+Python implementation of our algorithms and benchmark them using random circuits, the hidden-shift algorithm, and the quantum approximate optimization algorithm.

关键词： quantum simulation

Fault-tolerant quantum error correction using error weight parities

学校读者我要写书评

暂无评论

Physical Review A 2021年第4期104卷 042410-042410页

作者： Theerapat Tansuwannont Debbie Leung Institute for Quantum Computing and Department of Physics and Astronomy University of Waterloo Waterloo Ontario N2L 3G1 Canada Institute for Quantum Computing and Department of Combinatorics and Optimization University of Waterloo Waterloo Ontario N2L 3G1 Canada Perimeter Institute for Theoretical Physics Waterloo Ontario N2L 2Y5 Canada

In quantum error correction using imperfect primitives, errors of high weight arising from a few faults are major concerns since they might not be correctable by the quantum error correcting code. Fortunately, some errors of different weights are logically equivalent, and the same correction procedure is applicable to all equivalent errors; thus correcting high-weight errors is sometimes possible. In this work, we introduce a technique called weight parity error correction (WPEC) which can correct Pauli error of any weight in some stabilizer codes provided that the parity of the weight of the error is known. We show that the technique is applicable to concatenated codes constructed from the [[7,1,3]] Steane code or the [[23,1,7]] Golay code. We also provide a fault-tolerant error correction protocol using WPEC for the [[49,1,9]] concatenated Steane code which can correct up to three faults and requires only two ancillas.

关键词： quantum error correction

Classical algorithms for forrelation

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Bravyi, Sergey Gosset, David Grier, Daniel Schaeffer, Luke IBM Quantum IBM T.J. Watson Research Center United States Institute for Quantum Computing University of Waterloo Canada Department of Combinatorics and Optimization University of Waterloo Canada Cheriton School of Computer Science University of Waterloo Canada

We study the forrelation problem: given a pair of n-bit Boolean functions f and g, estimate the correlation between f and the Fourier transform of g. This problem is known to provide the largest possible quantum speedup in terms of its query complexity and achieves the landmark oracle separation between the complexity class BQP and the Polynomial Hierarchy. Our first result is a classical algorithm for the forrelation problem which has runtime O(n2n/2). This is a nearly quadratic improvement over the best previously known algorithm. Secondly, we show that quantum query algorithm that makes t queries to an n-bit oracle can be simulated by classical query algorithm making only O(2n(1-1/2t)) queries. This fixes a gap in the literature arising from a recently discovered critical error in a previous proof;it matches recently established lower bounds (up to poly(n, t)) factors) and thus characterizes the maximal separation in query complexity between quantum and classical algorithms. Finally, we introduce a graph-based forrelation problem where n binary variables live at vertices of some fixed graph and the functions f, g are products of terms describing interactions between nearest-neighbor variables. We show that the graph-based forrelation problem can be solved on a classical computer in time O(n) for any bipartite graph, any planar graph, or, more generally, any graph which can be partitioned into two subgraphs of constant treewidth. The graph-based forrelation is simply related to the variational energy achieved by the quantum Approximate optimization Algorithm (QAOA) with two entangling layers and Ising-type cost functions. By exploiting the connection between QAOA and the graph-based forrelation we were able to simulate the recently proposed Recursive QAOA with two entangling layers and 225 qubits on a laptop computer. Copyright © 2021, The Authors. All rights reserved.

关键词： Graphic methods