Comments 61
[irony] Возьму константную, срублю сбалансированную, сам сяду и фронтендера посажу. [/irony]
и все-таки, в момент появления оракула сразу возникает вопрос о том, что таки понимается в этом случае под сложностью алгоритма, почему она осталась O(1) и как должна быть задана функция f на вход алгоритму так, чтобы при этом ее вычисление было более затратно нежели сама подача представления этой функции на вход алгоритму?
Ну допустим, прилетели инопланетяне с альфы центавра и сказали: «Вот вам функция. Если она константная, то мы вас уничтожим, если сбалансированная — вам повезло.» И дали чёрный ящик с входом и выходом для пучка электронов. Классическая версия, говорят, тоже есть, но она дома, шлите туда запросы: 5 лет в одну сторону, 5 обратно.

Про возможность построения оракулов — это скорее к физикам. У нас есть прекрасная стройная теория, в которой можно использовать любые необходимые нам объекты классического мира в виде оракулов и мы ей пользуемся, не заботясь особо о практической реализации. Существуют алгоритмы, где оракул можно заранее вычислить на классическом компьютере и уже с его помощью решать гораздо более сложную задачу в квантовой модели.

Возвращаясь к вашему вопросу. С помощью базовых логических квантовых элементов можно построить произвольную булеву функцию. Допустим, у нас есть функция 1010 аргументов. Но мы так же знаем, как без вычислений функции построить её квантовый оракул из логических элементов. Тогда квантовый алгоритм окажется предпочтительным.

Алгоритм Дойча-Йожи — не самый лучший пример решения практически важных задач, однако он крайне интересен с теоретической точки зрения, позволяет показать все возможные преимущества квантового подхода и идеален для первого знакомства с квантовыми вычислениями в силу своей простоты.
«Вот вам функция. Если она константная, то мы вас уничтожим, если сбалансированная — вам повезло.»
Классическая версия, говорят, тоже есть, но она дома, шлите туда запросы: 5 лет в одну сторону, 5 обратно.
Вот, именно при такой постановке задачи, по завету товарища Сухова, стоило бы помучиться с отсылкой запросов классической версии. Вдруг функция сбалансированная?

Спасибо, было интересно, но понять так и не смог. Сдался чуть позже середины. В итоге решил скопипастить код и посмотреть просто посмотреть что будет. Ожидаемо, чуда не случилось. В эмуляторе функция вызывается с полным перебором всех возможных аргументов.

Сначала говорили про «функцию можно вызывать только один раз» — а потом оказалось, что вызовов будет много.
Как только появляется слово «квантовая» — так сразу же начинается всяческая фигня и самозапутывание…
Тут с пассажа про стулья уже было ясно, что автор, тензор ему в глаз, читателя за фронтендерафраера принял :)
Вызовов много лишь при эмуляции: ведь у нас с вами нет квантового компьютера. В самом алгоритме вызов функции один — применение квантового оракула.
В самом алгоритме вызов функции один — применение квантового оракула.


Э-ээ, а разве «вызов» в квантовых вычислениях эквивалентен вызову функции в обычных тьюринговых машинах? Что-то, как я понял — квантовый оракул сразу порождает ответы для всех значений входного вектора.
Ни?
Конечно, «вызов» стоило взять в кавычки. Мы один раз получаем от оракула всю информацию о функции. Но чтобы построить оракул, совсем не обязательно вычислять классическую функцию: он может быть построен из логических элементов, может быть дан свыше, может быть найден в природе и т.д. В настоящем квантовом компьютере мы не будем вычислять и знать матрицу оракула, это будет некоторый физический объект с требуемыми нам свойствами, который переведёт нашу квантовую систему в нужное состояние. А для эмуляции квантовых вычислений, конечно, необходимо вызвать функцию на всех аргументах и построить оракул в явном виде.
а на возникает тут сразу проблема следующего вида: вот дан черный ящик, нам сказали (или нам кажется) что этот ящик это оракул для функции f. как быстро можно проверить что черный ящик — действительно оракул для f и с какой точностью?
Ну, если оракул задан набором логических операторов, то достаточно легко. В любом другом случае, скорее всего, никак. Не стоит относиться к описанному алгоритму как к практически значимому :) У нас ещё квантовых компьютеров всего пара штук на всей Земле, а вы уже возмущаетесь, что мы оракулы строить и верифицировать не умеем…
Тогда и вовсе непонятно.
Операторы/гейты физически это что? Прибор, сигнал, ритуал?
В каком вообще сценарии без инопланетян мы можем получить интересный нам оракул для неизвестной нам функции?

