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

arXiv 2021年

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

Many quantum algorithms can be written as a composition of unitaries, some of which can be exactly synthesized by a universal fault-tolerant gate set like Clifford+T, while others can be approximately synthesized. One task of a quantum compiler is to synthesize each approximately synthesizable unitary up to some approximation error, such that the error of the overall unitary remains bounded by a certain amount. In this paper we consider the case when the errors are measured in the global phase invariant distance. Apart from deriving a relation between this distance and the Frobenius norm, we show that this distance composes. If a unitary is written as a composition (product and tensor product) of other unitaries, we derive bounds on the error of the overall unitary as a function of the errors of the composed unitaries. Our bound is better than the sum-of-error bound, derived by Bernstein- Vazirani(1997), for the operator norm. This builds the intuition that working with the global phase invariant distance might give us a lower resource count while synthesizing quantum circuits. Next we consider the following problem. Suppose we are given a decomposition of a unitary, that is, the unitary is expressed as a composition of other unitaries. We want to distribute the errors in each component such that the resource-count (specifically T-count) is optimized. We consider the specific case when the unitary can be decomposed such that the Rz(θ) gates are the only approximately synthesizable component. We prove analytically that for both the operator norm and global phase invariant distance, the error should be distributed equally among these components (given some approximations). The optimal number of T-gates obtained by using the global phase invariant distance is less than what is obtained using the operator norm. Furthermore, we show that in case of approximate quantum Fourier Transform, the error obtained by pruning rotation gates is less when measured in this distance,

关键词： Errors

来源：评论

学校读者我要写书评

暂无评论

Any AND-OR formula of size N can be evaluated in time N1/2+o(1) on a quantum computer

Any AND-OR formula of size N can be evaluated in time N1/2+o...

引用

48th Annual Symposium on Foundations of Computer Science, FOCS 2007

作者： Ambainis, Andris Childs, Andrew M. Reichardt, Ben W. Špalek, Robert Zhang, Shengyu Department of Computer Science University of Latvia Department of Combinatorics and Optimization Institute for Quantum Computing University of Waterloo Institute for Quantum Information California Institute of Technology NSF Grant PHY-0456720 and ARO Grant W911NF-05-1-0294 United States University of California Berkeley United States

ISBN: (纸本)0769530109

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(√N) 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. © 2007 IEEE.

关键词： quantum computers

来源：评论

学校读者我要写书评

暂无评论

Perturbation theory in a pure-exchange nonequilibrium economy

引用

Physical Review E 2010年第3期81卷 036102-036102页

作者： Samuel E. Vázquez Simone Severini Institute for Quantum Computing and Department of Combinatorics & Optimization University of Waterloo Waterloo Ontario Canada N2L 3G1

We develop a formalism to study linearized perturbations around the equilibria of a pure-exchange economy. With the use of mean-field theory techniques, we derive equations for the flow of products in an economy driven by heterogeneous preferences and probabilistic interaction between agents. We are able to show that if the economic agents have static preferences, which are also homogeneous in any of the steady states, the final wealth distribution is independent of the dynamics of the nonequilibrium theory. In particular, it is completely determined in terms of the initial conditions and it is independent of the probability, and the network of interaction between agents. We show that the main effect of the network is to determine the relaxation time via the usual eigenvalue gap as in random walks on graphs.

关键词： Mean field theory

来源：评论

学校读者我要写书评

暂无评论

quantum networks on cubelike graphs

引用

Physical Review A 2008年第5期78卷 052320-052320页

作者： Anna Bernasconi Chris Godsil Simone Severini Institute for Quantum Computing and Department of Combinatorics and Optimization University of Waterloo Waterloo Ontario N2L 3G1 Canada

Cubelike graphs are the Cayley graphs of the elementary Abelian group Z2n (e.g., the hypercube is a cubelike graph). We study perfect state transfer between two particles in quantum networks modeled by a large class of cubelike graphs. This generalizes the results of Christandl et al. [Phys. Rev. Lett. 92, 187902 (2004)] and Facer et al. [Phys. Rev. A 92, 187902 (2008)].

关键词： Graphic methods

来源：评论

学校读者我要写书评

暂无评论

quantum query complexity of minor-closed graph properties

Quantum query complexity of minor-closed graph properties

引用

作者： Childs, Andrew M. Kothari, Robin Department of Combinatorics and Optimization and Institute for Quantum Computing University of Waterloo Waterloo ON N2L 3G1 Canada David R. Cheriton School of Computer Science and Institute for Quantum Computing University of Waterloo Waterloo ON N2L 3G1 Canada

