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

quantum algorithms on Walsh transform and Hamming distance for Boolean functions

quantum INFORMATION PROCESSING 2018年第6期17卷 139-139页

作者： Xie, Zhengwei Qiu, Daowen Cai, Guangya Sun Yat Sen Univ Inst Comp Sci Theory Sch Data & Comp Sci Guangzhou 510006 Guangdong Peoples R China Sun Yat Sen Univ Guangdong Key Lab Informat Secur Technol Guangzhou 510006 Guangdong Peoples R China Jiangsu Univ Technol Sch Math & Phys Changzhou 213001 Peoples R China Inst Super Tecn Inst Telecomunicacoes Dept Matemat Ave Rovisco Pais P-1049001 Lisbon Portugal

Walsh spectrum or Walsh transform is an alternative description of Boolean functions. In this paper, we explore quantum algorithms to approximate the absolute value of Walsh transform W-f at a single point z(0) (i.e., |W-f (z(0))|) for n-variable Boolean functions with probability at least 8/pi(2) using the number of O(1/vertical bar W-f (z(0))vertical bar epsilon) queries, promised that the accuracy is epsilon, while the best known classical algorithm requires O(2(n)) queries. The Hamming distance between Boolean functions is used to study the linearity testing and other important problems. We take advantage of Walsh transform to calculate the Hamming distance between two n-variable Boolean functions f and g using O(1) queries in some cases. Then, we exploit another quantum algorithm which converts computing Hamming distance between two Boolean functions to quantum amplitude estimation (i.e., approximate counting). If Ham(f, g) = t not equal 0, we can approximately compute Ham(f,g) with probability at least 2/3 by combining our algorithm and Approx - Count (f, epsilon) algorithm using the expected number of Theta(root N/([epsilon t] + 1) + root t(N-t)/[epsilon t] + 1) queries, promised that the accuracy is epsilon. Moreover, our algorithm is optimal, while the exact query complexity for the above problem epsilon is Theta(N) and the query complexity with the accuracy epsilon is O(1/epsilon(2) N/(t + 1)) in classical algorithm, where N = 2(n). Finally, we present three exact quantum query algorithms for two promise problems on Hamming distance using O(1) queries, while any classical deterministic algorithm solving the problem uses O(2(n)) queries.

关键词： Walsh transform Hamming distance Bernstein-Vazirani algorithm quantum algorithms quantum amplitude estimation

来源：评论

学校读者我要写书评

暂无评论

quantum algorithms for Simon's Problem over Nonabelian Groups

引用

ACM TRANSACTIONS ON algorithms 2009年第1期6卷 1–15页

作者： Alagic, Gorjan Moore, Cristopher Russell, Alexander Univ Waterloo Inst Quantum Comp Waterloo ON N2L 3G1 Canada Univ New Mexico Santa Fe Inst Albuquerque NM 87131 USA Univ Connecticut Dept Comp Sci & Engn Storrs CT 06269 USA

Daniel Simon's 1994 discovery of an efficient quantum algorithm for finding "hidden shifts" of Z(2)(n) provided the first algebraic problem for which quantum computers are exponentially faster than their classical counterparts. In this article, we study the generalization of Simon's problem to arbitrary groups. Fixing a finite group G, this is the problem of recovering an involution (m) over right arrow = (m(1),..., m(n)) is an element of G(n) from an oracle f with the property that f ((x) over right arrow.(y) over right arrow) = f ((x) over right arrow) double left right arrow (y) over right arrow is an element of {(1) over right arrow, (m) over right arrow}. In the current parlance, this is the hidden subgroup problem (HSP) over groups of the form G(n), where G is a nonabelian group of constant size, and where the hidden subgroup is either trivial or has order two. Although groups of the form G(n) have a simple product structure, they share important representation-theoretic properties with the symmetric groups S-n, where a solution to the HSP would yield a quantum algorithm for Graph Isomorphism. In particular, solving their HSP with the so-called "standard method" requires highly entangled measurements on the tensor product of many coset states. In this article, we provide quantum algorithms with time complexity 2(O(root n)) that recover hidden involutions (m) over right arrow = (m(1),..., m(n)) is an element of G(n) where, as in Simon's problem, each m(i) is either the identity or the conjugate of a known element m which satisfies kappa(m) = -kappa(1) for some kappa is an element of (G) over cap. Our approach combines the general idea behind Kuperberg's sieve for dihedral groups with the "missing harmonic" approach of Moore and Russell. These are the first nontrivial HSP algorithms for group families that require highly entangled multiregister Fourier sampling.

