集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织

量子算法

此词条暂由水流心不竞初译，翻译字数共，未经审校，带来阅读不便，请见谅。

模板:Use American English 模板:使用美式英语

{{简述}算法在量子计算机上运行，通常依赖于叠加和/或纠缠}}

In quantum computing, a quantum algorithm is an algorithm which runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation.[1][2] A classical (or non-quantum) algorithm is a finite sequence of instructions, or a step-by-step procedure for solving a problem, where each step or instruction can be performed on a classical computer. Similarly, a quantum algorithm is a step-by-step procedure, where each of the steps can be performed on a quantum computer. Although all classical algorithms can also be performed on a quantum computer,[3]:126 the term quantum algorithm is usually used for those algorithms which seem inherently quantum, or use some essential feature of quantum computation such as quantum superposition or quantum entanglement.

In quantum computing, a quantum algorithm is an algorithm which runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation. A classical (or non-quantum) algorithm is a finite sequence of instructions, or a step-by-step procedure for solving a problem, where each step or instruction can be performed on a classical computer. Similarly, a quantum algorithm is a step-by-step procedure, where each of the steps can be performed on a quantum computer. Although all classical algorithms can also be performed on a quantum computer, the term quantum algorithm is usually used for those algorithms which seem inherently quantum, or use some essential feature of quantum computation such as quantum superposition or quantum entanglement.

在量子计算中，量子算法是在量子计算的实际模型上运行的一种算法，最常用的模型是量子计算电路模型。经典(或非量子)算法是一个有限的指令序列，或解决问题的一步一步的过程，其中每一步或指令都可以在经典计算机上执行。类似地，量子算法是一个循序渐进的过程，其中每个步骤都可以在量子计算机上执行。虽然所有的经典算法也可以在量子计算机上执行，但量子算法这个术语通常用于那些看似固有的量子算法，或者使用一些量子计算的本质特征，如态叠加原理或量子纠缠。


Problems which are undecidable using classical computers remain undecidable using quantum computers.[4]:127 What makes quantum algorithms interesting is that they might be able to solve some problems faster than classical algorithms because the quantum superposition and quantum entanglement that quantum algorithms exploit probably can't be efficiently simulated on classical computers (see Quantum supremacy).

Problems which are undecidable using classical computers remain undecidable using quantum computers. What makes quantum algorithms interesting is that they might be able to solve some problems faster than classical algorithms because the quantum superposition and quantum entanglement that quantum algorithms exploit probably can't be efficiently simulated on classical computers (see Quantum supremacy).

使用经典计算机是不可判定的问题使用量子计算机仍然是不可判定的问题。量子算法的有趣之处在于，它们可能比传统算法更快地解决某些问题，因为量子算法所利用的态叠加原理和量子纠缠可能无法在传统计算机上有效地模拟。


The best-known algorithms are Shor's algorithm for factoring and Grover's algorithm for searching an unstructured database or an unordered list. Shor's algorithms runs much (almost exponentially) faster than the best-known classical algorithm for factoring, the general number field sieve.[5] Grover's algorithm runs quadratically faster than the best possible classical algorithm for the same task,[citation needed] a linear search.

The best-known algorithms are Shor's algorithm for factoring and Grover's algorithm for searching an unstructured database or an unordered list. Shor's algorithms runs much (almost exponentially) faster than the best-known classical algorithm for factoring, the general number field sieve. Grover's algorithm runs quadratically faster than the best possible classical algorithm for the same task, a linear search.

最著名的算法是 Shor 的分解算法和 Grover 的搜索非结构化数据库或无序列表的算法。肖尔的算法比最著名的古典因式分解算法---- 普通数域筛选法分解算法运行得快得多(几乎是指数级)。对于同样的任务，Grover 的算法比最好的经典算法(线性搜索)运行得快。


Overview概述

Quantum algorithms are usually described, in the commonly used circuit model of quantum computation, by a quantum circuit which acts on some input qubits and terminates with a measurement. A quantum circuit consists of simple quantum gates which act on at most a fixed number of qubits. The number of qubits has to be fixed because a changing number of qubits implies non-unitary evolution. Quantum algorithms may also be stated in other models of quantum computation, such as the Hamiltonian oracle model.[6]


Quantum algorithms can be categorized by the main techniques used by the algorithm. Some commonly used techniques/ideas in quantum algorithms include phase kick-back, phase estimation, the quantum Fourier transform, quantum walks, amplitude amplification and topological quantum field theory. Quantum algorithms may also be grouped by the type of problem solved, for instance see the survey on quantum algorithms for algebraic problems.[7]

量子算法可以根据算法使用的主要技术进行分类。量子算法中常用的一些技术/思想包括相位反冲、相位估计、量子傅里叶变换、量子行走s、振幅放大和拓扑量子场论。量子算法也可以根据所解决问题的类型进行分组，例如参见代数问题的量子算法综述。[8]

The Deutsch–Jozsa algorithm solves a black-box problem which probably requires exponentially many queries to the black box for any deterministic classical computer, but can be done with exactly one query by a quantum computer. If we allow both bounded-error quantum and classical algorithms, then there is no speedup since a classical probabilistic algorithm can solve the problem with a constant number of queries with small probability of error. The algorithm determines whether a function f is either constant (0 on all inputs or 1 on all inputs) or balanced (returns 1 for half of the input domain and 0 for the other half).

Deutsch-Jozsa 算法解决了一个黑盒问题，这个问题可能需要对任何确定性经典计算机的黑盒进行指数级的查询，但是量子计算机只能完成一次查询。如果我们同时允许有界误差量子算法和经典算法，那么就不存在加速比，因为经典的概率算法可以在误差概率很小的情况下解决常数查询问题。该算法确定函数 f 是常量(所有输入为0还是所有输入为1)还是平衡(一半输入域返回1，另一半返回0)。

Algorithms based on the quantum Fourier transform基于量子傅里叶变换的算法

The quantum Fourier transform is the quantum analogue of the discrete Fourier transform, and is used in several quantum algorithms. The Hadamard transform is also an example of a quantum Fourier transform over an n-dimensional vector space over the field F2. The quantum Fourier transform can be efficiently implemented on a quantum computer using only a polynomial number of quantum gates.[citation needed]