Оракул это просто линейный оператор параметризованный этой функцией.
|x,y>->|x,y + f(x)>.
Как оно реализовано в природе вообще говоря не важно. Говоря языком "фронтендера" оракул это нечто реализуете api указанное выше.
В задаче дойча-йожи да нужен оракул для произвольной функции.


Но есть задачи в которых функция оракула известна заранее, тогда просто реализуют такой оператор, что, вообще говоря, тоже не всегда просто.

Пока все это напоминает историю с аналоговыми компьютерами и холодным термоядерным синтезом. Математики мамой клянутся, что давно просекли тему: пять минут страха, кропаль каких-то ярдов денег и, пацаны, вы в доле, все будет в шоколаде!

Но на практике попытки реализации упираются в очередное дурацкое несовершенство физического мира, с его инерционностями, нелинейностями и тому подобными гадостями. Пока еще ни кто не доказал, что физический квантовый мир обладает всеми нужными свойствами, каким его представляет себе модель КК, и из этой затеи выйдет что-то полезное.
Но чтобы построить оракул, совсем не обязательно вычислять классическую функцию: он может быть построен из логических элементов, может быть дан свыше, может быть найден в природе и т.д.


Квантовый оракул не может быть построен из логических элементов, бо они — не квантовые.
Не подчиняются (на макроуровне) волновому уравнению Шредингера, и не нуждаются в волновой пси-функции для своего описания.

В настоящем квантовом компьютере мы не будем вычислять и знать матрицу оракула, это будет некоторый физический объект с требуемыми нам свойствами, который переведёт нашу квантовую систему в нужное состояние.


Вот смотрите:
— Вы рассматриваете логическую функцию. Для представления её результата достаточно одного бита, в случае квуантовых вычислений — простого кубита с двумя состояниями, к которому применяются соотв. унитарные преобразования для получения результата вычислений.
— квантовый оракул для своего представления требует n (или n+1, мне ломы разбираться, где n — число аргументов) простых кубитов, к которым дважды применяется преобразование Адамара + наша искомая функция.
Но таким образом получается, что реально наша функция вычисляется как минимум n раз — только в параллель.
Но что мешает нам взять ПЛМ-ку сделать то же самое — и причём тут «квантовые вычисления»?
Квантовый оракул не может быть построен из логических элементов, бо они — не квантовые.
Не подчиняются (на макроуровне) волновому уравнению Шредингера, и не нуждаются в волновой пси-функции для своего описания.

Естественно, в контексте квантовых вычислений речь идёт о квантовых логических элементах. Вот например, функция f(x) = x из статьи может быть выражена с помощью одного гейта CNOT:


x


А вот f(x) = ~x:


not x


Аналогично выражается любая логическая функция любого количества переменных. Доказано, что это возможно с помощью универсального гейта Тоффоли:


toffoli


Но таким образом получается, что реально наша функция вычисляется как минимум n раз — только в параллель.

Нет, не получается.


Но что мешает нам взять ПЛМ-ку сделать то же самое

Вам мешает то, что в классической модели понадобится не n, а 2^n вычислений.

но не получится ли так, что понять ответ в искомой задаче можно будет с меньшей сложностью просто посмотрев на структуру и связи используемых логических элеменов в этой функции, без необходимости запускать функцию вообще?

Нет — задача выполнимости булевых формул NP-полная. Кстати, квантовые алгоритмы и её ускоряют, но это уже другая история)

но ведь решаемая задача — не задача о выполнимости, ибо тут очень сильно сужен класс рассматриваемых функций. она вообще остается NP-полной для выбранного класса функций?

Я не знаю никаких способов по виду функции определить константна она или сбалансирована и сомневаюсь, что это возможно, не вычисляя её. А задача о выполнимости, конечно, остаётся NP-полной для функций только константных или сбалансированных: ведь указанное свойство никак не коррелирует с видом функции.