关键词： Hidden subgroup problem quantum algorithms

来源：评论

学校读者我要写书评

暂无评论

quantum algorithms for electronic structure calculations: Particle-hole Hamiltonian and optimized wave-function expansions

引用

Physical Review A 2018年第2期98卷 022322-022322页

作者： Panagiotis Kl. Barkoutsos Jerome F. Gonthier Igor Sokolov Nikolaj Moll Gian Salis Andreas Fuhrer Marc Ganzhorn Daniel J. Egger Matthias Troyer Antonio Mezzacapo Stefan Filipp Ivano Tavernelli IBM Research GmbH Zurich Research Laboratory Säumerstrasse 4 8803 Rüschlikon Switzerland Institute for Theoretical Physics ETH Zurich 8093 Zurich Switzerland Kenneth S. Pitzer Center for Theoretical Chemistry Department of Chemistry University of California Berkeley California 94720 USA Microsoft Quantum Microsoft Redmond Washington 98052 USA IBM T. J. Watson Research Center Yorktown Heights New York 10598 USA

In this work we investigate methods to improve the efficiency and scalability of quantum algorithms for quantum chemistry applications. We propose a transformation of the electronic structure Hamiltonian in the second quantization framework into the particle-hole picture, which offers a better starting point for the expansion of the system wave function. The state of the molecular system at study is parametrized so as to constrain the sampling of the corresponding wave function within the sector of the molecular Fock space that contains the desired solution. To this end, we explore different mapping schemes to encode the molecular ground state wave function in a quantum register. Taking advantage of known post-Hartree-Fock quantum chemistry approaches and heuristic Hilbert space search quantum algorithms, we propose a new family of quantum circuits based on exchange-type gates that enable accurate calculations while keeping the gate count (i.e., the circuit depth) low. The particle-hole implementation of the unitary coupled-cluster (UCC) method within the variational quantum eigensolver approach gives rise to an efficient quantum algorithm, named q-UCC, with important advantages compared to the straightforward translation of the classical coupled-cluster counterpart. In particular, we show how a single Trotter step in the expansion of the system wave function can accurately and efficiently reproduce the ground-state energy of simple molecular systems.

关键词： quantum algorithms quantum gates quantum simulation

来源：评论

学校读者我要写书评

暂无评论

quantum algorithms FOR SHIFTED SUBSET PROBLEMS

引用

quantum INFORMATION & COMPUTATION 2009年第5-6期9卷 500-512页

作者： Montanro, Ashley Univ Bristol Dept Comp Sci Bristol BS8 1UB Avon England

We consider a recently proposed generalisation of the abelian hidden subgroup problem: the shifted subset problem. The problem is to determine a subset S of some abelian group, given access to quantum states of the form (S + x), for some unknown shift x. We give quantum algorithms to find Hamming spheres and other subsets of the boolean cube {0, 1}(n). The algorithms have time complexity polynomial in n and give rise to exponential separations from classical computation.

关键词： quantum algorithms shifted subsets Krawtchouk polynomials

来源：评论

学校读者我要写书评

暂无评论

quantum algorithms FOR GIBBS SAMPLING AND HITTING-TIME ESTIMATION

引用

quantum INFORMATION & COMPUTATION 2017年第1-2期17卷 41-64页

作者： Chowdhury, Anirban Narayan Somma, Rolando D. Univ New Mexico Ctr Quantum Informat & Control Albuquerque NM 87131 USA New Mexico Consortium Los Alamos Res Pk Los Alamos NM 87544 USA Los Alamos Natl Lab Theoret Div Los Alamos NM 87545 USA

