Quantum annealing

Введение

Квантовое отжигание (QA) - это процесс оптимизации для поиска глобального минимума данной объективной функции над данным набором возможных решений (состояний) путем процесса, использующего квантовые флуктуации. Квантовое отжигание используется в основном для задач, где пространство поиска дискретно (комбинаторные задачи оптимизации) с множеством локальных минимумов; например, для поиска основания состояния спин-стекла или проблемы странствующего продавца. Термин "квантовое отжигание" впервые был предложен в 1988 году Б. Аполлони, Н. Цеза Бианки и Д. Де Фалько как квантово вдохновленный классический алгоритм. В своем нынешнем виде она была сформулирована Т. Кадоваки и Х. Нисимори (ja) в 1998 году, хотя вариант воображаемого времени без квантовой когерентности был обсужден А. B. Finnila, M. A. Гомес, C. Себеник и J. D. Долл в 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 о его производительности. 25 мая 2011 года D Wave объявила, что Lockheed Martin Corporation заключила соглашение о покупке системы D Wave One. 28 октября 2011 года Институт информационных наук USC принял D Wave One от Lockheed. В мае 2013 года было объявлено, что консорциум Google, NASA Ames и некоммерческой Ассоциации исследований космических университетов приобрел адьябатический квантовый компьютер от D Wave Systems с 512 кубитами. Обширное исследование его эффективности в качестве квантового отжигателя, по сравнению с некоторыми классическими алгоритмами отжига, уже доступно. В июне 2014 года D Wave объявила о создании новой экосистемы квантовых приложений с вычислительной финансовой фирмой 1QB Information Technologies (1QBit) и исследовательской группой рака DNA SEQ, чтобы сосредоточиться на решении реальных проблем с помощью квантового оборудования. Как первая компания, занимающаяся производством программных приложений для коммерчески доступных квантовых компьютеров, исследования и разработка 1QBit были сосредоточены на процессорах квантового отжига D Wave и успешно продемонстрировали, что эти процессоры подходят для решения реальных приложений. После публикации демонстраций запутанности, вопрос о том, может ли машина D Wave продемонстрировать квантовое ускорение по сравнению со всеми классическими компьютерами, остается без ответа. Исследование, опубликованное в журнале Science в июне 2014 года, описывается как "вероятно, самое тщательное и точное исследование, которое было сделано по производительности машины D Wave" и "самое справедливое сравнение до сих пор", попыталось определить и измерить квантовое ускорение. Было выдвинуто несколько определений, поскольку некоторые из них могут быть непроверены эмпирическими тестами, в то время как другие, хотя и фальсифицированы, тем не менее, позволяют существование преимуществ производительности. Исследование показало, что чип D Wave "не производит квантового ускорения" и не исключает возможности в будущих тестах. Исследователи, возглавляемые Маттиасом Тройером из Швейцарского федерального технологического института, не обнаружили "никакого квантового ускорения" во всем диапазоне своих тестов, и только неубедительные результаты при рассмотрении подмножеств тестов. Их работа проиллюстрировала "неочевидную природу вопроса о квантовом ускорении". Дальнейшая работа позволила лучше понять эти тестовые метрики и их зависимость от сбалансированных систем, тем самым упустив любые признаки преимущества из-за квантовой динамики. Есть много открытых вопросов относительно квантового ускорения. Ссылка на ETH в предыдущем разделе относится только к одному классу задач по сравнению. Потенциально могут быть другие классы проблем, где может произойти квантовое ускорение. Исследователи из Google, LANL, USC, Texas A&M и D Wave работают над поиском таких проблемных классов. В декабре 2015 года Google объявил, что D Wave 2X превосходит как моделируемое отжигание, так и квантовое Монте-Карло до 100 000 000 в наборе сложных задач оптимизации. Архитектура D Wave отличается от традиционных квантовых компьютеров. Не известно, что он полиномиально эквивалентен универсальному квантовому компьютеру, и, в частности, не может выполнять алгоритм Шора, потому что алгоритм Шора не является процессом восхождения на холм. Алгоритм Шора требует универсального квантового компьютера. Во время конференции Qubits 2021, проведенной D Wave, было объявлено, что компания разрабатывает свои первые универсальные квантовые компьютеры, способные запускать алгоритм Шора в дополнение к другим алгоритмам модели ворот, таким как QAOA и VQE. "Междисциплинарное введение в алгоритмы квантового отжига" представляет собой введение в комбинаторные оптимизационные (NP hard) задачи, общую структуру алгоритмов квантового отжига и два примера такого рода алгоритмов для решения экземпляров задач максимума SAT и минимума Multicut, а также обзор систем квантового отжига, изготовленных D Wave Systems. Для иллюстрации квантового преимущества были описаны гибридные квантовые классические алгоритмы для крупномасштабных дискретных непрерывных задач оптимизации.

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.