вы уверены? потому что если еще чуть-чуть сузить класс функций (например, до только константных), то задача вроде бы сразу превращается в полиномиальную. да и если подходить с другой стороны, вы привели пример вероятностного алгоритма решения задачи (который за 14 итераций), точность которого не зависит от размерности задачи. если решаемая задача NP-полна, то возможно этот алгоритм можно эффективно применять и для других NP-полных задач, в частности для задачи ВЫП в классе произвольных функций?

Не уверен. Ни в чём нельзя быть уверенным, пока это не доказано. О вероятностных алгоритмах решения задачи выполнимости тоже не слышал и не представляю, как они могли бы работать в общем случае.

Нет, не получается.

Ну т.е. Вы вычисляете результат размером в кубит на n простых кубитов — но утверждаете, что «вычисления производятся только один раз»?
Удивительно.

Вам мешает то, что в классической модели понадобится не n, а 2^n вычислений

Да, но «классическая» модель в этом случае даёт детерминированный результат, а Ваша квантовая — только вероятностный.
Да, но «классическая» модель в этом случае даёт детерминированный результат, а Ваша квантовая — только вероятностный.

В статье описан детерминированный квантовый алгоритм.

Теперь Вы ещё и понятие «детерминированности» под себя переопределяете…

Алгоритм детерменированный, если для одинаковых входных данных он всегда производит одинаковый результат. Насколько я знаю, это достаточно общепринятое определение и алгоритм Дойча-Йожи ему удовлетворяет.

В квантовой механике существуют принципиально не-стохастические решения? 0_0

Причём тут это, если мы обсуждаем детерменированность алгоритма? Это понятие из информатики, а не механики и применимо к любому алгоритму, в том числе и квантовому.


Какая разница, какие процессы происходят в основе, если они всегда приводят к детерминированному результату, что может быть доказано (и доказано в конце статьи)? Вопрос риторический, можно не отвечать. Эта ветка ушла уже далеко от темы статьи.

Какая разница, какие процессы происходят в основе, если они всегда приводят к детерминированному результату


Шта-эээ? o_0 0_0 0_0
Молодой человек, Вы как-бы самые основы своей предметной области поизучать не пробовале? Дабы, чиста па-приколу — открыть для себя некоторые элементарные вещи в области квантмеха.
Ато неудобно как-то, ей-богу.
Я правильно понимаю, что описанное бессмысленно при таком подходе:
1)Выполняем обе функции по одному разу;
2)Записываем два полученных булевых значения. Предположим, что получили i в первом случае и k во втором(вместо i, k подставить любое число являющееся 0 или 1);
3)Скармливаем эти(и только эти) полученные значения некоторому квантовому алгоритму;
4)Получаем ответ о типе функции.
?
Я не очень понял ваш вопрос. Алгоритм позволяет узнать тип только одной функции по её квантовому представлению — оракулу.

Вам с самых основ рассказывают про математику, которая стоит за (возможно) самой перспективной технологией. Ну а пока пусть "Очень сложно. До свидания" набирает лайки.

Можно немножко не по теме вопрос: у вас в профиле написано, что вы делите трехзначные числа на ноль. Вы что, не знаете, что на ноль делить нельзя? Зачем себя публично дураком выставлять?
//я надеюсь, вы поймете, что мой комментарий не следует воспринимать буквально.

Картинки, песня, два стула — хорошо.


Python 3.5 и 3.6 вообще отлично:


gate._data @ self._data

f'{mstate:>0{self._n}b}'

Но вот это уже пижонство и перебор:


x = xs[:~0]
y = xs[~0]

Оригинальный синтаксис питона в этом плане ужасен. Если я хочу получить третий элемент с начала, я пишу xs[3], а если с конца — xs[-4]. Чувствуете неконсистентность? А если использовать синтаксис xs[~i], всё становится прекрасно и логично. И больше не надо беспокоиться, что забыл единицу в индексах вроде xs[-(i + j - 4)]. Я такой приём увидел где-то в комментариях на хабре и с тех пор не могу нарадоваться. И пишу так везде, чтобы подтолкнуть народ к красивой и консистентной индексации. Пора этот приём в учебники по питону добавлять.

Наконец-то статья с нормальным описанием квантового алгоритма на Хабре!


Черт, у меня уже давно лежал черновик ликбеза по квантовым вычислениям — и на треть он совпадает с вашей статьей, ааааа! Будет урок на будущее слоупоку. Думаю, подправлю немного и в обозримом будущем выложу на ГТ.

