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

quantum INFORMATION & COMPUTATION 2008年第8-9期8卷 834-859页

作者： Furrow, Bartholomew Univ British Columbia Dept Phys & Astron Vancouver BC V6T 1Z1 Canada

This paper's aim is to explore improvements to, and applications of, a fundamental quantum algorithm invented by Grover[1]. Grover's algorithm is a. basic tool that can be applied to a large number of problems in computer science, creating quantum algorithms that axe polynomially faster than fastest, known and fastest possible classical algorithms that solve the same problems. Our goal in this paper is to make these techniques readily accessible to those without a strong background in quantum physics: we achieve this by, providing a set of tools, each of which makes use of Grover's algorithm or similar techniques. which can be used as subroutines in many quantum algorithms. The tools we provide are carefully constructed: they are easy to use, and in many cases they are asymptotically faster than the best, tools previously available. The tools we build on include algorithms by Boyer: Brassard, Hoyer and Tapp[2], Buhrman, Cleve, de Witt and Zalka[3] and Durr and Hoyer [4]. After creating our tools., we create several new quantum algorithms, each of which is faster than the fastest known deterministic classical algorithm that accomplishes the same aim. and some of which are faster than the fastest possible deterministic classical algorithm. These algorithms solve problems front the fields of graph theory and computational geometry, and some employ dynamic programming techniques. We discuss a breadth-first search that is faster than circle minus(edges) (the classical limit) in a dense graph. maximum-points-on-a-line in O(N-3/2 lg N) (faster than the fastest classical algorithm known), as well as several other algorithms that are similarly illustrative of solutions in some class of problem. Through these new algorithms we illustrate the use of our tools. working to encourage their use and the study of quantum algorithms in general.

关键词： quantum algorithms quantum computing Grover's algorithm BBHT BCWZ

来源：评论

学校读者我要写书评

暂无评论

Optimized numerical gradient and Hessian estimation for variational quantum algorithms

引用

Physical Review A 2023年第4期107卷 042421-042421页

作者： Y. S. Teo Department of Physics and Astronomy Seoul National University 08826 Seoul South Korea

Sampling noisy intermediate-scale quantum devices is a fundamental step that converts coherent quantum-circuit outputs to measurement data for running variational quantum algorithms that utilize gradient and Hessian methods in cost-function optimization tasks. This step, however, introduces estimation errors in the resulting gradient or Hessian computations. To minimize these errors, we discuss tunable numerical estimators, which are the finite difference (including their generalized versions) and scaled parameter-shift estimators [introduced in Phys. Rev. A 103, 012405 (2021)], and propose operational circuit-averaged methods to optimize them. We show that these optimized numerical estimators offer estimation errors that drop exponentially with the number of circuit qubits for a given sampling-copy number, revealing a direct compatibility with the barren-plateau phenomenon. In particular, there exists a critical sampling-copy number below which an optimized difference estimator gives a smaller average estimation error in contrast to the standard (analytical) parameter-shift estimator, which exactly computes gradient and Hessian components. Moreover, this critical number grows exponentially with the circuit-qubit number. Finally, by forsaking analyticity, we demonstrate that the scaled parameter-shift estimators beat the standard unscaled ones in estimation accuracy under any situation, with comparable performances to those of the difference estimators within significant copy-number ranges, and are the best ones if larger copy numbers are affordable.

关键词： quantum algorithms

来源：评论

学校读者我要写书评

暂无评论

Ability of error correlations to improve the performance of variational quantum algorithms

引用

Physical Review A 2023年第4期107卷 042426-042426页

作者： Joris Kattemölle Guido Burkard Department of Physics University of Konstanz D-78457 Konstanz Germany

