量子计算机：量子算法与物理实现

摘要/Abstract

摘要：

量子算法与物理实现是量子计算机研究中的两个基本问题。本文首先总结了相关领域的主要进展，并讨论了有代表性的量子算法，特别介绍了用于求解线性方程组的量子算法，分析了影响新量子算法提出的因素。然后，探讨了物理实现的迪文森佐判据，并介绍了典型的实现方案及性能比较。同时，也关注了对量子计算机研究持有异议的观点。最后，对量子计算机的新研究方向作了探讨。

关键词: 量子计算机, 量子算法, 量子比特, 离子阱, 量子随机游走, Majorana费米子, 拓扑量子计算

Abstract:

Quantum algorithms and physical implementations are two basic problems in the research of quantum computers.First,we summarize the major progress in the relative areas,and discuss some representative examples of quantum algorithms,especially the one for solving systems of linear equations.The impact factors on proposing new quantum algorithms are also analyzed.Then,the DiVincenzo criteria are discussed, alone with some typical practical implementations and their performance comparison.Additionally,the viewpoints from the enemy camp about quantum computers are also concerned.Finally,we investigate some new research directions.

Key words: quantum computer;quantum algorithm;quantum bit(qubit);ion well;quantum random walking;Majorana Fermion;topological quantum computer

方粮，刘汝霖，汤振森，隋兵才，池雅庆. 量子计算机：量子算法与物理实现[J]. J4, 2012, 34(8): 32-43.

FANG Liang,LIU Rulin,TANG Zhensen,SUI Bingcai,CHI Yaqing. Quantum Computers: Algorithms and Physical Implementations[J]. J4, 2012, 34(8): 32-43.

参考文献