We present quantum algorithms for solving two problems regarding stochastic processes. The first algorithm prepares the thermal Gibbs state of a quantum system and runs in time almost linear in,root N beta/Z and polynomial in log(l/c), where N is the Hilbert space dimension, beta is the inverse temperature, Z is the partition function, and c is the desired precision of the output state. Our quantum algorithm exponentially improves the complexity dependence on 1/c and polynomially improves the dependence on beta of known quantum algorithms for this problem. The second algorithm estimates the hitting time of a Markov chain. For a sparse stochastic matrix P, it runs in time almost linear in 1/(c Delta(3/2)), where c is the absolute precision in the estimation and Delta is a parameter determined by P, and whose inverse is an upper bound of the hitting time. Our quantum algorithm quadratically improves the complexity dependence on 1/c and 1/Delta of the analog classical algorithm for hitting-time estimation. Both algorithms use tools recently developed in the context of Hamiltonian simulation, spectral gap amplification, and solving linear systems of equations.

关键词： quantum algorithms stochastic processes

来源：评论

学校读者我要写书评

暂无评论

quantum algorithms with local particle-number conservation: Noise effects and error correction

引用

Physical Review A 2021年第4期103卷 042412-042412页

作者： Michael Streif Martin Leib Filip Wudarski Eleanor Rieffel Zhihui Wang Quantum Artificial Intelligence Laboratory (QuAIL) NASA Ames Research Center Moffett Field California 94035 USA USRA Research Institute for Advanced Computer Science (RIACS) Mountain View California 94043 USA Data:Lab Volkswagen Group Ungererstrasse 69 80805 München Germany University Erlangen-Nürnberg (FAU) Institute of Theoretical Physics Staudtstrasse 7 91058 Erlangen Germany

quantum circuits with local particle-number conservation restrict the quantum computation to a subspace of the Hilbert space of the qubit register. In a noiseless or fault-tolerant quantum computation, such quantities are preserved. In the presence of noise, however, the evolution's symmetry could be broken and nonvalid states could be sampled at the end of the computation. On the other hand, the restriction to a subspace in the ideal case suggests the possibility of more resource-efficient error-mitigation techniques for circuits preserving symmetries that are not possible for general circuits. Here, we analyze the probability of staying in such symmetry-preserved subspaces under noise, providing an exact formula for local depolarizing noise. We apply our findings to benchmark, under depolarizing noise, the symmetry robustness of the XY quantum alternating operator Ansatz, which has local particle-number conserving symmetries and is a special case of the quantum alternating operator Ansatz. We also analyze the influence of the choice of encoding the problem on the symmetry robustness of the algorithm and discuss a simple adaption of the bit-flip code to correct for symmetry-breaking errors with reduced resources.

关键词： quantum algorithms quantum computation

来源：评论

学校读者我要写书评

暂无评论

Discrimination of quantum states and probabilistic quantum algorithms

Discrimination of quantum states and probabilistic quantum a...

引用

Conference on Noise and Information in Nanoelectronics, Sensors and Standards II

作者： Bergou, JA CUNY Hunter Coll Dept Phys & Astron New York NY 10021 USA

ISBN: (纸本)0819453943

In quantum information and quantum computing, the carrier of information is some quantum system and information is encoded in its state. The state, however, is not an observable in quantum mechanics, thus a fundamental problem arises: after processing the information it has to be read out or, in other words, the state of the system must be determined. When the possible target states are orthogonal, this is a relatively simple, provided the set of possible target states is known. But when the possible target states are not orthogonal their discrimination is far from being trivial even if their set is known. Thus the problem of discriminating among non-orthogonal states is ubiquitous in quantum information and quantum computing, underlying all communication and computing schemes. It is the subject of this talk to review recent theoretical and experimental advances in this field.

关键词： quantum information quantum algorithms quantum state discrimination generalized measurements

来源：评论

学校读者我要写书评

暂无评论

Variable time amplitude amplification and quantum algorithms for linear algebra problems

Variable time amplitude amplification and quantum algorithms...

引用

29th International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Ambainis, Andris Univ Latvia Fac Comp Raina Bulv 19 LV-1586 Riga Latvia

ISBN: (纸本)9783939897354

