561
个编辑
更改
跳到导航
跳到搜索
第214行：
第214行： − + 第244行：
第244行： − + − + − + + + + + 第268行：
第272行： − + + + 第286行：
第292行： − +
→Hidden subgroup problem隐子群问题
The [[Abelian group|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 (mathematics)|ring]] R and [[integer factorization|factoring]]. There are efficient quantum algorithms known for the Abelian hidden subgroup problem.
The [[Abelian group|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 (mathematics)|ring]] R and [[integer factorization|factoring]]. There are efficient quantum algorithms known for the Abelian hidden subgroup problem.
阿贝尔群[[Abelian群| Abelian]]隐子群问题[[hidden subgroup problem]]是量子计算机可以解决的许多问题的推广，例如西蒙Simon问题，求解[[Pell方程]]，测试[[环ring（mathematics）| ring]]R的[[主理想principal ideal]]和[[整数分解integer Factoriation | Factoriang]]。阿贝尔隐子群问题有许多有效的量子算法。<ref>{{cite conference
阿贝尔群[[Abelian群| Abelian]]隐子群问题[[hidden subgroup problem]]是量子计算机可以解决的许多问题的推广，例如西蒙Simon问题，求解[[Pell方程]]，测试[[ring（mathematics）| 环ring]]R的[[主理想principal ideal]]和[[整数分解integer Factoriation | Factoriang]]。阿贝尔隐子群问题有许多有效的量子算法。<ref>{{cite conference
|last1=Boneh |first1=D.
|last1=Boneh |first1=D.
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>O(\sqrt[3]{N})</math> steps. This is slightly faster than the <math>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.
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>O(\sqrt[3]{N})</math> steps. This is slightly faster than the <math>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 完全问题。
理论家们考虑了一种标准量子计算机的假设推广，这种计算机可以访问 Bohmian 力学中隐变量的历史。(这样的计算机完全是假设的，不会是标准的量子计算机，甚至不可能是量子力学的标准理论。)这样一台假设的计算机最多只能在 < math > o (sqrt [3]{ n }) </math > 步骤中实现对 n 项数据库的搜索。这比 Grover 的算法采取的 < math > o (sqrt { n }) </math > 步骤稍快。两种搜索方法都不允许任何一种量子计算机模型在多项式时间内解决 NP 完全问题。
}}</ref> 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<ref>{{cite arXiv
}}</ref>
}}</ref>更一般的隐藏子群问题，其中群不一定是阿贝尔的，是前面提到的问题和[[图同构]]以及某些[[格问题]]的推广。对于某些非阿贝尔群，有效的量子算法是众所周知的。然而，[[symmetric group]]没有有效的算法，这将为图同构提供一个有效的算法<ref>{{cite arXiv
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<ref>{{cite arXiv
}}</ref>
更一般的隐藏子群问题，其中群不一定是阿贝尔的，是前面提到的问题和[[图同构]]以及某些[[格问题]]的推广。对于某些非阿贝尔群，有效的量子算法是众所周知的。然而，[[symmetric group]]没有有效的算法，这将为图同构提供一个有效的算法<ref>{{cite arXiv
|last1=Moore |first1=C.|author1-link=Cris Moore
|last1=Moore |first1=C.|author1-link=Cris Moore
}}</ref> and the [[dihedral group]], which would solve certain lattice problems.<ref>{{cite arXiv
}}</ref> and the [[dihedral group]], which would solve certain lattice problems.<ref>{{cite arXiv
}}</ref>以及[[二面体群]]，它将解决某些晶格问题。<ref>{{cite arXiv
}}</ref>
以及[[二面体群]]，它将解决某些晶格问题。<ref>{{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.
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.
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(N<sup>1.297</sup>) queries, an improvement over the previous best O(N<sup>1.3</sup>) queries.
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(N<sup>1.297</sup>) queries, an improvement over the previous best O(N<sup>1.3</sup>) queries.
三角形发现问题是确定一个给定的图是否包含一个三角形(一个大小为3的团)的问题。量子算法最著名的下界是 ω (n) ，但是已知最好的算法需要 o (n < sup > 1.297 </sup >)查询，这是对以前最好的 o (n < sup > 1.3 </sup >)查询的改进。
三角形发现问题是确定一个给定的图是否包含一个三角形(一个大小为3的团)的问题。量子算法最著名的下界是 Ω(N) ，但是已知最好的算法需要O(N<sup>1.297</sup>)查询，这是对以前最好的 O(N<sup>1.3</sup>)查询的改进。
===Boson sampling problem玻色子取样问题===
===Boson sampling problem玻色子取样问题===