561
个编辑
更改
跳到导航
跳到搜索
第349行：
第349行： − − 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，从而近似琼斯多项式，据我们所知，这是难以计算的经典在绝境求生手册。 第362行：
第358行： − 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 不变量的有效量子算法。+ + + − :<math>| \tilde{f}(z_i) | \geqslant 2.</math>+ − −
→Fourier fishing and Fourier checking傅立叶钓鱼与傅立叶检验
我们有一个[[Oracle machine | Oracle]]，由n个随机布尔函数组成，将n位字符串映射到一个布尔值。我们需要找到n个n位字符串z<sub>1</sub>，…，z<sub>n</sub>，这样对于Hadamard-Fourier变换，至少有3/4的字符串满足
我们有一个[[Oracle machine | Oracle]]，由n个随机布尔函数组成，将n位字符串映射到一个布尔值。我们需要找到n个n位字符串z<sub>1</sub>，…，z<sub>n</sub>，这样对于Hadamard-Fourier变换，至少有3/4的字符串满足
:<math>| \tilde{f}(z_i)| \geqslant 1</math>
:<math>| \tilde{f}(z_i)| \geqslant 1</math>
并且至少有1/4满足
并且至少有1/4满足
:<math>| \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 [[BQP|bounded-error quantum polynomial time]] (BQP).
This can be done in [[BQP|bounded-error quantum polynomial time]] (BQP).