quantum amplitude amplification is a method of increasing a success probability of an algorithm from a small epsilon > 0 to Theta(1) with less repetitions than classically. In this paper, we generalize quantum amplitude amplification to the case when parts of the algorithm that is being amplified stop at different times. We then apply the new variable time amplitude amplification to give two new quantum algorithms for linear algebra problems. Our first algorithm is an improvement of Harrow et al. algorithm for solving systems of linear equations. We improve the running time of the algorithm from O(k(2) log N) to O(k log(3) k logN) where k is the condition number of the system of equations. Our second algorithm tests whether a matrix A is singular or far-from-singular, faster then the previously known algorithms.

关键词： quantum computing quantum algorithms amplitude amplification linear equations

来源：评论

学校读者我要写书评

暂无评论

Qubit-Efficient Variational quantum algorithms for Image Segmentation 5

Qubit-Efficient Variational Quantum Algorithms for Image Seg...

引用

2024 International Conference on quantum Computing and Engineering

作者： Venkatesh, Supreeth Mysore Macaluso, Antonio Nuske, Marlon Klusch, Matthias Dengel, Andreas Univ Kaiserslautern Landau RPTU Kaiserslautern Germany German Res Ctr Artificial Intelligence DFKI Saarbrucken Germany German Res Ctr Artificial Intelligence DFKI Kaiserslautern Germany

ISBN: (纸本)9798331541378

quantum computing is expected to transform a range of computational tasks beyond the reach of classical algorithms. In this work, we examine the application of variational quantum algorithms (VQAs) for unsupervised image segmentation to partition images into separate semantic regions. Specifically, we formulate the task as a graph cut optimization problem and employ two established qubit-efficient VQAs, which we refer to as Parametric Gate Encoding (PGE) and Ancilla Basis Encoding (ABE), to find the optimal segmentation mask. In addition, we propose Adaptive Cost Encoding (ACE), a new approach that leverages the same circuit architecture as ABE but adopts a problem-dependent cost function. We benchmark PGE, ABE and ACE on synthetically generated images, focusing on quality and trainability. ACE shows consistently faster convergence in training the parameterized quantum circuits in comparison to PGE and ABE. Furthermore, we provide a theoretical analysis of the scalability of these approaches against the quantum Approximate Optimization Algorithm (QAOA), showing a significant cutback in the quantum resources, especially in the number of qubits that logarithmically depends on the number of pixels. The results validate the strengths of ACE, while concurrently highlighting its inherent limitations and challenges. This paves way for further research in quantum-enhanced computer vision.

关键词： quantum algorithms variational circuits image segmentation combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

quantum algorithms FOR ONE-DIMENSIONAL INFRASTRUCTURES

引用

quantum INFORMATION & COMPUTATION 2014年第1-2期14卷 56-90页

作者： Sarvepalli, Pradeep Wocjan, Pawel IIT Madras Dept Elect Engn Madras 600036 Tamil Nadu India Univ Cent Florida Dept Elect Engn & Comp Sci Orlando FL 32816 USA

Infrastructures are group-like objects that make their appearance in arithmetic geometry in the study of computational problems related to number fields and function fields over finite fields. The most prominent computational tasks of infrastructures are the computation of the circumference of the infrastructure and the generalized discrete logarithms. Both these problems are not known to have efficient classical algorithms for an arbitrary infrastructure. Our main contributions are polynomial time quantum algorithms for one-dimensional infrastructures that satisfy certain conditions. For instance, these conditions are always fulfilled for infrastructures obtained from number fields and function fields, both of unit rank one. Since quadratic number fields give rise to such infrastructures, this algorithm can be used to solve Pell's equation and the principal ideal problem. In this sense we generalize Hallgren's quantum algorithms for quadratic number fields, while also providing a polynomial speedup over them. Our more general approach shows that these quantum algorithms can also be applied to infrastructures obtained from complex cubic and totally complex quartic number fields. Our improved way of analyzing the performance makes it possible to show that these algorithms succeed with constant probability independent of the problem size. In contrast, the lower bound on the success probability due to Hallgren decreases as the fourth power of the logarithm of the circumference. Our analysis also shows that fewer qubits are required. We also contribute to the study of infrastructures, and show how to compute efficiently within infrastructures.

关键词： quantum algorithms infrastructures circumference period finding quantum Fourier transform discrete log problem

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：