The quantum approximate optimization algorithm (QAOA) has the potential of providing a useful quantum advantage on noisy intermediate-scale quantum (NISQ) devices. The effects of uncorrelated noise on variational quantum algorithms such as QAOA have been studied intensively. Recent experimental results, however, show that the errors impacting NISQ devices are significantly correlated. We introduce a model for both spatially and temporally (non-Markovian) correlated errors based on classical environmental fluctuators. The model allows for the independent variation of the marginalized spacetime-local error probability and the correlation strength. Using this model, we study the effects of correlated stochastic noise on QAOA. We find evidence that the performance of QAOA improves as the correlation time or correlation length of the noise is increased at fixed local error probabilities. This shows that noise correlations in themselves need not be detrimental for NISQ algorithms such as QAOA.

关键词： quantum algorithms quantum computation quantum error correction

来源：评论

学校读者我要写书评

暂无评论

SINGLE-QUERY quantum algorithms FOR SYMMETRIC PROBLEMS

引用

quantum INFORMATION & COMPUTATION 2016年第1-2期16卷 19-38页

作者： Bucicovschi, Orest Copeland, Daniel Meyer, David A. Pommersheim, James Univ Calif San Diego Dept Math Project Geometry & Phys La Jolla CA 92093 USA Reed Coll Dept Math Portland OR 97202 USA

Given a unitary representation of a finite group on a finite-dimensional Hilbert space, we show how to find a state whose translates under the group are distinguishable with the highest probability. We apply this to several quantum oracle problems, including the GROUP MULTIPLICATION problem, in which the product of an ordered n-tuple of group elements is to be determined by querying elements of the tuple. For any finite group G, we give an algorithm to find the product of two elements of G with a single quantum query with probability 2/vertical bar G vertical bar. This generalizes Deutsch's Algorithm from Z(2) to an arbitrary finite group. We further prove that this algorithm is optimal. We also introduce the HIDDEN CONJUGATING ELEMENT PROBLEM, in which the oracle acts by conjugating by an unknown element of the group. We show that for many groups, including dihedral and symmetric groups, the unknown element can be determined with probability 1 using a single quantum query.

关键词： quantum state discrimination quantum algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient quantum algorithms for Stabilizer Entropies

引用

Physical Review Letters 2024年第24期132卷 240602-240602页

作者： Tobias Haug Soovin Lee M. S. Kim Quantum Research Center Blackett Laboratory

Stabilizer entropies (SEs) are measures of nonstabilizerness or “magic” that quantify the degree to which a state is described by stabilizers. SEs are especially interesting due to their connections to scrambling, localization and property testing. However, applications have been limited so far as previously known measurement protocols for SEs scale exponentially with the number of qubits. Here, we efficiently measure SEs for integer Rényi index n>1 via Bell measurements. The SE of N-qubit quantum states can be measured with O(n) copies and O(nN) classical computational time, where for even n we additionally require the complex conjugate of the state. We provide efficient bounds of various nonstabilizerness monotones that are intractable to compute beyond a few qubits. Using the IonQ quantum computer, we measure SEs of random Clifford circuits doped with non-Clifford gates and give bounds for the stabilizer fidelity, stabilizer extent, and robustness of magic. We provide efficient algorithms to measure Clifford-averaged 4n-point out-of-time-order correlators and multifractal flatness. With these measures we study the scrambling time of doped Clifford circuits and random Hamiltonian evolution depending on nonstabilizerness. Counterintuitively, random Hamiltonian evolution becomes less scrambled at long times, which we reveal with the multifractal flatness. Our results open up the exploration of nonstabilizerness with quantum computers.

关键词： Entropy quantum algorithms quantum algorithms & computation quantum computation quantum correlations, foundations & formalism quantum information theory Resource theories Many-body techniques

来源：评论

学校读者我要写书评

暂无评论

Error mitigation for variational quantum algorithms through mid-circuit measurements

引用

Physical Review A 2022年第2期105卷 022441-022441页

