Quantum annealing

Кіріспе

Кванттық физикаға негізделген оптималдандыру мәселелеріне арналған метагеуристика Кванттық оттепелеу (QA) - кванттық ауытқуларды пайдаланатын процесс арқылы берілген кандидат шешімдердің (кандидат күйлер) жиынтығында берілген объективті функцияның жаһандық минимумын табуға арналған оптималдандыру процесі. Кванттық оттепелеу негізінен іздеу кеңістігі дискретті (комбинациялық оптимизациялау проблемалары) көптеген жергілікті минимумдармен проблемалар үшін қолданылады; мысалы, спин шынысының негізгі жағдайын табу немесе саяхатшы сатушы мәселесі. "Кванттық оттепелеу" термині алғаш рет 1988 жылы Б. Аполлони, Н. Цеза Бианки және Д. Де Фалько кванттық илхам алған классикалық алгоритм ретінде ұсынды. Оны қазіргі түрінде Т. Кадоваки мен Х. Нишимори (ja) 1998 жылы тұжырымдады, бірақ кванттық когеренсіз елестетілген уақыт нұсқасы А. Б. Финнила, М. А. Гомес, С. Себеник және Дж. Д. Долл 1994 жылы. Кванттық оттепелеу барлық мүмкін болатын күйлердің (кандидат күйлердің) тең салмақты кванттық механикалық суперпозициясынан басталады. Содан кейін жүйе физикалық жүйелердің табиғи кванттық механикалық эволюциясына байланысты уақытқа тәуелді Шредингер теңдеуі бойынша дамып келеді. Барлық кандидат мемлекеттердің амплитудасы өзгеріп отырады, кванттық параллелизмді жүзеге асырады, ол көлденең өрістің уақытқа тәуелді күш-қуатына сәйкес, бұл мемлекеттер арасындағы кванттық туннельдеуге немесе шыңдар арқылы туннельдеуге әкеледі. Егер көлденең өрістің өзгеру жылдамдығы жеткілікті баяу болса, жүйе бірденгі гамильтонияның негізгі күйіне жақын болады (сонымен қатар, адиабатикалық кванттық есептеуді қараңыз). Егер көлденең өрістің өзгеру жылдамдығы жеделдетілсе, жүйе негіздік күйден уақытша шыға алады, бірақ соңғы проблеманың негіздік күйінде қорытындылау ықтималдығы жоғары болады. Ақыры көлденең өріс өшіріледі және жүйе бастапқы оңтайландыру мәселесінің шешімін сәйкес келетін классикалық Исинг моделінің негізгі күйіне жетеді деп күтіледі. Кездейсоқ магниттер үшін кванттық оттанудың табысты эксперименттік көрсетілімі бастапқы теориялық ұсыныстан кейін дереу хабарланды. Кванттық оттепелеу көптеген NP толық проблемаларды шешуде квадрат түбірді жылдамдату үшін жылдам Гровер оракулін қамтамасыз ететіндігі дәлелденді.

Quantum physics based metaheuristic for optimization problems

Quantum annealing (QA) is an optimization process for finding the global minimum of a given objective function over a given set of candidate solutions (candidate states), by a process using quantum fluctuations. Quantum annealing is used mainly for problems where the search space is discrete (combinatorial optimization problems) with many local minima; such as finding the ground state of a spin glass or the traveling salesman problem. The term "quantum annealing" was first proposed in 1988 by B. Apolloni, N. Cesa Bianchi and D. De Falco as a quantum inspired classical algorithm. It was formulated in its present form by T. Kadowaki and H. Nishimori (ja) in 1998 though an imaginary time variant without quantum coherence had been discussed by A. B. Finnila, M. A. Gomez, C. Sebenik and J. D. Doll in 1994. Quantum annealing starts from a quantum mechanical superposition of all possible states (candidate states) with equal weights. Then the system evolves following the time dependent Schrödinger equation, a natural quantum mechanical evolution of physical systems. The amplitudes of all candidate states keep changing, realizing a quantum parallelism, according to the time dependent strength of the transverse field, which causes quantum tunneling between states or essentially tunneling through peaks. If the rate of change of the transverse field is slow enough, the system stays close to the ground state of the instantaneous Hamiltonian (also see adiabatic quantum computation). If the rate of change of the transverse field is accelerated, the system may leave the ground state temporarily but produce a higher likelihood of concluding in the ground state of the final problem Hamiltonian, i. e., diabatic quantum computation. The transverse field is finally switched off, and the system is expected to have reached the ground state of the classical Ising model that corresponds to the solution to the original optimization problem. An experimental demonstration of the success of quantum annealing for random magnets was reported immediately after the initial theoretical proposal. Quantum annealing has also been proven to provide a fast Grover oracle for the square root speedup in solving many NP complete problems.