quantum Fourier transform是discrete Fourier transform的量子模拟，并用于几种量子算法中。Hadamard变换也是场F'2上n维向量空间上的量子傅里叶变换的示例。量子傅里叶变换可以在量子计算机上有效地实现，只需使用量子门s的多项式数。[citation needed]

Deutsch–Jozsa algorithm Deutsch-Jozsa算法

Main article: Deutsch–Jozsa algorithm
Main article: Deutsch–Jozsa算法

The Bernstein–Vazirani algorithm is the first quantum algorithm that solves a problem more efficiently than the best known classical algorithm. It was designed to create an oracle separation between BQP and BPP.

伯恩斯坦-瓦兹拉尼算法是第一个比最著名的经典算法更有效地解决问题的量子算法。它被设计用来创建 BQP 和 BPP 之间的预言分离。


The Deutsch–Jozsa algorithm solves a black-box problem which probably requires exponentially many queries to the black box for any deterministic classical computer, but can be done with exactly one query by a quantum computer. If we allow both bounded-error quantum and classical algorithms, then there is no speedup since a classical probabilistic algorithm can solve the problem with a constant number of queries with small probability of error. The algorithm determines whether a function f is either constant (0 on all inputs or 1 on all inputs) or balanced (returns 1 for half of the input domain and 0 for the other half).

Deutsch–Jozsa算法解决了一个黑盒问题，对于任何确定性经典计算机，这个问题可能需要对黑盒进行指数级的多次查询，但是量子计算机只需要一次查询就可以完成。如果我们同时允许有界误差量子算法和经典算法，那么就不会有加速，因为经典概率算法可以用小错误概率的常量查询来解决问题。该算法确定函数“f”是常量（所有输入为0还是1）还是平衡的（一半输入域返回1，另一半返回0）。

Bernstein–Vazirani algorithm伯恩斯坦-瓦齐拉尼算法

Main article: Bernstein–Vazirani algorithm
Main article: Bernstein–Vazirani算法

Simon's algorithm solves a black-box problem exponentially faster than any classical algorithm, including bounded-error probabilistic algorithms. This algorithm, which achieves an exponential speedup over all classical algorithms that we consider efficient, was the motivation for Shor's factoring algorithm.

Simon 的算法解决黑盒问题的速度比任何经典算法都要快，包括有界错误概率算法。这个算法比我们认为有效的所有经典算法都达到了指数级的加速，这也是 Shor 的因式分解算法的动机。


The Bernstein–Vazirani algorithm is the first quantum algorithm that solves a problem more efficiently than the best known classical algorithm. It was designed to create an oracle separation between BQP and BPP.

Bernstein-Vazirani算法是第一个比最著名的经典算法更有效地解决问题的量子算法。它的目的是在BQP和 BPP之间创建一个oracle separation。

Simon's algorithm西蒙算法

Main article: Simon's algorithm
Main article: Simon算法

The quantum phase estimation algorithm is used to determine the eigenphase of an eigenvector of a unitary gate given a quantum state proportional to the eigenvector and access to the gate. The algorithm is frequently used as a subroutine in other algorithms.

量子相位估计算法被用来确定给定与特征向量成正比的量子态的幺正门的特征向量的特征相位并访问该门。该算法在其他算法中经常作为子程序使用。


Simon's algorithm solves a black-box problem exponentially faster than any classical algorithm, including bounded-error probabilistic algorithms. This algorithm, which achieves an exponential speedup over all classical algorithms that we consider efficient, was the motivation for Shor's factoring algorithm.

Simon的算法比任何经典算法（包括有界误差概率算法）都以指数速度解决黑盒问题。该算法比我们认为有效的所有经典算法都有指数级的加速，是Shor因子分解算法的动机。

Quantum phase estimation algorithm量子相位估计算法

Main article: Quantum phase estimation algorithm
Main article: 量子相位估计算法

Shor's algorithm solves the discrete logarithm problem and the integer factorization problem in polynomial time, whereas the best known classical algorithms take super-polynomial time. These problems are not known to be in P or NP-complete. It is also one of the few quantum algorithms that solves a non–black-box problem in polynomial time where the best known classical algorithms run in super-polynomial time.

肖尔的算法在多项式时间内解决离散对数问题和整数分解问题，而最著名的经典算法需要超多项式时间。这些问题不知道是 P 或 NP 完全。它也是为数不多的在多项式时间内解决非黑盒问题的量子算法之一，而最著名的经典算法是在超多项式时间内运行的。


The quantum phase estimation algorithm is used to determine the eigenphase of an eigenvector of a unitary gate given a quantum state proportional to the eigenvector and access to the gate. The algorithm is frequently used as a subroutine in other algorithms.

使用量子相位估计算法来确定给定与本征向量成比例的量子状态和对门的访问的酉门的本征向量的本征相位。该算法常用作其它算法的子程序。

The abelian hidden subgroup problem is a generalization of many problems that can be solved by a quantum computer, such as Simon's problem, solving Pell's equation, testing the principal ideal of a ring R and factoring. There are efficient quantum algorithms known for the Abelian hidden subgroup problem. The more general hidden subgroup problem, where the group isn't necessarily abelian, is a generalization of the previously mentioned problems and graph isomorphism and certain lattice problems. Efficient quantum algorithms are known for certain non-abelian groups. However, no efficient algorithms are known for the symmetric group, which would give an efficient algorithm for graph isomorphism and the dihedral group, which would solve certain lattice problems.

阿贝尔隐子群问题是许多量子计算机可以解决的问题的推广，如西蒙问题、解佩尔方程、检验环 r 的主理想和因数分解。已知的阿贝尔隐子群问题有一些有效的量子算法。更一般的隐子群问题，其中群不一定是交换的，是前面提到的问题、图同构和某些格问题的推广。有效的量子算法是已知的某些非阿贝尔群。然而对于对称群，目前还没有一种有效的算法，这种算法可以给出图同构和二面体群的有效算法，从而解决某些格问题。