作者： Ludmila Botelho Adam Glos Akash Kundu Jarosław Adam Miszczak Özlem Salehi Zoltán Zimborás Institute of Theoretical and Applied Informatics Polish Academy of Sciences Bałtycka 5 44-100 Gliwice Poland Joint Doctoral School Silesian University of Technology Akademicka 2a 44-100 Gliwice Poland QWorld Association† Kesklinna linnaosa Tartu mnt 67/1-13b 10115 Tallinn Estonia Wigner Research Centre for Physics H-1525 P.O. Box 49 Budapest Hungary BME-MTA Lendület Quantum Information Theory Research Group 1111 Budapest Hungary

Noisy intermediate-scale quantum algorithms require novel paradigms of error mitigation. To obtain noise-robust quantum computers, each logical qubit is equipped with hundreds or thousands of physical qubits. However, it is not possible to use memory-consuming techniques for current quantum devices having at most hundreds or thousands of physical qubits on their own. For specific problems, valid quantum states have a unique structure as in the case of Fock states and W states where the Hamming weight is fixed, and the evolution takes place in a smaller subspace of the full Hilbert space. With this preknowledge, some errors can be detected during the evolution of the circuit, by filtering the states not obeying the pattern through postselection. In this paper, we present mid-circuit postselection schemes for frequently used encodings such as one-hot, binary, gray, and domain-wall encoding. For the particular subspace of one-hot states, we propose a method that works by compressing the full Hilbert space to a smaller subspace, allowing projecting to the desired subspace without using any ancilla qubits. We demonstrate the effectiveness of the approach for the quantum alternating operator ansatz algorithm. Our method is particularly suitable for the currently available hardware, where measuring and resetting are possible, but classical conditional operators are not.

关键词： quantum algorithms quantum computation

来源：评论

学校读者我要写书评

暂无评论

Analog quantum algorithms for the mixing of Markov chains

引用

Physical Review A 2020年第2期102卷 022423-022423页

作者： Shantanav Chakraborty Kyle Luh Jérémie Roland QuIC Ecole Polytechnique de Bruxelles Université libre de Bruxelles 1050 Brussels Belgium Center for Mathematical Sciences and Applications Harvard University Cambridge Massachusetts 02138 USA

The problem of sampling from the stationary distribution of a Markov chain finds widespread applications in a variety of fields. The time required for a Markov chain to converge to its stationary distribution is known as the classical mixing time. In this article, we deal with analog quantum algorithms for mixing. First, we provide an analog quantum algorithm that, given a Markov chain, allows us to sample from its stationary distribution in a time that scales as the sum of the square root of the classical mixing time and the square root of the classical hitting time. Our algorithm makes use of the framework of interpolated quantum walks and relies on Hamiltonian evolution in conjunction with von Neumann measurements. There also exists a different notion for quantum mixing: the problem of sampling from the limiting distribution of quantum walks, defined in a time-averaged sense. In this scenario, the quantum mixing time is defined as the time required to sample from a distribution that is close to this limiting distribution. Recently, we provided an upper bound on the quantum mixing time for Erdős-Rényi random graphs [Phys. Rev. Lett. 124, 050501 (2020)]. Here, we also extend and expand upon our findings therein. Namely, we provide an intuitive understanding of the state-of-the-art random matrix theory tools used to derive our results. In particular, for our analysis we require information about macroscopic, mesoscopic, and microscopic statistics of eigenvalues of random matrices which we highlight here. Furthermore, we provide numerical simulations that corroborate our analytical findings and extend this notion of mixing from simple graphs to any ergodic, reversible, Markov chain.

关键词： quantum algorithms quantum walks

来源：评论

学校读者我要写书评

暂无评论

Near-Term Efficient quantum algorithms for Entanglement Analysis

引用

Physical Review Applied 2023年第2期20卷 024071-024071页

作者： Ranyiliu Chen Benchi Zhao Xin Wang Institute for Quantum Computing Baidu Research Beijing 100193 China QMATH Department of Mathematical Sciences University of Copenhagen Universitetsparken 5 Copenhagen 2100 Denmark Thrust of Artificial Intelligence Information Hub Hong Kong University of Science and Technology (Guangzhou) Nansha China

