1981年，在麻省理工学院召开的第一届计算物理会议上，诺贝尔奖获得者、加州理工学院教授理查德·费曼提出利用量子效应对量子系统行为进行模拟的想法，这是量子计算的概念首次被提出。1982年，《International Journal of Theoretical Physics》出版了费曼在该次会议上作的题为“Simulating physics with computers”[1]的主旨报告。
1994年，数学家彼得·肖尔在理论计算机顶级会议FOCS上提出一种可以在量子计算机上实现的量子算法[2]，该算法可以在多项式时间内解决大整数分解问题，这使得基于经典计算复杂性理论的现代密码学算法（如RSA）变得不再安全。同时，由于该算法的提出，使人们看到量子计算机的巨大应用前景，从而开启了量子计算机的研究热潮。
与传统计算机类似，实现量子计算机也需要从“硬件”与“软件”两个方向共同努力。在“硬件”方面，主要围绕固态量子计算（如：超导、量子点）和基于量子光学的量子计算（如：离子阱）两类物理实现系统开展研究，在“软件”方面，重点围绕量子算法设计和量子程序语言设计开展研究。这些研究工作涉及计算机科学、电子科学、数学、物理学等多个学科的交叉与融合。
一、两类量子计算机
量子计算机主要分为通用量子计算机（也称为标准量子计算机）和专用量子计算机。通用量子计算机通过量子纠缠、量子干涉、量子叠加等量子态实现计算，例如，Google于2018年3月发布的72量子比特的量子计算机Bristlecone；专用量子计算机则是通过其他理论或模型实现计算（如，量子退火理论等），例如，D-Wave公司的发布的各型量子计算机，该公司于2018年发布的量子计算机已具有高达2000个量子位。
在介绍通用量子计算机的研究难点之前，先介绍一下与量子计算相关的量子态的概念。量子叠加是指量子比特可以处于0和1的叠加态（注意经典计算机每比特只能为0或者1），即一个量子比特能够同时包含0和1的信息。因此，对叠加的量子比特进行操作，便能够同时完成对0和1的操作。这样随着量子比特数量的增长，量子叠加能表示的信息将呈指数增长，n个量子比特能同时包含2^n个数的信息，对这n个量子比特的运算便能够同时完成对2^n个数的运算。量子纠缠是指在计算过程中量子比特之间会产生相关性，其中一个量子比特的状态不能独立于其他量子比特状态来单独进行描述。量子相干性指系统处于量子叠加的能力。
量子计算机实现其非常规计算能力的前提是要保持量子相干性，因此，需要让其与环境尽可能隔离，而计算所需的操控与测量导致无法实现真正的隔离；此外，当前量子门寿命很短，操作错误率很高，这些都是通用量子计算硬件实现中的挑战。
专用量子计算机虽然已经做到上千个量子位，但由于其应用领域非常有限，因此，一直以来都饱受质疑。
二、关于量子霸权
美国国家科学基金委的Dmitri Maslov等2018年10月在IEEE最权威的综述期刊《Proceedings of the IEEE》发表的文章 “An Outlook for Quantum Computing [Point of View]”对量子计算机的性能空间做了总结与展望。
下图1中绿色部分代表着截止论文发表时（2018年9月）可用的量子计算系统，这些系统的性能非常有限，并且能够被经典计算机模拟。蓝色虚线粗略的划分了能够通过经典计算机模拟和不能通过经典计算机模拟的量子计算系统。紫色部分代表了量子霸权，它的定义是只能使用更加先进的量子计算机完成的任务，无论其实用性如何，这些任务都不能被经典计算机模拟。所以，量子霸权其实是指要找到一些任务，这些任务可能不具有实际价值，但是能够通过实验证明量子计算机真的可用。虽然量子霸权的边界仍未确定，但是预计这样的实验中所需的量子比特数(≳50)、量子门误差概率(≲1E-3) 和相干时间（≳1E3门操作时间）。图中其他不同的形状代表解决不同问题的资源需求。
图 1 量子计算机的性能空间
近期谷歌宣称世界排名第一的超级计算机Summit需要计算1万年，而使用谷歌量子计算机只需3分20秒的实验，无疑证明了量子霸权。虽然不确定Google撤稿的原因，但只要这个实验证明正确且可行，那么无疑将成为量子计算机发展的重要里程碑。
[1]Feynman, Richard P. "Simulating physics with computers." International Journal of Theoretical Physics21.6-7(1982):467-488.
[2]Shor, P. "Algorithms for Quantum Computation: Discrete Logarithms and Factoring." Proceedings of 35th Annual Symposium on Foundations of Computer Scienece. 1994.
[3]Maslov, Dmitri, Y. Nam, and J. Kim. "An Outlook for Quantum Computing [Point of View]." Proceedings of the IEEE107.1(2018):5-10.