Shor's algorithm肖尔算法

Main article: Shor's algorithm
Main article: Shor算法


Shor's algorithm solves the discrete logarithm problem and the integer factorization problem in polynomial time,

Shor的算法在多项式时间内解决了离散对数问题和整数分解问题，[9] whereas the best known classical algorithms take super-polynomial time. These problems are not known to be in P or NP-complete. It is also one of the few quantum algorithms that solves a non–black-box problem in polynomial time where the best known classical algorithms run in super-polynomial time.

而最著名的经典算法需要超多项式时间。这些问题在 P或NP 完全中是未知的。它也是少数在多项式时间内解决非黑盒问题的量子算法之一，其中最著名的经典算法在超多项式时间内运行。

[math]\displaystyle{ | \tilde{f}(z_i) | \geqslant 2. }[/math]

2. </math > | tilde { f }(z _ i) | geqlant2

Hidden subgroup problem隐子群问题

This can be done in bounded-error quantum polynomial time (BQP).

这可以在有界误差量子多项式时间(BQP)内完成。

The abelian hidden subgroup problem is a generalization of many problems that can be solved by a quantum computer, such as Simon's problem, solving Pell's equation, testing the principal ideal of a ring R and factoring. There are efficient quantum algorithms known for the Abelian hidden subgroup problem.

阿贝尔群 Abelian隐子群问题hidden subgroup problem是量子计算机可以解决的许多问题的推广，例如西蒙Simon问题，求解Pell方程，测试 环ringR的主理想principal ideal和 Factoriang。阿贝尔隐子群问题有许多有效的量子算法。[10]

The more general hidden subgroup problem, where the group isn't necessarily abelian, is a generalization of the previously mentioned problems and graph isomorphism and certain lattice problems. Efficient quantum algorithms are known for certain non-abelian groups. However, no efficient algorithms are known for the symmetric group, which would give an efficient algorithm for graph isomorphism[11]

更一般的隐藏子群问题，其中群不一定是阿贝尔的，是前面提到的问题和图同构以及某些格问题的推广。对于某些非阿贝尔群，有效的量子算法是众所周知的。然而，symmetric group没有有效的算法，这将为图同构提供一个有效的算法[12] and the dihedral group, which would solve certain lattice problems.[13]

以及二面体群，它将解决某些晶格问题。[14]

The triangle-finding problem is the problem of determining whether a given graph contains a triangle (a clique of size 3). The best-known lower bound for quantum algorithms is Ω(N), but the best algorithm known requires O(N1.297) queries, an improvement over the previous best O(N1.3) queries.

三角形发现问题是确定一个给定的图是否包含一个三角形(一个大小为3的团)的问题。量子算法最著名的下界是 Ω(N) ，但是已知最好的算法需要O(N1.297)查询，这是对以前最好的 O(N1.3)查询的改进。

Boson sampling problem玻色子取样问题

Main article: Boson sampling

模板:主

A formula is a tree with a gate at each internal node and an input bit at each leaf node. The problem is to evaluate the formula, which is the output of the root node, given oracle access to the input.

公式是一棵树，在每个内部节点上有一个门，在每个叶节点上有一个输入位。问题是在给定对输入的预言访问权限的情况下，计算公式，即根节点的输出。

The Boson Sampling Problem in an experimental configuration assumes[15] an input of bosons (ex. photons of light) of moderate number getting randomly scattered into a large number of output modes constrained by a defined unitarity. The problem is then to produce a fair sample of the probability distribution of the output which is dependent on the input arrangement of bosons and the Unitarity.[16] Solving this problem with a classical computer algorithm requires computing the permanent of the unitary transform matrix, which may be either impossible or take a prohibitively long time. In 2014, it was proposed[17] that existing technology and standard probabilistic methods of generating single photon states could be used as input into a suitable quantum computable linear optical network and that sampling of the output probability distribution would be demonstrably superior using quantum algorithms. In 2015, investigation predicted[18] the sampling problem had similar complexity for inputs other than Fock state photons and identified a transition in computational complexity from classically simulatable to just as hard as the Boson Sampling Problem, dependent on the size of coherent amplitude inputs.

实验配置中的玻色子取样问题假定[19]中等数量的玻色子s（例如光子）的输入，被随机散射成由定义的单位性约束的大量输出模式。然后问题是产生一个输出的概率分布的公平样本，这个样本依赖于玻色子的输入排列和幺正性。[20]用经典的计算机算法解决这个问题需要计算酉变换矩阵的（mathematics）| Permanent，这可能是不可能的，也可能需要很长的时间。2014年提出[21]现有的产生单光子态的技术和标准概率方法可以作为一个合适的量子可计算线性光学网络的输入，而使用量子算法对输出概率分布进行采样显然更为优越。2015年，调查预测[22]对于Fock态光子以外的输入，采样问题具有类似的复杂性，并且确定了计算复杂性从经典可模拟到与玻色子采样问题一样困难的转变，这取决于相干振幅输入的大小。

A well studied formula is the balanced binary tree with only NAND gates. This type of formula requires Θ(Nc) queries using randomness, where [math]\displaystyle{ c = \log_2(1+\sqrt{33})/4 \approx 0.754 }[/math]. With a quantum algorithm however, it can be solved in Θ(N0.5) queries. No better quantum algorithm for this case was known until one was found for the unconventional Hamiltonian oracle model.

一个经过深入研究的公式是只有 NAND 门的平衡二叉搜索树。这种类型的公式需要使用随机性的 θ (n < sup > c )查询，其中 < math > c = log _ 2(1 + sqrt {33})/4大约0.754 </math > 。然而，量子算法可以在 θ (n < sup > 0.5 )查询中求解。没有更好的量子算法来处理这种情况，直到非常规的哈密顿预言模型被发现。

Estimating Gauss sums估计高斯和

A Gauss sum is a type of exponential sum. The best known classical algorithm for estimating these sums takes exponential time. Since the discrete logarithm problem reduces to Gauss sum estimation, an efficient classical algorithm for estimating Gauss sums would imply an efficient classical algorithm for computing discrete logarithms, which is considered unlikely. However, quantum computers can estimate Gauss sums to polynomial precision in polynomial time.