В самом начале про классическое детерминированное решение:


Если все вычисленные значения одинаковы, то функция, очевидно, константна

Как-то неочевидно. Применяем к логическому И – функция не константна и не сбалансирована (3 пример чуть до этого).
Прошли половину + 1 аргументов – первые три пары, везде ответ 0. Но функция не константная.

Пусть дана булева функция f и о ней априорно известно, что она или константна, то есть для любого из своих аргументов всегда возвращает либо 0, либо 1, или сбалансирована, то есть ровно на половине своих аргументов возвращает 0, а ровно на половине 1.

Логическое И не проходит по предусловию. Соответственно, если больше чем на половине входов возвращается одно значение, то функция может быть только константной.
В условии задачи априорно известно, что функция либо константная, либо сбалансированная. Это наше ограничение на входные данные. С функциями не константными и не сбалансированными все предложенные алгоритмы не работают и выдают, если так угодно, случайный результат. Конъюнкцию я привёл как раз как пример «плохой» функции.

У меня про сферу Блоха вопрос. Понятно, что полезно покопаться в учебниках, но вдруг и одного комментария хватит для понимания. Википедия говорит, что на сфере находятся только чистые состояния квантовой системы, а смешанные внутри. Можно привести примеры чистых состояний (кроме |0> и |1>) и их взаимное расположение на сфере? А также примеры смешанных и где они находятся внутри.

|0>±|1>, например, чистые. Если |0> — горизонтальная поляризация фотона, а |1> — вертикальная, то |0>±|1> — круговые (соответственно, левая и правая).


Смешанные состояния — это в духе "фотон поляризован то ли горизонтально, то ли вертикально". Не путать с круговой поляризацией, которая "одновременно" и горизонтальная, и вертикальная.


Разницу хорошо видно, если взять несколько фотонов. Все фотоны в чистом состоянии |0>+|1> будут одинаковыми, а в ансамбле смешанных половина будет горизонтальной, половина — вертикальной.

Не понял как в определении оператора <фи у нас получается скалярное произведение элемента Н на элемент Н*: (<фи|, |пси>). Это скалярное произведение какого из двух пространств?
Заранее спасибо за объяснение. Статья выглядит просто волшебной.

Давайте каждому вектору x сопоставим такую функцию: f(y) = (y, x) — скалярное произведение на этот вектор. Можно считать, что мы «зафиксировали» второй аргумент или частично применили функцию скалярного произведения. Каждому вектору будет сопоставлена единственная такая функция. И каждая такая функция будет линейным оператором, поэтому всё их множество будет содержаться в множестве линейных операторов — сопряжённом пространстве. А теперь мы обозначим каждую такую функцию бра-вектором, внутри которого записан «зафиксированный» аргумент. Таким образом, запись <x|y> — скалярное произведение x на y в оригинальном пространстве кет-векторов, записанное в непривычной форме, но имеющее под собой чёткое обоснование.

В рамках данной статьи такое обозначение не несло никакого дополнительного смысла и его можно было бы и вовсе не использовать, однако оно общепринято в квантовой информатике, поэтому я и попытался его объяснить.
Итак, не понял утверждение
Теперь можно сделать важную поправку: квантовую систему может описывать не любое гильбертово пространство, а лишь такое, что

то есть норма каждого элемента равна единице.

В любом гильбертовом пространстве есть вектора с любой вещественной нормой, так как вектор можно умножать на любую действительную константу, и норма умножится соответствующим образом.
Если мы выделим в нашем гильбертовом пространстве состояний некоторый базис

Обязательно ортонормированный базис, иначе вместо простой суммы со скалярными произведениями в коэффициентах надо будет систему уравнений решать.

представляет из себя трёхмерную сферу

Тут, вероятно, стоит прояснить, что трехмерная сфера — это не самая обыкновенная сфера в трехмерном пространстве, а все-таки поверхность размерности 3 в четырехмерном пространстве над действительными числами, порожденном двумя парами коэффициентов, задающими числа альфа и бета. Картинка с обычной сферой тоже сбивает на представление об обычной сфере :) По крайней мере, мне показалось что вы подразумеваете такую сферу, иначе по размерности никак не вяжется…
Only those users with full accounts are able to leave comments. Log in, please.