Симуляциялық отқа қосумен салыстыру

Кванттық оттепелеуді симуляциялық оттепелеумен салыстыруға болады, оның "температура" параметрі QA туннельдік өрісінің күшін ұқсас атқарады. Симуляциялық оттануда температура бір ток күйінен жоғары "энергия" күйіне көшу ықтималдығын анықтайды. Кванттық оттепелеуде көлденең өрістің күші барлық күйлердің амплитудасын қатар өзгертуге кванттық механикалық ықтималдығын анықтайды. Аналитикалық және сандық дәлелдер кванттық оттепелеудің белгілі бір жағдайларда симуляциялық оттепелеуден артық екенін көрсетеді (қатаң талдау үшін және кванттық оттепелеудің кездейсоқ мақсатты гамильтониялық және әртүрлі есептеу тәсілдерін салыстыру үшін толық шешімін табуға болатын моделі үшін қараңыз).

D-Wave іске асырулары

2011 жылы D Wave Systems D Wave One деген атпен нарықтағы алғашқы коммерциялық кванттық оттегінің пайда болуын жариялады және оның өнімділігі туралы Nature журналында мақала жариялады. 2011 жылдың 25 мамырында D Wave компаниясы Lockheed Martin корпорациясы D Wave One жүйесін сатып алу туралы келісімге қол қойғандығын жариялады. 2011 жылдың 28 қазанында USC ақпараттық ғылымдар институты Lockheed-тің D Wave One-ін қабылдады. 2013 жылдың мамыр айында Google, NASA Ames және коммерциялық емес университеттер ғарыш зерттеулер қауымдастығының консорциумы 512 кубитпен D Wave Systems-тен адиабатикалық кванттық компьютер сатып алғаны туралы хабарланды. Кейбір классикалық оттепел алгоритмдермен салыстырғанда оның кванттық оттепел ретінде өнімділігін егжей-тегжейлі зерттеу қазірдің өзінде қол жетімді. 2014 жылдың маусым айында D Wave кванттық аппараттық жабдықпен нақты әлемдегі проблемаларды шешуге назар аудару үшін 1QB Information Technologies (1QBit) есептеу қаржы компаниясы және қатерлі ісік зерттеу тобы DNA SEQ-мен бірге жаңа кванттық қосымшалар экожүйесін жариялады. Коммерциялық кванттық компьютерлер үшін бағдарламалық жасақтамаларды шығаруға арналған алғашқы компания ретінде 1QBit-тің ғылыми-зерттеу және әзірлеу бөлімі D Wave-дің кванттық оттану процессорларына назар аударды және бұл процессорлардың нақты әлемдегі қолданбаларды шешу үшін жарамды екенін табысты көрсетті. Жарияланған түйісудің көрсетілімдерімен D Wave машинасы барлық классикалық компьютерлерге қарағанда кванттық жылдамдықты көрсете ала ма, жоқ па деген сұрақ әлі жауапсыз қалды. 2014 жылдың маусым айында "Science" журналында жарияланған зерттеу "D Wave машинасының жұмыс істеуін зерттеудің ең толық және дәл жүргізілгені" және "әлі күнге дейін ең әділ салыстыру" ретінде сипатталды, ол кванттық жылдамдықты анықтауға және өлшеуге тырысты. Бірнеше анықтама берілді, өйткені кейбіреулері эмпирикалық сынақтар арқылы тексерілмеуі мүмкін, ал басқалары, жалған болса да, дегенмен, өнімділік артықшылықтарының болуына мүмкіндік береді. Зерттеу D Wave чипі "кванттық жылдамдықты арттырмағанын" анықтады және болашақ сынақтарда мүмкіндігін жоққа шығармады. Швейцарияның технология институтының Маттиас Тройер бастаған зерттеушілер барлық сынақтардың барысында "кванттық жылдамдықты арттырмаған", тек сынақтардың кіші топтарын қараған кезде ғана нәтижелер анық болған жоқ. Олардың жұмысы "кванттық жылдамдық мәселесінің нәзік сипатын" көрсетті. Қосымша жұмыстар осы тесттік өлшемдерді және олардың теңгерімді жүйелерге тәуелділігін түсінуді жетілдірді, осылайша кванттық динамикаға байланысты артықшылықтардың белгілерін жоғалтты. Кванттық жылдамдыққа қатысты көптеген сұрақтар бар. Алдыңғы бөлімдегі ETH сілтемесі тек бір сыныптағы эталондық проблемаларға арналған. Кванттық жылдамдықты арттыратын басқа да проблемалар болуы мүмкін. Google, LANL, USC, Texas A&M және D Wave зерттеушілері осындай проблемалық кластарды табу үшін жұмыс істейді. 2015 жылдың желтоқсан айында Google D Wave 2X симуляциялық оттепелеу мен Кванттық Монте-Карлоды күрделі оптимизациялық проблемалар жиынтығында 100 000 000 есеге артық орындайтынын мәлімдеді. D Wave архитектурасы дәстүрлі кванттық компьютерлерден ерекшеленеді. Ол универсалды кванттық компьютермен полиномиялық эквивалентті болып табылмайды және әсіресе Шордың алгоритмін орындай алмайды, өйткені Шордың алгоритмі тау-төбеге көтерілу процесі емес. Шордың алгоритміне әмбебап кванттық компьютер қажет. D Wave өткізген Qubits 2021 конференциясы барысында компанияның QAOA және VQE сияқты басқа қақпа модельдерінің алгоритмдеріне қосымша Шор алгоритмін орындай алатын алғашқы әмбебап кванттық компьютерлерін жасап жатқаны мәлім болды. "Кванттық оттегінің алгоритмдеріне жан-жақты кіріспе" комбинаторлық оңтайландыру (NP hard) мәселелеріне кіріспе, кванттық оттегінің алгоритмдерінің жалпы құрылымы және осы түрдегі алгоритмдердің екі мысалы, сонымен бірге D Wave Systems өндіретін кванттық оттегінің жүйелерінің шолуымен бірге, максимум SAT және Минимальді көп қиылысты проблемалардың инстанцияларын шешу үшін. Кванттық артықшылықты көрсету үшін ірі ауқымды дискретті үздіксіз оптимизациялау проблемалары үшін гибридтік кванттық классикалық алгоритмдер туралы хабарланды.

