Solving search problems by strongly simulating quantum circuits.
Solving search problems by strongly simulating quantum circuits.
复制标题
DOI：
10.1038/srep01235
复制
发表时间：
2013
影响因子：
4.6
通讯作者：
Jaksch, D.
中科院分区：
文献类型：
--
作者：
Johnson, T. H.;Biamonte, J. D.;Clark, S. R.;Jaksch, D.
使用经典计算机模拟量子电路可以让我们分析量子算法的内部工作原理。最完整的模拟类型，即强模拟，通常被认为是低效的。然而，几个有效的强模拟技术是已知的量子电路的限制家庭，我们在这篇文章中开发了一个额外的技术。此外，我们还证明了强模拟算法执行另一项基本任务：解决搜索问题。有效的强模拟技术允许解决一类搜索问题的计数和有效地找到。这增强了强模拟方法的实用性，已知的或尚未发现的，并扩展了已知的有效模拟的搜索问题的类别。将强模拟与搜索问题联系起来也限制了有效强模拟电路的计算能力;如果它们可以解决P中的所有问题，这意味着NP和#P中的所有问题都可以在多项式时间内解决。
Simulating quantum circuits using classical computers lets us analyse the inner workings of quantum algorithms. The most complete type of simulation, strong simulation, is believed to be generally inefficient. Nevertheless, several efficient strong simulation techniques are known for restricted families of quantum circuits and we develop an additional technique in this article. Further, we show that strong simulation algorithms perform another fundamental task: solving search problems. Efficient strong simulation techniques allow solutions to a class of search problems to be counted and found efficiently. This enhances the utility of strong simulation methods, known or yet to be discovered, and extends the class of search problems known to be efficiently simulable. Relating strong simulation to search problems also bounds the computational power of efficiently strongly simulable circuits; if they could solve all problems in P this would imply that all problems in NP and #P could be solved in polynomial time.
登录
查看更多内容
影响因子：
2.9
作者：
Aaronson, S;Gottesman, D
通讯作者：
Gottesman, D
影响因子：
1.5
作者：
DiVincenzo, DP;Terhal, BM
通讯作者：
Terhal, BM
影响因子：
2.4
作者：
Johnson, T. H.;Clark, S. R.;Jaksch, D.
通讯作者：
Jaksch, D.
DOI：
10.1098/rspa.2002.1097
发表时间：
2003-08-08
影响因子：
3.5
作者：
Jozsa, R;Linden, N
通讯作者：
Linden, N
影响因子：
1.6
作者：
Shor, PW
通讯作者：
Shor, PW