高斯和是指数和的一种。最著名的经典算法估计这些总和需要指数时间。由于离散对数问题归结为高斯和估计，一个有效的经典算法估计高斯和将意味着一个有效的经典算法计算离散对数，这被认为是不可能的。然而，量子计算机可以在多项式时间内精确地估计高斯和。[23]


A problem is BQP-complete if it is in BQP and any problem in BQP can be reduced to it in polynomial time. Informally, the class of BQP-complete problems are those that are as hard as the hardest problems in BQP and are themselves efficiently solvable by a quantum computer (with bounded error).

在 BQP 中的问题是 BQP 完全问题，BQP 中的任何问题都可以在多项式时间内化为 BQP 完全问题。非正式地，这类 BQP 完全问题是那些在 BQP 中和最困难的问题一样困难的问题，并且它们本身可以由量子计算机有效地解决(有界误差)。

Fourier fishing and Fourier checking傅立叶钓鱼与傅立叶检验

We have an oracle consisting of n random Boolean functions mapping n-bit strings to a Boolean value. We are required to find n n-bit strings z1,..., zn such that for the Hadamard-Fourier transform, at least 3/4 of the strings satisfy

我们有一个 Oracle，由n个随机布尔函数组成，将n位字符串映射到一个布尔值。我们需要找到n个n位字符串z1，…，zn，这样对于Hadamard-Fourier变换，至少有3/4的字符串满足

[math]\displaystyle{ | \tilde{f}(z_i)| \geqslant 1 }[/math]


and at least 1/4 satisfies

并且至少有1/4满足

[math]\displaystyle{ | \tilde{f}(z_i) | \geqslant 2. }[/math]

Witten had shown that the Chern-Simons topological quantum field theory (TQFT) can be solved in terms of Jones polynomials. A quantum computer can simulate a TQFT, and thereby approximate the Jones polynomial, which as far as we know, is hard to compute classically in the worst-case scenario.

威滕已经证明了切恩-西蒙斯拓扑量子场论(TQFT)可以用琼斯多项式来求解。量子计算机可以模拟一个 TQFT，从而近似琼斯多项式，据我们所知，这是难以计算的经典在绝境求生手册。

The idea that quantum computers might be more powerful than classical computers originated in Richard Feynman's observation that classical computers seem to require exponential time to simulate many-particle quantum systems. Since then, the idea that quantum computers can simulate quantum physical processes exponentially faster than classical computers has been greatly fleshed out and elaborated. Efficient (that is, polynomial-time) quantum algorithms have been developed for simulating both Bosonic and Fermionic systems and in particular, the simulation of chemical reactions beyond the capabilities of current classical supercomputers requires only a few hundred qubits. Quantum computers can also efficiently simulate topological quantum field theories. In addition to its intrinsic interest, this result has led to efficient quantum algorithms for estimating quantum topological invariants such as Jones and HOMFLY polynomials, and the Turaev-Viro invariant of three-dimensional manifolds.

量子计算机可能比经典计算机更强大的想法起源于 Richard Feynman 的观察，即经典计算机似乎需要 EXPTIME 来模拟多粒子量子系统。从那时起，量子计算机可以比经典计算机以指数级速度模拟量子物理过程的想法得到了充实和阐述。已经开发出高效的(即多项式时间)量子算法，用于模拟玻色子和费米子系统，特别是模拟超出当前经典超级计算机能力的化学反应，只需要几百个量子位。量子计算机还可以有效地模拟拓扑量子场理论。这个结果除了具有内在的意义外，还导致了估计诸如 Jones 和 HOMFLY 多项式等量子拓扑不变量以及三维流形的 Turaev-Viro 不变量的有效量子算法。

This can be done in bounded-error quantum polynomial time (BQP). 这可以在有界误差量子多项式时间（BQP）内完成。[24]

Algorithms based on amplitude amplification基于幅度放大的算法

The quantum approximate optimization algorithm is a toy model of quantum annealing which can be used to solve problems in graph theory. The algorithm makes use of classical optimization of quantum operations to maximize an objective function.

量子近似优化算法是一个量子退火的玩具模型，可以用来解决图论中的问题。该算法利用量子运算的经典优化来最大化目标函数。

Amplitude amplification is a technique that allows the amplification of a chosen subspace of a quantum state. Applications of amplitude amplification usually lead to quadratic speedups over the corresponding classical algorithms. It can be considered to be a generalization of Grover's algorithm.

振幅放大是一种允许放大量子态的选定子空间的技术。与相应的经典算法相比，振幅放大的应用通常会导致二次加速。这可以看作是Grover算法的推广。

Grover's algorithm格罗弗算法

The VQE algorithm applies classical optimization to minimize the energy expectation of an ansatz state to find the ground state energy of a molecule. This can also be extended to find excited energies of molecules.

VQE 算法采用经典优化方法使假设态的能量期望最小化，以求得分子的基态能量。这也可以扩展到发现分子的激发能。

Main article: Grover's algorithm
Main article: Grover算法

Grover's algorithm searches an unstructured database (or an unordered list) with N entries, for a marked entry, using only [math]\displaystyle{ O(\sqrt{N}) }[/math] queries instead of the [math]\displaystyle{ O({N}) }[/math] queries required classically.[25] Classically, [math]\displaystyle{ O({N}) }[/math] queries are required even allowing bounded-error probabilistic algorithms.

Grover的算法只使用[math]\displaystyle{ O（\sqrt{N}） }[/math]查询而不是经典要求的[math]\displaystyle{ O（{N}） }[/math]查询来搜索具有N个条目的非结构化数据库（或无序列表）中的标记条目。传统上，即使允许有界错误概率算法，也需要[math]\displaystyle{ O（{N}） }[/math]查询。