Entanglement plays a crucial role in quantum physics and is the key resource in quantum information processing. However, entanglement detection and quantification are believed to be hard due to the operational impracticality of existing methods. This work proposes three near-term efficient algorithms that exploit the hybrid quantum-classical technique to address this difficulty. The first algorithm finds the Schmidt decomposition—a powerful tool to analyze the properties and structure of entanglement—for bipartite pure states. While the logarithm negativity can be calculated from the Schmidt decomposition, we propose the second algorithm to estimate the logarithm negativity for bipartite pure states, where the width of the parameterized quantum circuits is further reduced. Finally, we generalize our framework for mixed states, leading to our third algorithm that detects entanglement on specific families of states, and determines distillability in general. All three algorithms share a similar framework where the optimizations are accomplished by maximizing a cost function utilizing local parameterized quantum circuits, with better hardware efficiency and practicality compared to existing methods. The experimental implementation on quantum Leaf using the Institute of Physics, Chinese Academy of Sciences superconducting quantum processor exhibits the validity and practicality of our methods for analyzing and quantifying entanglement on near-term quantum devices.

关键词： Entanglement detection Entanglement measures quantum algorithms quantum entanglement

来源：评论

学校读者我要写书评

暂无评论

Qubit-Efficient Randomized quantum algorithms for Linear Algebra

引用

PRX quantum 2024年第2期5卷 020324-020324页

作者： Samson Wang Sam McArdle Mario Berta Department of Physics Imperial College London London SW7 2BW United Kingdom AWS Center for Quantum Computing Pasadena CA 91106 USA Institute for Quantum Information and Matter Caltech Pasadena CA 91125 USA Department of Computing Imperial College London London SW7 2BW United Kingdom Institute for Quantum Information RWTH Aachen University 52056 Aachen Germany

We propose a class of randomized quantum algorithms for the task of sampling from matrix functions, without the use of quantum block encodings or any other coherent oracle access to the matrix elements. As such, our use of qubits is purely algorithmic and no additional qubits are required for quantum data structures. Our algorithms start from a classical data structure in which the matrix of interest is specified in the Pauli basis. For N×N Hermitian matrices, the space cost is log (N)+1 qubits and, depending on the structure of the matrices, the gate complexity can be comparable to state-of-the-art methods that use quantum data structures of up to size O(N2), when considering equivalent end-to-end problems. Within our framework, we present a quantum linear system solver that allows one to sample properties of the solution vector, as well as algorithms for sampling properties of ground states and Gibbs states of Hamiltonians. As a concrete application, we combine these subroutines to present a scheme for calculating Green’s functions of quantum many-body systems.

关键词： quantum algorithms quantum algorithms & computation quantum algorithms for chemical calculations

来源：评论

学校读者我要写书评

暂无评论

Characterization of exact one-query quantum algorithms

引用

Physical Review A 2020年第2期101卷 022325-022325页

作者： Weijiang Chen Zekun Ye Lvzhou Li Institute of Computer Science Theory School of Data and Computer Science Sun Yat-Sen University Guangzhou 510006 China Center for Quantum Computing Peng Cheng Laboratory Shenzhen 518055 China Ministry of Education Key Laboratory of Machine Intelligence and Advanced Computing Sun Yat-Sen University Guangzhou 510006 China

The quantum query model is one of the most important models in quantum computing. Several well-known quantum algorithms are captured by this model, including the Deutsch-Jozsa algorithm, the Simon algorithm, the Grover algorithm, and others. In this paper, we characterize the computational power of exact one-query quantum algorithms. It is proved that a total Boolean function f:{0,1}n→{0,1} can be exactly computed by a one-query quantum algorithm if and only if f(x)=xi1 or xi1⊕xi2 (up to isomorphism). Note that, unlike most work in the literature based on the polynomial method, our proof does not resort to any knowledge about the polynomial degree of f.

关键词： quantum algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：