Ваша проблема на самом деле связана с типами. Меняя порядок следования аргументов в динамическом языке вы неявно меняете тип функции. В хорошем статическом языке такая ситуация невозможна. Предвосхищая замечания, для типов, одинаковых на машинном уровне, но разных семантически, существует newtype.
Передача вместо множества аргументов одного большого объекта, конечно, решает проблему с порядком аргументов, но рождает проблемы ещё больше и серьёзнее.
И по количеству закрывающих скобочек стремится к коду на лиспе. Поэтому я очень часто мечтаю о функциональном языке, компилируемом в питон. Автор, большое спасибо. Хочется побольше статей с примерами применения и, в особенности, использования в нём математических пакетов, таких как numpy например.
Причём тут это, если мы обсуждаем детерменированность алгоритма? Это понятие из информатики, а не механики и применимо к любому алгоритму, в том числе и квантовому.
Какая разница, какие процессы происходят в основе, если они всегда приводят к детерминированному результату, что может быть доказано (и доказано в конце статьи)? Вопрос риторический, можно не отвечать. Эта ветка ушла уже далеко от темы статьи.
Алгоритм детерменированный, если для одинаковых входных данных он всегда производит одинаковый результат. Насколько я знаю, это достаточно общепринятое определение и алгоритм Дойча-Йожи ему удовлетворяет.
Не уверен. Ни в чём нельзя быть уверенным, пока это не доказано. О вероятностных алгоритмах решения задачи выполнимости тоже не слышал и не представляю, как они могли бы работать в общем случае.
Я не знаю никаких способов по виду функции определить константна она или сбалансирована и сомневаюсь, что это возможно, не вычисляя её. А задача о выполнимости, конечно, остаётся NP-полной для функций только константных или сбалансированных: ведь указанное свойство никак не коррелирует с видом функции.
Квантовый оракул не может быть построен из логических элементов, бо они — не квантовые.
Не подчиняются (на макроуровне) волновому уравнению Шредингера, и не нуждаются в волновой пси-функции для своего описания.
Естественно, в контексте квантовых вычислений речь идёт о квантовых логических элементах. Вот например, функция f(x) = x из статьи может быть выражена с помощью одного гейта CNOT:
А вот f(x) = ~x:
Аналогично выражается любая логическая функция любого количества переменных. Доказано, что это возможно с помощью универсального гейта Тоффоли:
Но таким образом получается, что реально наша функция вычисляется как минимум n раз — только в параллель.
Нет, не получается.
Но что мешает нам взять ПЛМ-ку сделать то же самое
Вам мешает то, что в классической модели понадобится не n, а 2^n вычислений.
Оригинальный синтаксис питона в этом плане ужасен. Если я хочу получить третий элемент с начала, я пишу xs[3], а если с конца — xs[-4]. Чувствуете неконсистентность? А если использовать синтаксис xs[~i], всё становится прекрасно и логично. И больше не надо беспокоиться, что забыл единицу в индексах вроде xs[-(i + j - 4)]. Я такой приём увидел где-то в комментариях на хабре и с тех пор не могу нарадоваться. И пишу так везде, чтобы подтолкнуть народ к красивой и консистентной индексации. Пора этот приём в учебники по питону добавлять.
Ну, если оракул задан набором логических операторов, то достаточно легко. В любом другом случае, скорее всего, никак. Не стоит относиться к описанному алгоритму как к практически значимому :) У нас ещё квантовых компьютеров всего пара штук на всей Земле, а вы уже возмущаетесь, что мы оракулы строить и верифицировать не умеем…
Давайте каждому вектору x сопоставим такую функцию: f(y) = (y, x) — скалярное произведение на этот вектор. Можно считать, что мы «зафиксировали» второй аргумент или частично применили функцию скалярного произведения. Каждому вектору будет сопоставлена единственная такая функция. И каждая такая функция будет линейным оператором, поэтому всё их множество будет содержаться в множестве линейных операторов — сопряжённом пространстве. А теперь мы обозначим каждую такую функцию бра-вектором, внутри которого записан «зафиксированный» аргумент. Таким образом, запись <x|y> — скалярное произведение x на y в оригинальном пространстве кет-векторов, записанное в непривычной форме, но имеющее под собой чёткое обоснование.
В рамках данной статьи такое обозначение не несло никакого дополнительного смысла и его можно было бы и вовсе не использовать, однако оно общепринято в квантовой информатике, поэтому я и попытался его объяснить.
Конечно, «вызов» стоило взять в кавычки. Мы один раз получаем от оракула всю информацию о функции. Но чтобы построить оракул, совсем не обязательно вычислять классическую функцию: он может быть построен из логических элементов, может быть дан свыше, может быть найден в природе и т.д. В настоящем квантовом компьютере мы не будем вычислять и знать матрицу оракула, это будет некоторый физический объект с требуемыми нам свойствами, который переведёт нашу квантовую систему в нужное состояние. А для эмуляции квантовых вычислений, конечно, необходимо вызвать функцию на всех аргументах и построить оракул в явном виде.
В условии задачи априорно известно, что функция либо константная, либо сбалансированная. Это наше ограничение на входные данные. С функциями не константными и не сбалансированными все предложенные алгоритмы не работают и выдают, если так угодно, случайный результат. Конъюнкцию я привёл как раз как пример «плохой» функции.
Ваша проблема на самом деле связана с типами. Меняя порядок следования аргументов в динамическом языке вы неявно меняете тип функции. В хорошем статическом языке такая ситуация невозможна. Предвосхищая замечания, для типов, одинаковых на машинном уровне, но разных семантически, существует
newtype.Передача вместо множества аргументов одного большого объекта, конечно, решает проблему с порядком аргументов, но рождает проблемы ещё больше и серьёзнее.
Замечательно, спасбо большое! Вот только
attrgetter('filename')не радует, я бы оставил лямбду)Мой код для обработки данных зачастую выглядит как-то так:
И по количеству закрывающих скобочек стремится к коду на лиспе. Поэтому я очень часто мечтаю о функциональном языке, компилируемом в питон. Автор, большое спасибо. Хочется побольше статей с примерами применения и, в особенности, использования в нём математических пакетов, таких как
numpyнапример.Причём тут это, если мы обсуждаем детерменированность алгоритма? Это понятие из информатики, а не механики и применимо к любому алгоритму, в том числе и квантовому.
Какая разница, какие процессы происходят в основе, если они всегда приводят к детерминированному результату, что может быть доказано (и доказано в конце статьи)? Вопрос риторический, можно не отвечать. Эта ветка ушла уже далеко от темы статьи.
Алгоритм детерменированный, если для одинаковых входных данных он всегда производит одинаковый результат. Насколько я знаю, это достаточно общепринятое определение и алгоритм Дойча-Йожи ему удовлетворяет.
В статье описан детерминированный квантовый алгоритм.
Не уверен. Ни в чём нельзя быть уверенным, пока это не доказано. О вероятностных алгоритмах решения задачи выполнимости тоже не слышал и не представляю, как они могли бы работать в общем случае.
Я не знаю никаких способов по виду функции определить константна она или сбалансирована и сомневаюсь, что это возможно, не вычисляя её. А задача о выполнимости, конечно, остаётся NP-полной для функций только константных или сбалансированных: ведь указанное свойство никак не коррелирует с видом функции.
Нет — задача выполнимости булевых формул NP-полная. Кстати, квантовые алгоритмы и её ускоряют, но это уже другая история)
Естественно, в контексте квантовых вычислений речь идёт о квантовых логических элементах. Вот например, функция
f(x) = xиз статьи может быть выражена с помощью одного гейта CNOT:А вот
f(x) = ~x:Аналогично выражается любая логическая функция любого количества переменных. Доказано, что это возможно с помощью универсального гейта Тоффоли:
Нет, не получается.
Вам мешает то, что в классической модели понадобится не n, а 2^n вычислений.
Оригинальный синтаксис питона в этом плане ужасен. Если я хочу получить третий элемент с начала, я пишу
xs[3], а если с конца —xs[-4]. Чувствуете неконсистентность? А если использовать синтаксисxs[~i], всё становится прекрасно и логично. И больше не надо беспокоиться, что забыл единицу в индексах вродеxs[-(i + j - 4)]. Я такой приём увидел где-то в комментариях на хабре и с тех пор не могу нарадоваться. И пишу так везде, чтобы подтолкнуть народ к красивой и консистентной индексации. Пора этот приём в учебники по питону добавлять.В рамках данной статьи такое обозначение не несло никакого дополнительного смысла и его можно было бы и вовсе не использовать, однако оно общепринято в квантовой информатике, поэтому я и попытался его объяснить.
@— один из бинарных операторов в Python, описан в PEP465, добавлен в версии 3.5. Акутальная версия, кстати, уже 3.6.Низя.