Quantum supremacy: some fundamental concepts

• 来源期刊: 国家科学评论（英文版）
• 年，卷（期）: 2019,（1）
• 页码范围: 22-23
• 页数: 2页
• 语种: 英文
• DOI: 10.1093/nsr/nwy072

摘要

Quantum computation was envisioned by Feynman as a valuable means of solving quantum problems [1].The question is,how do we prove the superiority of quantum computing over classical devices? A common misconception in describing the power of a quantum computer over a classical computer is that quantum bits can be prepared in a superposition of an exponential number of states,which cannot be achieved with classical bits.This statement is certainly true,but it does not tell us,specifically,what problems quantum computers can efficiently solve while classical computers fail to do so.In fact,based exactly on the technique of Feynman's path integral,the output (i.e.transition amplitude) of any quantum circuit can be calculated classically with a polynomial amount of memory (although the temporal cost would be exponential).Therefore any quantum computation can be simulated classically;the key question is about the efficiency.