Комментарии 61
Редко встречается такой контент и прекрасное оформление. Спасибо
Про возможность построения оракулов — это скорее к физикам. У нас есть прекрасная стройная теория, в которой можно использовать любые необходимые нам объекты классического мира в виде оракулов и мы ей пользуемся, не заботясь особо о практической реализации. Существуют алгоритмы, где оракул можно заранее вычислить на классическом компьютере и уже с его помощью решать гораздо более сложную задачу в квантовой модели.
Возвращаясь к вашему вопросу. С помощью базовых логических квантовых элементов можно построить произвольную булеву функцию. Допустим, у нас есть функция 1010 аргументов. Но мы так же знаем, как без вычислений функции построить её квантовый оракул из логических элементов. Тогда квантовый алгоритм окажется предпочтительным.
Алгоритм Дойча-Йожи — не самый лучший пример решения практически важных задач, однако он крайне интересен с теоретической точки зрения, позволяет показать все возможные преимущества квантового подхода и идеален для первого знакомства с квантовыми вычислениями в силу своей простоты.
«Вот вам функция. Если она константная, то мы вас уничтожим, если сбалансированная — вам повезло.»Вот, именно при такой постановке задачи, по завету товарища Сухова, стоило бы помучиться с отсылкой запросов классической версии. Вдруг функция сбалансированная?
Классическая версия, говорят, тоже есть, но она дома, шлите туда запросы: 5 лет в одну сторону, 5 обратно.
Спасибо, было интересно, но понять так и не смог. Сдался чуть позже середины. В итоге решил скопипастить код и посмотреть просто посмотреть что будет. Ожидаемо, чуда не случилось. В эмуляторе функция вызывается с полным перебором всех возможных аргументов.
Как только появляется слово «квантовая» — так сразу же начинается всяческая фигня и самозапутывание…
В самом алгоритме вызов функции один — применение квантового оракула.
Э-ээ, а разве «вызов» в квантовых вычислениях эквивалентен вызову функции в обычных тьюринговых машинах? Что-то, как я понял — квантовый оракул сразу порождает ответы для всех значений входного вектора.
Ни?
Операторы/гейты физически это что? Прибор, сигнал, ритуал?
В каком вообще сценарии без инопланетян мы можем получить интересный нам оракул для неизвестной нам функции?
Оракул это просто линейный оператор параметризованный этой функцией.
|x,y>->|x,y + f(x)>.
Как оно реализовано в природе вообще говоря не важно. Говоря языком "фронтендера" оракул это нечто реализуете api указанное выше.
В задаче дойча-йожи да нужен оракул для произвольной функции.
Но есть задачи в которых функция оракула известна заранее, тогда просто реализуют такой оператор, что, вообще говоря, тоже не всегда просто.
Но на практике попытки реализации упираются в очередное дурацкое несовершенство физического мира, с его инерционностями, нелинейностями и тому подобными гадостями. Пока еще ни кто не доказал, что физический квантовый мир обладает всеми нужными свойствами, каким его представляет себе модель КК, и из этой затеи выйдет что-то полезное.
Но чтобы построить оракул, совсем не обязательно вычислять классическую функцию: он может быть построен из логических элементов, может быть дан свыше, может быть найден в природе и т.д.
Квантовый оракул не может быть построен из логических элементов, бо они — не квантовые.
Не подчиняются (на макроуровне) волновому уравнению Шредингера, и не нуждаются в волновой пси-функции для своего описания.
В настоящем квантовом компьютере мы не будем вычислять и знать матрицу оракула, это будет некоторый физический объект с требуемыми нам свойствами, который переведёт нашу квантовую систему в нужное состояние.
Вот смотрите:
— Вы рассматриваете логическую функцию. Для представления её результата достаточно одного бита, в случае квуантовых вычислений — простого кубита с двумя состояниями, к которому применяются соотв. унитарные преобразования для получения результата вычислений.
— квантовый оракул для своего представления требует n (или n+1, мне ломы разбираться, где n — число аргументов) простых кубитов, к которым дважды применяется преобразование Адамара + наша искомая функция.
Но таким образом получается, что реально наша функция вычисляется как минимум n раз — только в параллель.
Но что мешает нам взять ПЛМ-ку сделать то же самое — и причём тут «квантовые вычисления»?
Квантовый оракул не может быть построен из логических элементов, бо они — не квантовые.
Не подчиняются (на макроуровне) волновому уравнению Шредингера, и не нуждаются в волновой пси-функции для своего описания.
Естественно, в контексте квантовых вычислений речь идёт о квантовых логических элементах. Вот например, функция f(x) = x из статьи может быть выражена с помощью одного гейта CNOT:
А вот f(x) = ~x:
Аналогично выражается любая логическая функция любого количества переменных. Доказано, что это возможно с помощью универсального гейта Тоффоли:
Но таким образом получается, что реально наша функция вычисляется как минимум n раз — только в параллель.
Нет, не получается.
Но что мешает нам взять ПЛМ-ку сделать то же самое
Вам мешает то, что в классической модели понадобится не n, а 2^n вычислений.
Нет — задача выполнимости булевых формул NP-полная. Кстати, квантовые алгоритмы и её ускоряют, но это уже другая история)
Я не знаю никаких способов по виду функции определить константна она или сбалансирована и сомневаюсь, что это возможно, не вычисляя её. А задача о выполнимости, конечно, остаётся NP-полной для функций только константных или сбалансированных: ведь указанное свойство никак не коррелирует с видом функции.
Нет, не получается.
Ну т.е. Вы вычисляете результат размером в кубит на n простых кубитов — но утверждаете, что «вычисления производятся только один раз»?
Удивительно.
Вам мешает то, что в классической модели понадобится не n, а 2^n вычислений
Да, но «классическая» модель в этом случае даёт детерминированный результат, а Ваша квантовая — только вероятностный.
Да, но «классическая» модель в этом случае даёт детерминированный результат, а Ваша квантовая — только вероятностный.
В статье описан детерминированный квантовый алгоритм.
Алгоритм детерменированный, если для одинаковых входных данных он всегда производит одинаковый результат. Насколько я знаю, это достаточно общепринятое определение и алгоритм Дойча-Йожи ему удовлетворяет.
Причём тут это, если мы обсуждаем детерменированность алгоритма? Это понятие из информатики, а не механики и применимо к любому алгоритму, в том числе и квантовому.
Какая разница, какие процессы происходят в основе, если они всегда приводят к детерминированному результату, что может быть доказано (и доказано в конце статьи)? Вопрос риторический, можно не отвечать. Эта ветка ушла уже далеко от темы статьи.
Какая разница, какие процессы происходят в основе, если они всегда приводят к детерминированному результату
Шта-эээ? o_0 0_0 0_0
Молодой человек, Вы как-бы самые основы своей предметной области поизучать не пробовале? Дабы, чиста па-приколу — открыть для себя некоторые элементарные вещи в области квантмеха.
Ато неудобно как-то, ей-богу.
1)Выполняем обе функции по одному разу;
2)Записываем два полученных булевых значения. Предположим, что получили i в первом случае и k во втором(вместо i, k подставить любое число являющееся 0 или 1);
3)Скармливаем эти(и только эти) полученные значения некоторому квантовому алгоритму;
4)Получаем ответ о типе функции.
?
Что, нельзя было без бредовых картинок?
Низя.
//я надеюсь, вы поймете, что мой комментарий не следует воспринимать буквально.
Про деление на ноль на Хабре есть статья: https://habrahabr.ru/post/247635/
Картинки, песня, два стула — хорошо.
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> будут одинаковыми, а в ансамбле смешанных половина будет горизонтальной, половина — вертикальной.
Не понял как в определении оператора <фи у нас получается скалярное произведение элемента Н на элемент Н*: (<фи|, |пси>). Это скалярное произведение какого из двух пространств?
Заранее спасибо за объяснение. Статья выглядит просто волшебной.
В рамках данной статьи такое обозначение не несло никакого дополнительного смысла и его можно было бы и вовсе не использовать, однако оно общепринято в квантовой информатике, поэтому я и попытался его объяснить.
Теперь можно сделать важную поправку: квантовую систему может описывать не любое гильбертово пространство, а лишь такое, что
…
то есть норма каждого элемента равна единице.
В любом гильбертовом пространстве есть вектора с любой вещественной нормой, так как вектор можно умножать на любую действительную константу, и норма умножится соответствующим образом.
Если мы выделим в нашем гильбертовом пространстве состояний некоторый базис
Обязательно ортонормированный базис, иначе вместо простой суммы со скалярными произведениями в коэффициентах надо будет систему уравнений решать.
представляет из себя трёхмерную сферу
Тут, вероятно, стоит прояснить, что трехмерная сфера — это не самая обыкновенная сфера в трехмерном пространстве, а все-таки поверхность размерности 3 в четырехмерном пространстве над действительными числами, порожденном двумя парами коэффициентов, задающими числа альфа и бета. Картинка с обычной сферой тоже сбивает на представление об обычной сфере :) По крайней мере, мне показалось что вы подразумеваете такую сферу, иначе по размерности никак не вяжется…
Есть две функции