Комментарии 42
Выглядит стимпанково)))
Я вот давно почитываю о квантовых компьютерах, но до сих пор не могу полностью осознать вот этот момент с битом в суперпозиции. Кто-то может простым языком объяснить как вообще происходит вычисление с битами в суперпозиции? Сколько ни пытался, не могу понять, как это работает. Вот я хочу на квантовом компьютере сложить 100 + 25, что будут делать кубиты с этим?
Ну ваш пример с суммой конечно тут не особо подходит, но я так понимаю это как если сначала вы свяжите алгортимически определенные кубиты, потом введете данные и просто снимите результат, который и будет суммой. На сколько я понимаю суперприрост достигается на опрпделенных задачах с определенными алгоритмами
Почитайте мануал к IBM quantum experience. Там достаточно подробно рассказывают про принципы вычисления с помощью кубитов + песочница.
https://quantumexperience.ng.bluemix.net/qx/tutorial?sectionId=b03bd3750e9b05822d31f4d9ffb097ba&pageIndex=0
https://quantumexperience.ng.bluemix.net/qx/tutorial?sectionId=b03bd3750e9b05822d31f4d9ffb097ba&pageIndex=0
В сложении и нет никакой выгоды.
Выгода появляется там, где начинаются существенно квантовые операции. Например, представьте себе единичный вектор размерности 2^n (n — разрядность квантового регистра), и что Вы одной операцией способны повернуть его.
Согласитесь, что при разрядности 49 (вектор в 100 триллионноразмерном пространстве) от затеи уже начинает ощущаться определённый профит?
Выгода появляется там, где начинаются существенно квантовые операции. Например, представьте себе единичный вектор размерности 2^n (n — разрядность квантового регистра), и что Вы одной операцией способны повернуть его.
Согласитесь, что при разрядности 49 (вектор в 100 триллионноразмерном пространстве) от затеи уже начинает ощущаться определённый профит?
Я, признаться, матчасть так и на осилил, но если в двух слова, упрощенно и на языке научпопа «для домохозяек», то я понял это так (пусть меня поправят, если я совсем все напутал). Основной шум вокруг КК — изза их способности сильно ускорять вычисления, связанные с перебором вариантов, поиском тех из них, которые дают некий заданный результат.
Грубо говоря, если есть некая y=f(x), обратная от которой имеет несимметричную сложность вычисления (ну скажем, факториал 663! посчитать легко, а вот обратно — уже боль), то классический способ вычисления обратной — сводится к перебору x, последовательному вычислению прямой функции, и сравнению результата прямой с аргументом обратной, и все оптимизации до сих пор сводятся к сокращению области поиска.
И фишка КК в том, что вместо последовательного перебора конкретных значений, на вход квантового вычислителя подается значение, представленное набор битов в суперпозиции, и (ни ноль, ни единица), и искомый результат, и вся система может коллапсировать только одним возможным способом, при котором результат равен искомому.
Ну т.е. надо нам обратный факториал от 24 посчитать. Вместо перебора 1, 2, и тп, просто подаем на вход вычислителя факториала x в суперпозиции и 24 как искомый результат, система коллапсирует, и аргумент коллапсирует в 4.
Повторюсь, конструктивные помидоры от людей «в теме» — принимаются с радостью.
Грубо говоря, если есть некая y=f(x), обратная от которой имеет несимметричную сложность вычисления (ну скажем, факториал 663! посчитать легко, а вот обратно — уже боль), то классический способ вычисления обратной — сводится к перебору x, последовательному вычислению прямой функции, и сравнению результата прямой с аргументом обратной, и все оптимизации до сих пор сводятся к сокращению области поиска.
И фишка КК в том, что вместо последовательного перебора конкретных значений, на вход квантового вычислителя подается значение, представленное набор битов в суперпозиции, и (ни ноль, ни единица), и искомый результат, и вся система может коллапсировать только одним возможным способом, при котором результат равен искомому.
Ну т.е. надо нам обратный факториал от 24 посчитать. Вместо перебора 1, 2, и тп, просто подаем на вход вычислителя факториала x в суперпозиции и 24 как искомый результат, система коллапсирует, и аргумент коллапсирует в 4.
Повторюсь, конструктивные помидоры от людей «в теме» — принимаются с радостью.
Лучшее объяснение принципу квантовых вычислений в теории Мультивселенной. Квантовая машина работает так же как и обычная, но вычисления происходят параллельно во множестве копий Вселенной. В конце результат вычисления доступен в каждой из Вселенных. Вполне логично, ежели разложение корня на множители в общем требует определённого числа операций, то где они будут происходить в квантовой машине?
Дэвид Дойч, залогиньтесь =)
Нет, мне тоже нравится эта идея и объяснение, но вот услышать бы мнение настоящих физиков, хорошо в этом разбирающихся. То есть, как они объяснят получение этого результата? Если вам не нравится объяснение с мультивселенной, то что конкретно происходит в компьютере и как он тогда считает?
Нет, мне тоже нравится эта идея и объяснение, но вот услышать бы мнение настоящих физиков, хорошо в этом разбирающихся. То есть, как они объяснят получение этого результата? Если вам не нравится объяснение с мультивселенной, то что конкретно происходит в компьютере и как он тогда считает?
Я вполне физик. :3 Правда, в процессе образования после перерыва, но… Как именно оно работает вам никто не скажет. Вам покажут формулы, вполне работающие и дающие верный результат. Ибо в квантовой механике много разных интерпретаций, включая и очень экзотические. И общего мнения по ним не приняли. Дэвид Дойч ещё более физик, чем я, и именно его работы легли в основу квантовых вычислений. Многомировая версия квантовой механики наиболее разумная с позиции объяснения. В ней не нужны ни влияние сознания на эксперимент, ни коллапс волновой функции, ни неизмеримые величины, и прочая магия.
В конце результат вычисления доступен в каждой из Вселенных.
Разъясните пожалуйста, потому что в книге этот момент не уточняется или я пропустил.
Именно правильный результат доступен во всех Вселенных или в каждой Вселенной он будет свой, но правильный только в нашей?
Очень подробно разобрано в Дэвид Дойч, «Структура реальности», глава 9. Наша Вселенная ничем не выделена в ряду прочих. Конечно, результат один во всех Вселенных. Объединение результатов вычисления происходит в процессе интерференции. Ровно как и фотоны в интерферометре.
Больше полезной инфы.
http://www.quiprocone.org/Protected/DD_lectures.htm
https://people.eecs.berkeley.edu/~christos/classics/Deutsch_quantum_theory.pdf
http://www.michaelnielsen.org/qcqi
Больше полезной инфы.
http://www.quiprocone.org/Protected/DD_lectures.htm
https://people.eecs.berkeley.edu/~christos/classics/Deutsch_quantum_theory.pdf
http://www.michaelnielsen.org/qcqi
Как вообще сравнивают мощности квантовых и классических компьютеров, если классические компьютеры универсальны, а квантовые заточены под решение крайне узкого круга задач?
обычные компьютеры на заре их эры тоже были заточены под решение крайне узкого круга задач
Ну, если рассматривать не счеты и табуляторы, то вообще-то даже на заре пытались делать более или менее универсальные машины. Машина Тьюринга, как абстрактное вычислительное устройство в сознании пионеров эры компьютеров, вполне универсальна. С квантовыми вычислениями пока подобной универсальности не наблюдается.
НЛО прилетело и опубликовало эту надпись здесь
Разве мог Тьюринг представить (да и собственно предполагать), что через каких то 50 лет машина разработанная им для дешифровки немецкого шифра будет исполнять хотя бы десятую часть из того, что мы сейчас делаем на своих компьютерах?
Лайкаем котиков? Играем в игры? А нормального ИИ нет до сих пор.
Машина Тьюринга — это не Бомба, которая была сделана для шифров.
И чего могут/не могут делать машины он неплохо представлял, как чисто математически (решив «проблему остановки»), так и «в бытовом смысле» (придумав тест имени себя).
Кстати, второй части мы пока что не достигли — нормально тест Тьюринга пока что ни один бот толком не прошел.
И чего могут/не могут делать машины он неплохо представлял, как чисто математически (решив «проблему остановки»), так и «в бытовом смысле» (придумав тест имени себя).
Кстати, второй части мы пока что не достигли — нормально тест Тьюринга пока что ни один бот толком не прошел.
Квантовый компьютер в предельном переходе даёт классический. :) То есть, при желании, Вы можете изобразить машину Тюринга на квантовом компе (хотя и непонятно, нафига это нужно). Обратное — неверно.
…
«Неуниверсальность» появляется лишь потому, что квантовые вычисления НЕВЕРОЯТНО большой гемморой для нашей технологии по сравнению с классическими. Поэтому нет смысла делать на квантовом компе нечто, не требующее существенно квантовых операций.
14нм литографический завод может делать изображения на не хуже, чем любой принтер. Но нет смысла использовать завод для распечатки статьи. Принтер дешевле.
…
«Неуниверсальность» появляется лишь потому, что квантовые вычисления НЕВЕРОЯТНО большой гемморой для нашей технологии по сравнению с классическими. Поэтому нет смысла делать на квантовом компе нечто, не требующее существенно квантовых операций.
14нм литографический завод может делать изображения на не хуже, чем любой принтер. Но нет смысла использовать завод для распечатки статьи. Принтер дешевле.
Обратное тоже верно — квантовые компьютеры отнюдь не супертюринговые.
? Вы не можете эмулировать на машине Тьюринга квантовый компьютер.
Вы не можете исполнить алгоритм Гровера ни на какой классической машине. В принципе.
Вы можете исполнить только классический алгоритм с перебором и притвориться, что «это то же самое, потому что получен тот же результат», что разница только в производительности. Хотя на самом деле — разница в алгоритме.
Вы не можете исполнить алгоритм Гровера ни на какой классической машине. В принципе.
Вы можете исполнить только классический алгоритм с перебором и притвориться, что «это то же самое, потому что получен тот же результат», что разница только в производительности. Хотя на самом деле — разница в алгоритме.
Почему это? Мне всегда казалось, что обычные компьютеры вполне неплохо справляются с линейной алгеброй.
А при чём тут линейная алгебра?
Расскажите мне, пошагово, как будет выглядеть исполнение квантового алгоритма (ну, пусть Гровера, раз уж я взял его для примера) на классической машине (пусть недетерминированной)?
Расскажите мне, пошагово, как будет выглядеть исполнение квантового алгоритма (ну, пусть Гровера, раз уж я взял его для примера) на классической машине (пусть недетерминированной)?
Так же, как и симуляция любой другой конечномерной квантовой системы. Состояния — вектора над комплексными числами. Квантовые гейты — их унитарные преобразования. Выполнение алгоритма — применение унитарных преобразований к векторам (фактически, умножение векторов на матрицы). Если нужно зачем-то просимулировать измерение (например, для постселекции) — умножаем вектор состояния на сопряженный, получаем вероятности и делаем рандомный выбор в соответствии с распределением.
Если хочется посимулировать еще и шум, то делаем то же самое, но над матрицами плотности.
Если хочется посимулировать еще и шум, то делаем то же самое, но над матрицами плотности.
А Вам совсем не видится подставы в том, что сложность (в смысле, O(n)) получившегося у Вас при «симуляции» алгоритма таки очень отличается от O(n) квантового?
Я могу дать Вам алгоритм для КК с линейной сложностью, а Вы при эмуляции на Тьюринге получите экспоненту. И Вы по-прежнему будете считать, что машина Тьюринга эквивалентна КК? Вы только что доказали, что NP=P?
Для обеспечения такой «эквивалентности» Вам придётся выкинуть теорию алгоритмов. Потому что нынешняя теория таких трюков не понимает.
Ну или «просто игнорировать её». Что, конечно, гораздо удобнее.
Я могу дать Вам алгоритм для КК с линейной сложностью, а Вы при эмуляции на Тьюринге получите экспоненту. И Вы по-прежнему будете считать, что машина Тьюринга эквивалентна КК? Вы только что доказали, что NP=P?
Для обеспечения такой «эквивалентности» Вам придётся выкинуть теорию алгоритмов. Потому что нынешняя теория таких трюков не понимает.
Ну или «просто игнорировать её». Что, конечно, гораздо удобнее.
На это существует несколько известных мне точек зрения и никакая из них не опровергает возможность симуляции.
Во-первых, изменение асимптотической сложности алгоритма не имеет никакого отношения к симуляции. Скажем, алгоритм, выполняющийся с логарифмической сложностью на машине с произвольным доступом к памяти может стать полиномиальным на машине с лентой (типа классической машины Тюринга). Верно ли тогда на ваш взгляд утверждение, что обычный компьютер не эквивалентен машине Тюринга? Ведь рост сложности такой же, как при переходе классический-квантовый. Тоже экспоненциальный.
Во-вторых, сложность — вещь асимптотическая и по хорошему, имеет только предельный смысл. Если я сделаю матричный процессор, который будет умножать матрицу размером 2^16 на вектор размером 2^8 за стабильное количество тактов, то он будет полностью эквивалентен восьмикубитному квантовому компьютеру с точки зрения «усеченной» сложности. Более того, он будет наверняка быстрее, потому что обычно GP квантовые компьютеры не могут выполнить произвольный гейт за раз — гейты собираются из элементарных гейтов. А такая машина сможет.
Во-первых, изменение асимптотической сложности алгоритма не имеет никакого отношения к симуляции. Скажем, алгоритм, выполняющийся с логарифмической сложностью на машине с произвольным доступом к памяти может стать полиномиальным на машине с лентой (типа классической машины Тюринга). Верно ли тогда на ваш взгляд утверждение, что обычный компьютер не эквивалентен машине Тюринга? Ведь рост сложности такой же, как при переходе классический-квантовый. Тоже экспоненциальный.
Во-вторых, сложность — вещь асимптотическая и по хорошему, имеет только предельный смысл. Если я сделаю матричный процессор, который будет умножать матрицу размером 2^16 на вектор размером 2^8 за стабильное количество тактов, то он будет полностью эквивалентен восьмикубитному квантовому компьютеру с точки зрения «усеченной» сложности. Более того, он будет наверняка быстрее, потому что обычно GP квантовые компьютеры не могут выполнить произвольный гейт за раз — гейты собираются из элементарных гейтов. А такая машина сможет.
А вас не смущает, что когда квантовый компьютер будет симулировать классический то сложность его алгоритмов будет сильно выше таковой у нативного классического, и по производительности он будет сильно отставать?
НЛО прилетело и опубликовало эту надпись здесь
А как же D-Wave?
А у гугла тоже квантовый отжиг или полноценные кубиты?
Квантовый отжиг будет если и этому проекту финансирование остановят, лол
Полноценные кубиты от команды http://web.physics.ucsb.edu/~martinisgroup/ (John Martinis and his team at UC Santa Barbara will join Google in this initiative — сентябрь 2014).
Публикации: http://web.physics.ucsb.edu/~martinisgroup/publications.shtml
Демонстрация 5 кубитов на чипе: https://arxiv.org/ftp/arxiv/papers/1402/1402.4848.pdf (Nature 508, 500-503 (2014), DOI: 10.1038/nature13171, scholar)
Here, we demonstrate a universal set of logic gates in a superconducting multi-qubit processor, achieving an average single-qubit gate fidelity of 99.92% and a two-qubit gate fidelity up to 99.4%.… five qubits arranged in a linear array with nearest-neighbour coupling. As a further demonstration, we construct a five-qubit Greenberger-Horne-Zeilinger (GHZ) state using the complete circuit and full set of gates. The results demonstrate that Josephson quantum computing is a high-fidelity technology, with a clear path to scaling up to large-scale, fault-tolerant quantum circuits.
Показали 1 и 2-кубитные операции с приемлемой точностью, получили универсальный набор (в основе two-qubit controlled-Z и 24 однокубитных вращения "Clifford"). Успешно собрали 5-кубитное состояние GHZ (FIG. 4).
https://www.aps.org/publications/apsnews/201705/quantum.cfm
John Martinis, one of Google’s quantum computing gurus, laid out the company’s "stretch goal": to build and test a 49-qubit ("quantum bit") quantum computer by the end of this year. This computer will use qubits made of superconducting circuits.… To demonstrate that their 49-qubit quantum computer works, Martinis’s group will first precisely prepare the qubits — embedded on a chip — in an initial quantum state. Then, they will control the qubits using applied potentials and let the states evolve. Finally, they will measure the qubits’ state and compare it to a theoretical simulation of the experiment calculated by a classical supercomputer. If the final state matches their classical simulation, they will have successfully controlled the evolution of the qubits — which means they can perform quantum computations.… his group has already successfully built and tested a 9-qubit version.… Before making the 49-qubit version, they will first scale up to a 20 or 30-qubit computer.
Published last month in Nature, the Google group predicted that industry will commercialize small, specialized quantum computers five years from now. "If we can do something useful and commercially viable, then there will be funding to build up the industry and scale up," Martinis says.
Статья про 9-кубитный — https://arxiv.org/ftp/arxiv/papers/1511/1511.03316.pdf "Digitized adiabatic quantum computing with a superconducting circuit" — Nature 534, 222-226 (2016), DOI: 10.1038/nature17658, https://arxiv.org/abs/1511.03316 (10 Nov 2015):
Devices were made at the UC Santa Barbara Nanofabrication Facility, a part of the NSF-funded National Nanotechnology Infrastructure Network, and at the NanoStructures Cleanroom Facility.
Не совсем так
two-qubit controlled-Z и 24 однокубитных вращения «Clifford»не образуют универсальных набора. Это следует из теоремы Готтесмана-Нилла. Авторы статьи этого и не утверждают. Они эти операции для бенчмарки только используют. Для универсальности к ним надо добавить ещё какое-нибудь однокубитовое вращение.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
К концу этого года Google планирует показать в работе 49-кубитный квантовый компьютер