Theorists have considered a hypothetical generalization of a standard quantum computer that could access the histories of the hidden variables in Bohmian mechanics. (Such a computer is completely hypothetical and would not be a standard quantum computer, or even possible under the standard theory of quantum mechanics.) Such a hypothetical computer could implement a search of an N-item database at most in [math]\displaystyle{ O(\sqrt[3]{N}) }[/math] steps. This is slightly faster than the [math]\displaystyle{ O(\sqrt{N}) }[/math] steps taken by Grover's algorithm. Neither search method would allow either model of quantum computer to solve NP-complete problems in polynomial time.[26]

理论家们考虑了一个标准量子计算机的假设推广，它可以访问玻姆力学中隐藏变量的历史。（这样一台计算机完全是假设的，而且“不是”一台标准的量子计算机，甚至在量子力学的标准理论下也是可能的）这样一台假设的计算机最多可以在[math]\displaystyle{ O（\sqrt[3]{N}） }[/math]步中实现对N项数据库的搜索。这比Grover's algorithm采用的[math]\displaystyle{ O（\sqrt{N}） }[/math]步骤稍微快一点。这两种搜索方法都不允许任何一种量子计算机模型在多项式时间内求解 NP完全问题。[27]

Quantum counting量子计数

Quantum counting solves a generalization of the search problem. It solves the problem of counting the number of marked entries in an unordered list, instead of just detecting if one exists. Specifically, it counts the number of marked entries in an [math]\displaystyle{ N }[/math]-element list, with error [math]\displaystyle{ \varepsilon }[/math] making only [math]\displaystyle{ \Theta\left(\frac{1}{\varepsilon} \sqrt{\frac{N}{k}}\right) }[/math] queries, where [math]\displaystyle{ k }[/math] is the number of marked elements in the list.

量子计数解决了搜索问题的一般化。它解决了计算无序列表中标记条目数的问题，而不是仅仅检测是否存在。具体地说，它统计[math]\displaystyle{ N }[/math]-元素列表中标记的条目数，错误[math]\displaystyle{ \varepsilon }[/math]只生成[math]\displaystyle{ \Theta\left(\frac{1}{\varepsilon} \sqrt{\frac{N}{k}}\right) }[/math]查询，其中[math]\displaystyle{ k }[/math]是列表中标记的元素数。[28]<ref>