We study the quantum query complexity of m inor-closed graph properties, which include such problems as determining whether an n-vertex graph is planar, is a forest, or does not contain a path of a given length. We show that most minor-closed properties-those that cannot be characterized by a finite set of forbidden subgraphs-have quantum query complexity Θ(n3/2). To establish this, we prove an adversary lower bound using a detailed analysis of the structure of minor-closed properties with respect to forbidden topological minors and forbidden subgraphs. On the other hand, we show that minor-closed properties (and more generally, sparse graph properties) that can be characterized by finitely many forbidden subgraphs can be solved strictly faster, in o(n3/2) queries. Our algorithms are a novel application of the quantum walk search framework and give improved upper bounds for several subgraph-finding problems. © 2012 Societ y for Industrial and Applied Mathematics.

关键词： Graph theory

来源：评论

学校读者我要写书评

暂无评论

quantum Complexity of the Kronecker Coefficients

引用

PRX quantum 2024年第1期5卷 010329-010329页

作者： Sergey Bravyi Anirban Chowdhury David Gosset Vojtěch Havlíček Guanyu Zhu IBM Quantum IBM T.J. Watson Research Center Department of Combinatorics and Optimization University of Waterloo Institute for Quantum Computing University of Waterloo Perimeter Institute for Theoretical Physics Waterloo

Whether or not the Kronecker coefficients of the symmetric group count some set of combinatorial objects is a longstanding open question. In this work we show that a given Kronecker coefficient is proportional to the rank of a projector that can be measured efficiently using a quantum computer. In other words a Kronecker coefficient counts the dimension of the vector space spanned by the accepting witnesses of a QMA verifier, where QMA is the quantum analogue of NP. This implies that approximating the Kronecker coefficients to within a given relative error is not harder than a certain natural class of quantum approximate counting problems that captures the complexity of estimating thermal properties of quantum many-body systems. A second consequence is that deciding positivity of Kronecker coefficients is contained in QMA, complementing a recent NP-hardness result of Ikenmeyer, Mulmuley, and Walter. We obtain similar results for the related problem of approximating row sums of the character table of the symmetric group. Finally, we discuss an efficient quantum algorithm that approximates normalized Kronecker coefficients to inverse-polynomial additive error.

关键词： quantum algorithms & computation quantum computation quantum information theory Computational complexity

来源：评论

学校读者我要写书评

暂无评论

quantum algorithms for algebraic problems

引用

Reviews of Modern Physics 2010年第1期82卷 1-1页

作者： Andrew M. Childs Wim van Dam []Department of Combinatorics and Optimization and Institute for Quantum Computing University of Waterloo Waterloo Ontario Canada N2L 3G1

quantum computers can execute algorithms that dramatically outperform classical computation. As the best-known example, Shor discovered an efficient quantum algorithm for factoring integers, whereas factoring appears to be difficult for classical computers. Understanding what other computational problems can be solved significantly faster using quantum algorithms is one of the major challenges in the theory of quantum computation, and such algorithms motivate the formidable task of building a large-scale quantum computer. This article reviews the current state of quantum algorithms, focusing on algorithms with superpolynomial speedup over classical computation and, in particular, on problems with an algebraic flavor.

关键词： quantum computers ALGORITHMS INTEGER programming quantum theory ALGEBRA

来源：评论

学校读者我要写书评

暂无评论

Practical quantum appointment scheduling

arXiv

引用

arXiv 2018年

作者： Touchette, Dave Lovitz, Benjamin Lütkenhaus, Norbert Institute for Quantum Computing Department of Combinatorics and Optimization University of Waterloo Perimeter Institute for Theoretical Physics Institute for Quantum Computing Department of Physics and Astronomy University of Waterloo

We propose a protocol based on coherent states and linear optics operations for solving the appointmentscheduling problem. Our main protocol leaks strictly less information about each party's input than the optimal classical protocol, even when considering experimental errors. Along with the ability to generate constant-amplitude coherent states over two modes, this protocol requires the ability to transfer these modes back-and-forth between the two parties multiple times with low coupling loss. The implementation requirements are thus still challenging. Along the way, we develop new tools to study quantum information cost of interactive protocols in the finite regime. Copyright © 2018, The Authors. All rights reserved.

关键词： Scheduling

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

A note on observables for counting trails and paths in graphs

引用

Journal of Mathematical Modelling and Algorithms 2009年第3期8卷 335-342页

作者： Markopoulou, Fotini Severini, Simone Perimeter Institute for Theoretical Physics Waterloo N2L 2Y5 ON Canada Institute for Quantum Computing and Department of Combinatorics and Optimization University of Waterloo Waterloo N2L 3G1 ON 200 University Avenue West Canada

We point out that the total number of trails and the total number of paths of given length, between two vertices of a simple undirected graph, are obtained as expectation values of specifically engineered quantum mechanical observables. Such observables are contextual with some background independent theories of gravity and emergent geometry. Thus, we point out yet another situation in which the mathematical formalism of a physical theory has some computational aspects involving intractable problems. © Springer Science + Business Media B.V. 2009.

关键词： Cycles Enumeration Graphity models Grassman variables Observables Paths

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：