跳至內容

絕熱量子計算機

維基百科,自由的百科全書

絕熱量子計算機 (AQC)是一種量子計算機的形式,依賴絕熱理論英語Adiabatic theorem進行計算[1] 。AQC與量子退火緊密相關,甚至可認為是量子退火的一個子類[2][3][4][5]

描述

[編輯]

首先要找到一個基態能夠描述我們所感興趣的問題的解的哈密頓量(這個量可能是複雜的)。接下來準備一個簡單哈密頓量的系統並將其初始化至基態。最後,將該簡單哈密頓量絕熱演化為我們所求的複雜哈密頓量.。根據絕熱理論,該系統會保持在基態,所以最終該系統所處的狀態將可以描述該問題的解。絕熱量子計算在多項式運算方面展示出了和傳統量子計算一樣的能力[6]

絕熱量子計算的時間複雜度是指完成絕熱演算所需的時間,與哈密頓量的本徵能隙(譜隙)有關。具體地說,如果系統處於基態,基態與第一激發態之間的能隙提給出了演化速度的上界[7]當譜隙很小時,演化速度也會很慢。 整個算法的運行時間可以被約束為:

這裏代表的最小頻譜距 。

AQC是一個可能解決量子耗散問題的方法。由於系統處於基態,外界的干涉無法使它向更低的能態移動。如果外界的能量低於基態和第一激發態的能量差,系統躍遷的高能態的可能性將相應的更低。 因此,系統可以依據需求長時間處於單系統本徵態。

普遍來講,在絕熱模型中的結果依賴於量子複雜性和QMA-問題。如果k≥2, k-local的哈密頓量是QMA完備的[8] QMA難度的結果已知於量子比特的現實晶格模型[9]

代表泡利矩陣.這種模型被用於通用絕熱量子計算。QMA-完備問題的哈密頓量也可以被限制作用在量子比特的兩維網格上[10]或一條每個有12種狀態的量子顆粒上。[11]如果這種模型被證明是物理可行的,它們也可以用來構建通用絕熱量子計算機的基礎。

在實際計算中仍存在一些問題。因為哈密頓量是逐漸變化,當多個 量子比特接近一個臨界點時會產生一些有趣的現象。臨界點是指當基態能量很接近第一激發態時。這時,只需要添加少量的能量(來自外界環境或是由於哈密頓量的改變)就能使系統脫離基態從而破壞計算。試圖加快計算速度會增加外部能量;改變量子比特的數量會使臨界點處能隙變小。

絕熱量子計算的可滿足性問題

[編輯]
已隱藏部分未翻譯內容,歡迎參與翻譯

Adiabatic quantum computation solves satisfiability problems and other combinatorial search problems by the process below. Generally this kind of problem is to seek for a state that satisfies . This expression contains the satisfiability of M clauses, each clause has the value True or False, and can involve n bits. Each bit here is a variable so is a Boolean value function of . QAA solves this kind of problem using quantum adiabatic evolution. It starts with an Initial Hamiltonian :

where shows the Hamiltonian corresponding to the clause , usually the choice of won't depend on different clauses, so only the total number of times each bit involved in all clauses matters. Then it goes through an adiabatic evolution, ending in the Problem Hamiltonian :

where is the satisfying Hamiltonian of clause C. It has eigenvalues:

For a simple path of Adiabatic Evolution with running time T, consider: and let , we have: , which is the adiabatic evolution Hamiltonian of our algorithm.

According to the adiabatic theorem, we start from the ground state of Hamiltonian at beginning, go through an adiabatic process, and at last ending in the ground state of problem Hamiltonian . Then we measure the z-component of each of the n spins in the final state, this will produce a string which is highly likely to be the result of our satisfiability problem. Here the running time T must be sufficiently long to assure the correctness of result, and according to adiabatic theorem, T is about , where is the minimum energy gap between ground state and first excited state.[12]

D-波量子處理器

[編輯]

The D-Wave One is a device made by a Canadian company D-Wave Systems which describes it as doing quantum annealing.[13] In 2011, Lockheed-Martin purchased one for about US$10 million; in May 2013, Google purchased a D-Wave Two with 512 qubits.[14] As of now, the question of whether the D-Wave processors offer a speedup over a classical processor is still unanswered. Tests performed by researchers at Quantum Artificial Intelligence Lab (NASA), USC, ETH Zurich, and Google show that as of now, there is no evidence of a quantum advantage. [15][16][17]

參考