In 2011, D Wave Systems announced the first commercial quantum annealer on the market by the name D Wave One and published a paper in Nature on its performance. On May 25, 2011, D Wave announced that Lockheed Martin Corporation entered into an agreement to purchase a D Wave One system. On October 28, 2011 USC's Information Sciences Institute took delivery of Lockheed's D Wave One. In May 2013 it was announced that a consortium of Google, NASA Ames and the non profit Universities Space Research Association purchased an adiabatic quantum computer from D Wave Systems with 512 qubits. An extensive study of its performance as quantum annealer, compared to some classical annealing algorithms, is already available. In June 2014, D Wave announced a new quantum applications ecosystem with computational finance firm 1QB Information Technologies (1QBit) and cancer research group DNA SEQ to focus on solving real world problems with quantum hardware. As the first company dedicated to producing software applications for commercially available quantum computers, 1QBit's research and development arm has focused on D Wave's quantum annealing processors and has successfully demonstrated that these processors are suitable for solving real world applications. With demonstrations of entanglement published, the question of whether or not the D Wave machine can demonstrate quantum speedup over all classical computers remains unanswered. A study published in Science in June 2014, described as "likely the most thorough and precise study that has been done on the performance of the D Wave machine" and "the fairest comparison yet", attempted to define and measure quantum speedup. Several definitions were put forward as some may be unverifiable by empirical tests, while others, though falsified, would nonetheless allow for the existence of performance advantages. The study found that the D Wave chip "produced no quantum speedup" and did not rule out the possibility in future tests. The researchers, led by Matthias Troyer at the Swiss Federal Institute of Technology, found "no quantum speedup" across the entire range of their tests, and only inconclusive results when looking at subsets of the tests. Their work illustrated "the subtle nature of the quantum speedup question". Further work has advanced understanding of these test metrics and their reliance on equilibrated systems, thereby missing any signatures of advantage due to quantum dynamics. There are many open questions regarding quantum speedup. The ETH reference in the previous section is just for one class of benchmark problems. Potentially there may be other classes of problems where quantum speedup might occur. Researchers at Google, LANL, USC, Texas A&M, and D Wave are working to find such problem classes. In December 2015, Google announced that the D Wave 2X outperforms both simulated annealing and Quantum Monte Carlo by up to a factor of 100,000,000 on a set of hard optimization problems. D Wave's architecture differs from traditional quantum computers. It is not known to be polynomially equivalent to a universal quantum computer and, in particular, cannot execute Shor's algorithm because Shor's algorithm is not a hillclimbing process. Shor's algorithm requires a universal quantum computer. During the Qubits 2021 conference held by D Wave, it was announced that the company is developing their first universal quantum computers, capable of running Shor's algorithm in addition to other gate model algorithms such as QAOA and VQE. "A cross disciplinary introduction to quantum annealing based algorithms" presents an introduction to combinatorial optimization (NP hard) problems, the general structure of quantum annealing based algorithms and two examples of this kind of algorithms for solving instances of the max SAT and Minimum Multicut problems, together with an overview of the quantum annealing systems manufactured by D Wave Systems. Hybrid quantum classic algorithms for large scale discrete continuous optimization problems were reported to illustrate the quantum advantage.