{{Cite book 

|last1=Brassard |first1=G.

Category:Quantum computing

类别: 量子计算 

|last2=Hoyer |first2=P.

Category:Quantum information science

类别: 量子信息科学 

|last3=Mosca |first3=M.

Category:Theoretical computer science

类别: 理论计算机科学 

|last4=Tapp |first4=A.

|year=2002

Category:Emerging technologies

类别: 新兴技术


This page was moved from wikipedia:en:Quantum algorithm. Its edit history can be viewed at 量子算法/edithistory

此页摘自维基百科：英文：量子算法。其编辑历史记录可在编辑历史记录查阅

  1. ↑ Nielsen, Michael A.; Chuang, Isaac L. (2000). Quantum Computation and Quantum Information. Cambridge University Press. ISBN 978-0-521-63503-5. 
  2. ↑ Mosca, M. (2008). "Quantum Algorithms". arXiv:0808.0369 [quant-ph].
  3. ↑ Lanzagorta, Marco; Uhlmann, Jeffrey K. (2009-01-01). Quantum Computer Science. Morgan & Claypool Publishers. ISBN 9781598297324. https://books.google.com/books?id=-wkJIuw0YRsC&pg=PA23&lpg=PA23&dq=quantum%2520computer%2520equivalent%2520classical%2520computer#v=onepage. 
  4. ↑ Nielsen, Michael A.; Chuang, Isaac L. (2010). Quantum Computation and Quantum Information (2nd ed.). Cambridge: Cambridge University Press. ISBN 978-1-107-00217-3. https://books.google.com/books?id=-s4DEy7o-a0C. 
  5. ↑ https://quantum-computing.ibm.com/docs/iqx/guide/shors-algorithm
  6. ↑ {{cite arXiv Quantum algorithms are usually described, in the commonly used circuit model of quantum computation, by a quantum circuit which acts on some input qubits and terminates with a measurement. A quantum circuit consists of simple quantum gates which act on at most a fixed number of qubits. The number of qubits has to be fixed because a changing number of qubits implies non-unitary evolution. Quantum algorithms may also be stated in other models of quantum computation, such as the Hamiltonian oracle model. 在常用的量子计算电路模型中，量子算法通常由一个量子电路来描述，量子电路作用于某些输入量子位，并以测量结束。量子电路由简单的量子门组成，量子门最多作用于固定数量的量子位。量子位的数目必须是固定的，因为量子位数目的改变意味着非幺正演化。量子算法也可以用在其他量子计算模型中，比如哈密顿预言模型。 | last1 = Farhi | first1 = E. | last2 = Goldstone |first2=J. Quantum algorithms can be categorized by the main techniques used by the algorithm. Some commonly used techniques/ideas in quantum algorithms include phase kick-back, phase estimation, the quantum Fourier transform, quantum walks, amplitude amplification and topological quantum field theory. Quantum algorithms may also be grouped by the type of problem solved, for instance see the survey on quantum algorithms for algebraic problems. 量子算法可以按照算法使用的主要技术进行分类。一些在量子算法中常用的技术/想法包括相位反冲、相位估计、量子傅里叶变换、量子行走、振幅放大和拓扑量子场论。量子算法也可以按照解决问题的类型进行分组，例如参见代数问题中量子算法的调查。 | last3 = Gutmann |first3=S. | date = 2007 | title = A Quantum Algorithm for the Hamiltonian NAND Tree The quantum Fourier transform is the quantum analogue of the discrete Fourier transform, and is used in several quantum algorithms. The Hadamard transform is also an example of a quantum Fourier transform over an n-dimensional vector space over the field F2. The quantum Fourier transform can be efficiently implemented on a quantum computer using only a polynomial number of quantum gates. 量子傅里叶变换是离散傅里叶变换的量子相似物，被用于几个量子算法中。阿达马变换也是 f < sub > 2 域上 n 维向量空间上的量子傅里叶变换的一个例子。量子傅里叶变换可以在量子计算机上有效地实现，只需要使用多项式数量的量子门。 | eprint = quant-ph/0702144 }}
  7. ↑ Childs, Andrew M.; van Dam, W. (2010). "Quantum algorithms for algebraic problems". Reviews of Modern Physics. 82 (1): 1–52. arXiv:0812.0380. Bibcode:2010RvMP...82....1C. doi:10.1103/RevModPhys.82.1. S2CID 119261679.
  8. ↑ Childs, Andrew M.; van Dam, W. (2010). "Quantum algorithms for algebraic problems". Reviews of Modern Physics. 82 (1): 1–52. arXiv:0812.0380. Bibcode:2010RvMP...82....1C. doi:10.1103/RevModPhys.82.1. S2CID 119261679.
  9. ↑ The Boson Sampling Problem in an experimental configuration assumes an input of bosons (ex. photons of light) of moderate number getting randomly scattered into a large number of output modes constrained by a defined unitarity. The problem is then to produce a fair sample of the probability distribution of the output which is dependent on the input arrangement of bosons and the Unitarity. Solving this problem with a classical computer algorithm requires computing the permanent of the unitary transform matrix, which may be either impossible or take a prohibitively long time. In 2014, it was proposed that existing technology and standard probabilistic methods of generating single photon states could be used as input into a suitable quantum computable linear optical network and that sampling of the output probability distribution would be demonstrably superior using quantum algorithms. In 2015, investigation predicted the sampling problem had similar complexity for inputs other than Fock state photons and identified a transition in computational complexity from classically simulatable to just as hard as the Boson Sampling Problem, dependent on the size of coherent amplitude inputs. 实验结构中的玻色子抽样问题假设输入玻色子(例如:。中等数量的光子，被随机散射到大量的输出模式中，这些模式受到定义的幺正性的约束。然后，问题是产生一个依赖于玻色子的输入排列和幺正性的输出概率分布的公平样本。用经典的计算机算法求解这个问题需要计算酉变换矩阵的永久性，这可能是不可能的，也可能需要很长的时间。在2014年，有人提出，现有的技术和标准的概率方法产生单光子态可以用作输入到一个合适的量子可计算线性光学网络，输出概率分布的采样将被证明优于使用量子算法。在2015年，调查预测采样问题具有类似的复杂性输入而不是福克态光子，并确定了计算复杂性的转变，从经典的模拟到一样困难的玻色子采样问题，取决于相干振幅输入的大小。 Shor, P. W. (1997 A Gauss sum is a type of exponential sum. The best known classical algorithm for estimating these sums takes exponential time. Since the discrete logarithm problem reduces to Gauss sum estimation, an efficient classical algorithm for estimating Gauss sums would imply an efficient classical algorithm for computing discrete logarithms, which is considered unlikely. However, quantum computers can estimate Gauss sums to polynomial precision in polynomial time. 高斯和是指数和的一种类型。最著名的估算这些总和的经典算法需要6个 EXPTIME。由于离散对数问题归结为高斯和估计，一个有效的估计高斯和的经典算法将意味着一个有效的经典算法计算离散对数，这被认为是不可能的。然而，量子计算机可以在多项式时间内估计高斯和到多项式精度。). "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer". SIAM Journal on Scientific and Statistical Computing. 26 (5 We have an oracle consisting of n random Boolean functions mapping n-bit strings to a Boolean value. We are required to find n n-bit strings z1, ..., zn such that for the Hadamard-Fourier transform, at least 3/4 of the strings satisfy 我们有一个由 n 个随机布尔函数组成的预言,它们将 n 位字符串映射到一个布尔值。我们需要找到 n 位字符串 z 1 ,... ,z < sub > n ,使得对于 Hadamard-Fourier 变换,至少有3/4的字符串满足): 1484–1509. arXiv:[//arxiv.org/abs/quant-ph/9508027 [math]\displaystyle{ | \tilde{f}(z_i)| \geqslant 1 }[/math] [ math > quant-ph/9508027 '"`UNIQ--math-0000004D-QINU`"' [ math >]. Bibcode:1995quant.ph..8027S. doi:[//doi.org/10.1137%2Fs0097539795293172%0A%0Aand%20at%20least%201%2F4%20satisfies%0A%0A%E8%87%B3%E5%B0%91%E6%9C%891%2F4%E7%9A%84%E4%BA%BA%E6%BB%A1%E6%84%8F 10.1137/s0097539795293172 and at least 1/4 satisfies 至少有1/4的人满意]. S2CID 2337707. {{cite journal}}: Check |arxiv= value (help); Check |doi= value (help); Check date values in: |year= (help); Text "geqslant 1 </math >" ignored (help); Text "tilde { f }(z _ i)" ignored (help); line feed character in |arxiv= at position 17 (help); line feed character in |doi= at position 26 (help); line feed character in |issue= at position 2 (help); line feed character in |year= at position 5 (help)
  10. ↑ Boneh, D.; Lipton, R. J. Amplitude amplification is a technique that allows the amplification of a chosen subspace of a quantum state. Applications of amplitude amplification usually lead to quadratic speedups over the corresponding classical algorithms. It can be considered to be a generalization of Grover's algorithm. 振幅放大是一种允许放大选定的量子态子空间的技术。应用振幅放大通常导致二次加速比相应的经典算法。它可以被认为是 Grover 算法的推广。 (1995). Coppersmith, D. (ed.). Quantum cryptoanalysis of hidden linear functions. Springer-Verlag. pp. 424–437 Grover's algorithm searches an unstructured database (or an unordered list) with N entries, for a marked entry, using only [math]\displaystyle{ O(\sqrt{N}) }[/math] queries instead of the [math]\displaystyle{ O({N}) }[/math] queries required classically. Classically, [math]\displaystyle{ O({N}) }[/math] queries are required even allowing bounded-error probabilistic algorithms. Grover 的算法只使用 < math > o (sqrt { n }) </math > 查询,而不使用经典要求的 < math > o ({ n }) </math > 查询,在带有 n 个条目的非结构化数据库(或无序列表)中搜索标记条目。传统上,甚至允许有界错误的概率算法也需要查询。. ISBN [[Special:BookSources/3-540-60221-6 Theorists have considered a hypothetical generalization of a standard quantum computer that could access the histories of the hidden variables in Bohmian mechanics. (Such a computer is completely hypothetical and would not be a standard quantum computer, or even possible under the standard theory of quantum mechanics.) Such a hypothetical computer could implement a search of an N-item database at most in [math]\displaystyle{ O(\sqrt[3]{N}) }[/math] steps. This is slightly faster than the [math]\displaystyle{ O(\sqrt{N}) }[/math] steps taken by Grover's algorithm. Neither search method would allow either model of quantum computer to solve NP-complete problems in polynomial time. 理论家们考虑了一种标准量子计算机的假设推广，这种计算机可以访问 Bohmian 力学中隐变量的历史。(这样的计算机完全是假设的，不会是标准的量子计算机，甚至不可能是量子力学的标准理论。)这样一台假设的计算机最多只能在 < math > o (sqrt [3]{ n }) </math > 步骤中实现对 n 项数据库的搜索。这比 Grover 的算法采取的 < math > o (sqrt { n }) </math > 步骤稍快。两种搜索方法都不允许任何一种量子计算机模型在多项式时间内解决 NP 完全问题。|3-540-60221-6 Theorists have considered a hypothetical generalization of a standard quantum computer that could access the histories of the hidden variables in Bohmian mechanics. (Such a computer is completely hypothetical and would not be a standard quantum computer, or even possible under the standard theory of quantum mechanics.) Such a hypothetical computer could implement a search of an N-item database at most in '"`UNIQ--math-00000052-QINU`"' steps. This is slightly faster than the '"`UNIQ--math-00000053-QINU`"' steps taken by Grover's algorithm. Neither search method would allow either model of quantum computer to solve NP-complete problems in polynomial time. 理论家们考虑了一种标准量子计算机的假设推广，这种计算机可以访问 Bohmian 力学中隐变量的历史。(这样的计算机完全是假设的，不会是标准的量子计算机，甚至不可能是量子力学的标准理论。)这样一台假设的计算机最多只能在 < math > o (sqrt [3]{ n }) </math > 步骤中实现对 n 项数据库的搜索。这比 Grover 的算法采取的 < math > o (sqrt { n }) </math > 步骤稍快。两种搜索方法都不允许任何一种量子计算机模型在多项式时间内解决 NP 完全问题。]]. {{cite conference}}: Check |isbn= value: invalid character (help); Unknown parameter |booktitle= ignored (help); line feed character in |first2= at position 6 (help); line feed character in |isbn= at position 14 (help); line feed character in |pages= at position 8 (help)
  11. ↑ A bot will complete this citation soon. Click here to jump the queue arXiv:[1].
  12. ↑ A bot will complete this citation soon. Click here to jump the queue arXiv:[2].右) </math > 查询，其中 < math > k </math > 是列表中标记的元素的数量。更准确地说，算法输出 < math > k’ </math > 的估计值，即被标记的条目数，具有以下精确度: < math > | k-k’ | leq varepsilon k </math > 。 |last3=Schulman |first3=L. J. |year=2005 |title=The Symmetric Group Defies Strong Fourier Sampling: Part I |eprint=quant-ph/0501056 }}
  13. ↑ A bot will complete this citation soon. Click here to jump the queue arXiv:[3].
  14. ↑ {{cite arXiv A quantum walk is the quantum analogue of a classical random walk, which can be described by a probability distribution over some states. A quantum walk can be described by a quantum superposition over states. Quantum walks are known to give exponential speedups for some black-box problems. They also provide polynomial speedups for many problems. A framework for the creation of quantum walk algorithms exists and is quite a versatile tool. Yaoyun Shi first proved a tight lower bound when the size of the range is sufficiently large. Ambainis and Kutin independently (and via different proofs) extended his work to obtain the lower bound for all functions. 量子游走是经典随机游走的量子模拟，它可以用概率分布描述某些状态。量子行走可以用态叠加原理描述。众所周知，量子行走可以为某些黑盒问题提供指数加速。它们还为许多问题提供了多项式加速。创建量子行走算法的框架已经存在，并且是一个相当通用的工具。当范围大小为足够大时，《耀云诗》首次证明了一个紧下界。Ambainis 和 Kutin 独立地(通过不同的证明)推广了他的工作，得到了所有函数的下界。 | last = Regev | first = O. | date = 2003 | title = Quantum Computation and Lattice Problems | eprint = cs/0304005 }}
  15. ↑ Ralph, T.C. "Figure 1: The boson-sampling problem". Nature Photonics. Nature. Retrieved 12 September 2014.
  16. ↑ Lund, A.P.; Laing, A.; Rahimi-Keshari, S.; Rudolph, T.; O'Brien, J.L.; Ralph, T.C. (September 5, 2014). "Boson Sampling from Gaussian States". Phys. Rev. Lett. 113 (10): 100502. arXiv:1305.4346. Bibcode:2014PhRvL.113j0502L. doi:10.1103/PhysRevLett.113.100502. PMID 25238340. S2CID 27742471.
  17. ↑ "The quantum revolution is a step closer". Phys.org. Omicron Technology Limited. Retrieved 12 September 2014.
  18. ↑ Seshadreesan, Kaushik P.; Olson, Jonathan P.; Motes, Keith R.; Rohde, Peter P.; Dowling, Jonathan P. (2015). "Boson sampling with displaced single-photon Fock states versus single-photon-added coherent states: The quantum-classical divide and computational-complexity transitions in linear optics". Physical Review A. 91 (2): 022334. arXiv:1402.0531. Bibcode:2015PhRvA..91b2334S. doi:10.1103/PhysRevA.91.022334. S2CID 55455992.
  19. ↑ Ralph, T.C. "Figure 1: The boson-sampling problem". Nature Photonics. Nature. Retrieved 12 September 2014.
  20. ↑ Lund, A.P.; Laing, A.; Rahimi-Keshari, S.; Rudolph, T.; O'Brien, J.L.; Ralph, T.C. (September 5, 2014). "Boson Sampling from Gaussian States". Phys. Rev. Lett. 113 (10): 100502. arXiv:1305.4346. Bibcode:2014PhRvL.113j0502L. doi:10.1103/PhysRevLett.113.100502. PMID 25238340. S2CID 27742471.
  21. ↑ "The quantum revolution is a step closer". Phys.org. Omicron Technology Limited. Retrieved 12 September 2014.
  22. ↑ Seshadreesan, Kaushik P.; Olson, Jonathan P.; Motes, Keith R.; Rohde, Peter P.; Dowling, Jonathan P. (2015). "Boson sampling with displaced single-photon Fock states versus single-photon-added coherent states: The quantum-classical divide and computational-complexity transitions in linear optics". Physical Review A. 91 (2): 022334. arXiv:1402.0531. Bibcode:2015PhRvA..91b2334S. doi:10.1103/PhysRevA.91.022334. S2CID 55455992.
  23. ↑ Fast quantum algorithms for more complicated formulas are also known. 快速量子算法的更复杂的公式也是众所周知的。 van Dam, W.; Seroussi, G. The problem is to determine if a black box group, given by k generators, is commutative. A black box group is a group with an oracle function, which must be used to perform the group operations (multiplication, inversion, and comparison with identity). We are interested in the query complexity, which is the number of oracle calls needed to solve the problem. The deterministic and randomized query complexities are [math]\displaystyle{ \Theta(k^2) }[/math] and [math]\displaystyle{ \Theta(k) }[/math] respectively. A quantum algorithm requires [math]\displaystyle{ \Omega(k^{2/3}) }[/math] queries but the best known algorithm uses [math]\displaystyle{ O(k^{2/3} \log k) }[/math] queries. 问题是确定一个由 k 个生成元给出的黑盒子群是否是可交换的。黑盒子组是具有 oracle 函数的组，必须使用 oracle 函数来执行组操作(乘法、反转和与单位的比较)。我们感兴趣的是查询复杂度，这是解决问题所需的 oracle 调用的数量。确定性和随机化查询复杂度分别为 < math > Theta (k ^ 2) </math > 和 < math > Theta (k) </math > 。量子算法需要 < math > Omega (k ^ {2/3}) </math > 查询，但是最著名的算法使用 < math > o (k ^ {2/3} log k) </math > 查询。 (2002). "Efficient Quantum Algorithms for Estimating Gauss Sums". arXiv:[//arxiv.org/abs/quant-ph/0207131 The complexity class BQP (bounded-error quantum polynomial time) is the set of decision problems solvable by a quantum computer in polynomial time with error probability of at most 1/3 for all instances. It is the quantum analogue to the classical complexity class BPP. 复杂度类 BQP (有界误差量子多项式时间)是由量子计算机在多项式时间内解决的决策问题的集合，所有实例的误差概率最多为1/3。它是经典复杂性类 BPP 的量子类似物。 quant-ph/0207131 The complexity class BQP (bounded-error quantum polynomial time) is the set of decision problems solvable by a quantum computer in polynomial time with error probability of at most 1/3 for all instances. It is the quantum analogue to the classical complexity class BPP. 复杂度类 BQP (有界误差量子多项式时间)是由量子计算机在多项式时间内解决的决策问题的集合，所有实例的误差概率最多为1/3。它是经典复杂性类 BPP 的量子类似物。]. {{cite arxiv}}: |arxiv= required (help); Check |arxiv= value (help); line feed character in |eprint= at position 17 (help); line feed character in |first2= at position 3 (help)
  24. ↑ {{Cite arXiv In 2009 Aram Harrow, Avinatan Hassidim, and Seth Lloyd, formulated a quantum algorithm for solving linear systems. The algorithm estimates the result of a scalar measurement on the solution vector to a given linear system of equations. 2009年，Aram Harrow，Avinatan Hassidim，和 Seth Lloyd 制定了一个求解线性系统的量子算法。该算法估计一个给定线性方程组的解向量的标量测量结果。 | last = Aaronson | first = S. | year = 2009 Provided the linear system is a sparse and has a low condition number [math]\displaystyle{ \kappa }[/math], and that the user is interested in the result of a scalar measurement on the solution vector, instead of the values of the solution vector itself, then the algorithm has a runtime of [math]\displaystyle{ O(\log(N)\kappa^2) }[/math], where [math]\displaystyle{ N }[/math] is the number of variables in the linear system. This offers an exponential speedup over the fastest classical algorithm, which runs in [math]\displaystyle{ O(N\kappa) }[/math] (or [math]\displaystyle{ O(N\sqrt{\kappa}) }[/math] for positive semidefinite matrices). 如果线性系统是稀疏的，并且条件数很低，而且用户对解向量的标量测量结果感兴趣，而不是解向量本身的值，那么算法有一个运行时为 < math > o (log (n) kappa ^ 2) </math > ，其中 < math > n </math > 是线性系统中的变量数。这比最快的经典算法提供了一个指数级的加速，该算法运行在 < math > o (n kappa) </math > (或 < math > o (n sqrt { kappa) </math > 为正半定矩阵)中。 | title = BQP and the Polynomial Hierarchy | class = quant-ph | eprint = 0910.4698 Hybrid Quantum/Classical Algorithms combine quantum state preparation and measurement with classical optimization. These algorithms generally aim to determine the ground state eigenvector and eigenvalue of a Hermitian Operator. 量子/经典混合算法将量子态的准备和测量与经典优化相结合。这些算法通常旨在确定厄米算子的基态特征向量和特征值。 }}
  25. ↑ Grover, Lov K. (1996). "A fast quantum mechanical algorithm for database search". arXiv:quant-ph/9605043.
  26. ↑ Aaronson, Scott. "Quantum Computing and Hidden Variables" (PDF).
  27. ↑ Aaronson, Scott. "Quantum Computing and Hidden Variables" (PDF).
  28. ↑ Brassard, G.; Hoyer, P.; Tapp, A. (1998). Quantum Counting. Lecture Notes in Computer Science. 1443. pp. 820–831. arXiv:quant-ph/9805082. doi:10.1007/BFb0055105. ISBN 978-3-540-64781-2. 
取自“https://wiki.swarma.org/index.php?title=量子算法&oldid=21369”