[編輯]
  1. ^ Farhi, E.; Goldstone, Jeffrey; Gutmann, S.; Sipser, M. Quantum Computation by Adiabatic Evolution. 2000. arXiv:quant-ph/0001106v1可免費查閱. 
  2. ^ Kadowaki, T.; Nishimori, H. Quantum annealing in the transverse Ising model. Physical Review E. 1998-11-01, 58 (5): 5355. Bibcode:1998PhRvE..58.5355K. arXiv:cond-mat/9804280可免費查閱. doi:10.1103/PhysRevE.58.5355. 
  3. ^ Finilla, A.B.; Gomez, M.A.; Sebenik, C.; Doll, D.J. Quantum annealing: A new method for minimizing multidimensional functions. Chemical Physics Letters. 1994-03-18, 219 (5): 343–348. Bibcode:1994CPL...219..343F. arXiv:chem-ph/9404003可免費查閱. doi:10.1016/0009-2614(94)00117-0. 
  4. ^ Santoro, G.E.; Tosatti, E. Optimization using quantum mechanics: quantum annealing through adiabatic evolution. Journal of Physics A. 2006-09-08, 39 (36): R393. Bibcode:2006JPhA...39R.393S. doi:10.1088/0305-4470/39/36/R01. 
  5. ^ Das, A.; Chakrabarti, B.K. Colloquium: Quantum annealing and analog quantum computation. Reviews of Modern Physics. 2008-09-05, 80 (3): 1061. Bibcode:2008RvMP...80.1061D. arXiv:0801.2193可免費查閱. doi:10.1103/RevModPhys.80.1061. 
  6. ^ Aharonov, Dorit; van Dam, Wim; Kempe, Julia; Landau, Zeph; LLoyd, Seth. Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation. SIAM Journal on Computing. 2007-04-01, 37: 166. arXiv:quant-ph/0405098可免費查閱. doi:10.1137/s0097539705447323. 
  7. ^ van Dam, Wim; van Mosca, Michele; Vazirani, Umesh. How Powerful is Adiabatic Quantum Computation?. Proceedings of the 42nd Annual Symposium on Foundations of Computer Science: 279. 
  8. ^ Kempe, J.; Kitaev, A.; Regev, O. The Complexity of the Local Hamiltonian Problem. SIAM Journal on Computing. 2006-07-27, 35 (5): 1070–1097. ISSN 1095-7111. arXiv:quant-ph/0406180v2可免費查閱. doi:10.1137/S0097539704445226. 
  9. ^ Biamonte, J.D.; Love, P.J. Realizable Hamiltonians for Universal Adiabatic Quantum Computers. Physical Review A. 2008-07-28, 78 (1): 012352. Bibcode:2008PhRvA..78a2352B. arXiv:0704.1287可免費查閱. doi:10.1103/PhysRevA.78.012352. 
  10. ^ Oliveira, R.; Terhal, B.M. The complexity of quantum spin systems on a two-dimensional square lattice. Quantum Information & Computation. 2008-11-01, 8: 0900–0924. Bibcode:2005quant.ph..4050O. arXiv:quant-ph/0504050可免費查閱. 
  11. ^ Aharonov, D.; Gottesman, D.; Irani, S.; Kempe, J. The Power of Quantum Systems on a Line. Communications in Mathematical Physics. 2009-04-01, 287 (1): 41–65. Bibcode:2009CMaPh.287...41A. arXiv:0705.4077可免費查閱. doi:10.1007/s00220-008-0710-3. 
  12. ^ Farhi. Quantum Computation by Adiabatic Evolution. arXiv:quant-ph/0001106可免費查閱. 
  13. ^ Quantum Computing: How D-Wave Systems Work. D-Wave. D-Wave Systems, Inc. [2014-08-28]. (原始內容存檔於2014-09-14). 
  14. ^ Jones, Nicola. Computing: The quantum company. Nature. 2013-06-20, 498 (7454): 286–288 [2014-01-02]. Bibcode:2013Natur.498..286J. PMID 23783610. doi:10.1038/498286a. (原始內容存檔於2014-01-03). 
  15. ^ Boixo, S.; Rønnow, T.F.; Isakov, S.V.; Wang, Z.; Wecker, D.; Lidar, D.A.; Martinis, J.M.; Troyer, M. Evidence for quantum annealing with more than one hundred qubits. Nature Physics. 2014-02-28, 10 (3): 218–224. Bibcode:2014NatPh..10..218B. arXiv:1304.4595可免費查閱. doi:10.1038/nphys2900. 
  16. ^ Ronnow, T.F.; Wang, Z.; Job, J.; Boixo, S.; Isakov, S.V.; Wecker, D.; Martinis, J.M.; Lidar, D.A.; Troyer, M. Defining and detecting quantum speedup. Science. 2014-07-25, 345 (6195): 420–424. Bibcode:2014Sci...345..420R. PMID 25061205. arXiv:1401.2910可免費查閱. doi:10.1126/science.1252319. 
  17. ^ Venturelli, D.; Mandrà, S.; Knysh, S.; O'Gorman, B.; Biswas, R.; Smelyanskiy, V. Quantum Optimization of Fully Connected Spin Glasses. Physical Review X. 2015-09-18, 5 (3): 031040. Bibcode:2015PhRvX...5c1040V. arXiv:1406.7553可免費查閱. doi:10.1103/PhysRevX.5.031040.