［1］Feynman P R. Simulating Physics with Computers［J］. International Journal of Theoretical Physics, 1982, 21(6/7):467488.
［2］Deutsch D. Quantum Theory, the ChurchTuring Principle and the Universal Quantum Computer［Z］. 1985:400497.
［3］Shor W P.Algorithms for Quantum Computation: Discrete Logarithms and Factoring［C］∥Proc of the 35th Annual Symposium on Foundations of Computer Science,1994:124134.
［4］Grover K L. A Fast Quantum Mechanical Algorithm for Database Search［C］∥Proc of STOC 1996, 1996:212219.
［5］Harrow A W,Hassidim A, Lloyd S. Quantum Algorithm for Solving Linear Systems of Equations［J］.Physical Review Letters,2009,15(103):150502.
［6］Divincenzo D P.The Physical Implementation of Quantum Computation［J］.Fortschritter der Physik,2000,48:771784.
［7］Cirac J I,Zoller P.Quantum Computations with Cold Trapped IONS［J］.Physical Review Letters,1995,74(20):40914094.
［8］Lloyd S.Universal Quantum Simulators［J］.Science,1996,273(5278):10731078.
［9］Shor W P.Why Haven’t More Quantum Algorithms BEEN Found?［J］.Journal of the ACM,2003,50(1):8790.
［10］DiVincenzo, D P. Quantum Computation with Quantum Dots［J］.Physical Review A,1998,57(1):120126.
［11］Elzerman J M. SingleShot Readout of an Individual Electron Spin in a Quantum Dot［J］.Nature, 2004,430:431435.
［12］Biercuk M J, Garaj S,Mason N,et al. GateDefined Quantum Dots on Carbon Nanotubes［J］. Nano Lett, 2005,5(7):12671271.
［13］Gaudreau L, et al. A Tunable Few Electron Triple Quantum Dot［J］. Applied Physics Letters, 2009,95(19):193101193103.
［14］University of Innsbruck, Institute for Theoretical Physics［EB/OL］.［20111116］.http:∥www.uibk.ac.at/thphysik/qo/research/trappedions.html.
［15］Wineland D J, et al. Experimental Issues in Coherent Quantumstate Manipulation of Trapped Atomic Ions［J］. Journal of Research of the National Institute of Standards and Technology,1998,103(3):259328.
［16］Building AtomPhoton Networks with Trapped Ions［EB/OL］.［20111116］.http:∥www.iontrap.umd.edu/research/ion_photon/index.html.
［17］Tinkham M.Introduction to Superconductivity［M］.2nd ed. McGrawHill, New York, 1996.
［18］Caldeira A O,Leggett A J. Quantum Tunneling in Adissipative System［J］.Ann Phys(N.Y.),1983,149:374456.
［19］Leggett A J, Chakravarty S, Dorsey A T, et al. Dynamics of the Dissipative Twostate System［J］. Reviews of Modern Physics,1987,59:185.
［20］Nielsen M A, Chuang I L. Quantum Computation and Quantum Information［M］. Cambridge University Press, Cambridge, 2000.
［21］Makhlin Y, Schon G, Shnirman A. QuantumState Engineering with JosephsonJunction Devices［J］. Reviews of Modern Physics, 2001,73(2):357400.
［22］Nakamura Y, Pashkin Y A, Tsai J S. Cohevent Control of Macroscopic Quantum States in a SingleCooperPair Box［J］. Nature (London), 1999,398:786788.
［23］Vion D,Aassime A,Cottet A,et al.Manipulating the Quantum State of an Electrical Circuit［J］. Science, 2002, 296:886889.
［24］Friedman J R, Patel V, et al. Quautum Superposition of Distinct Macroscopic States［J］.Nature (London), 2000,406:4346.
［25］Caspar H. van der Wal, Wilhelm F K, et al. Quantum Superposition of Macroscopic PersistentCurrent States［J］. Science, 2000,290:773777.
［26］Chiorescu I, Nakamura Y, Harmans C J P M,et al.Coherent Quantum Dynamics of a Superconducting Flux Qubit［J］. Science, 2003, 299:18691871.
［27］Martinis J,Nam S,Aumentado J,et al.Rabi Oscillations in a Large JosephsonJunction Qubit［J］.Phys Rev Lett, 2002,89(11):11790111179014.
［28］Yu Y,Han S,Chu X,et al.Coherent Temporal Oscillations of Macroscopic Quantum States in a Josephson Junction［J］.Science,2002,296:889892.
［29］Blais A,Huang R S,Wallraff A,et al.Cavity Quantum Electrodynamics for Superconducting Electrical Circuits:An Architecture for Quantum Computation［J］.Phys Rev A, 2004,69(6):114.
［30］Wallraff A,Schuster D I,Blais A,et al.Strong Coupling of a Single Photon to a Superconducting Qubit Using Circuit Quantum Electrodynamics［J］.Nature (London), 2004,431:162167.
［31］Chiorescu I,Bertet P,Semba K,et al. Coherent Dynamics of a Flux Qubit Coupled to a Harmonic Oscillator［J］.Nature (London) ,2004,431:159162.
［32］Johansson J,Saito S,Meno T,et al. Vacuum Rabi Oscillations in a Macroscopic Superconducting Qubit LC Oscillator System［J］.Phys Rev Lett,2006,96(12):127006.
［33］Huang X M H,Zorman C A,Mehregany M,et al.Nanodevice Motion at Microwave Frequencies［J］.Nature (London) ,2003,421(3):496498.
［34］Schriefl J. Dekohrenz in Josephson Quantenbits:［PhD thesis］［D］.Universitat Karlsruhe (TH),2005.
［35］Nakamura Y,Pashkin Y A,Yamamoto T,et al.Charge Echo in a CooperPair Box［J］.Phys Rev Lett,2002,88(4):047901.
［36］Astafiev O, Pashkin Y A, Nakamura Y, et al. Quantum Noise in the Josephson Charge Qubit［J］.Phys Rev Lett,2004,93(26):267007.
［37］Paladino E,Faoro L,Falci G.Decoherence and 1/f Noise in Josephson Qubits［J］.Phys Rev Lett,2002,88(22):228304.
［38］Yoshihara F,Harrabi K,Niskanen A O,et al.Decoherence of Flux Qubits Due to 1/f Flux Noise［J］.Phys Rev Lett,2006,97(16):167001.
［39］Ithier G,Collin E,Joye Z P,et al.Decoherence in a Superconducting Quantum Bit Circuit［J］.Phys Rev B,2005,72(13):134519.
［40］Makhlin Y,Schoen G,Shnirman A.Quantum State Engineering with JosephsonJunction Devices［J］.Reviews of Modern Physics,2001,73(2):357400.
［41］Orlando T P,Mooij J E,Tian L,et al.Superconducting PersistentCurrent Qubit［J］.Phys Rev B, 1999,60(22):1539815413.
［42］Niskanen A O,Harrabi K,et al.Quantum Coherent Tunable Coupling of Superconducting Qubits［J］.Science,2001,316:723726.
［43］Farhi E,Goldstone J,Gutman S.A Quantum Algorithm for the Hamiltonian NAND Tree［J］. Theory of Computing Systems, 2008(4): 169190.
［44］Dyakonov M I.Quantum Computing:A View from the Enemy Camp［J］.Optics and Spectroscopy,2003,95(2):261267.
［45］Haroche S, Raimond J. Quantum Computing: Dream or Nightmare?［J］.Physics Today,1996,49(8):5152.
［46］Brassard G,Hyer P,Mosca M,et al.Quantum Amplitude Amplification and Estimation［M］.Faculty of Mathematics,University of Waterloo,2000.
［47］Berry D W,Ahokas G,Cleve R,et al.Efficient Quantum Algorithms for Simulating Sparse Hamiltonians［J］.Comm Math Phys, 2007, 270:359371.
［48］Childs A M.On the Relationship Between Continuous and DiscreteTime Quantum Walk［J］.Communications in Mathematics Physics, 2010,294:581603.
［49］Luis A, Perina J. Optimum PhaseShift Estimation and the Quantum Description of the Phase Difference［J］. Phys Rev A, 1996,54(5):45644570.
［50］Cleve R, Ekert A, Macchiavello C, et al. Quantum Algorithms Revisited［C］∥Proc of the Royal Society,1997.
［51］Quarter Electrons May Enable Exotic Quantum Computer: Researchers come closer to weaving quantum "braids"［EB/OL］.［20111015］.http:∥www.scientificamerican.com/article.cfm?id=quarterelectronsmayenablequantumcomputer&page=2.
［52］Hsieh D,Xia Y,Qian D,et al.Obervatio of Unconventional Quantum Spin Textures in Toplogical Insulator［J］.Science, 2009,323(5916):919922.

[1]	周旭，谭晓青. 通用的辅助量子计算[J]. 计算机工程与科学, 2017, 39(11): 2000-2005.
[2]	林家逖任德龙田欣刘亮. 经典逻辑门与量子逻辑门之比较[J]. J4, 2005, 27(11): 93-95.
[3]	霍红卫潘征. 大数质因子分解的量子算法[J]. J4, 2003, 25(1): 23-25.