What is the largest separation between quantum and classical query complexity?

• 来源期刊: 科学通报（英文版）
• 年，卷（期）: 2017,（14）
• 页码范围: 980-981
• 页数: 2页
• 语种: 英文

摘要

In the theory of computation,a key question in analyzing the computational complexity of a certain computational problem is how much least physical resource would be needed to solve a computational task [1].Here,the physical sources include time and the storage,in particular,the number of unit gates and processors in a circuit.Some computation problems can be easily solved,such as multiplying two numbers together,meaning that such problems can be solved in a short time and/or with less storage.While some computational problems are hard to solve,such as factorization of a larger number.A problem is regarded as inherently difficult if its solution requires significant resources,no matter what algorithms are used.One of the roles played by the computational complexity theory is to determine the practical limits on what computers can and cannot do.