Какова временная сложность (не сложность запросов) алгоритма Гровера? Мне кажется ясным, что это поскольку существуют итерации и каждая итерация требует использования операции отражения, которая в свою очередь требует времени с использованием любого стандартного набора универсальных ворот.Ω( √Ω (...
В «Квантовых вычислениях» и «Квантовой информации» Нильсена и Чуанга они говорят, что многие из алгоритмов, основанных на квантовых преобразованиях Фурье, основаны на свойстве инвариантности Козе преобразований Фурье и предполагают, что свойства инвариантности других преобразований могут дать новые...
В своей статье 1995 года « Алгоритмы полиномиального времени для первичной факторизации и дискретных логарифмов на квантовом компьютере» Питер У. Шор обсуждает усовершенствование порядка упорядочения своего алгоритма факторизации. Стандартные выходы алгоритма r′r′r' , делитель порядка rrr из xxx по...
Хорошо известно, что квантовые компьютеры являются строго более мощными, чем их классические аналоги, с точки зрения сложности запросов . Существуют ли другие модели (естественные или искусственные), которые строго находятся между квантовой и классической с точки зрения сложности запросов?...
Можно ли алгоритмически проверить, является ли вычисляемое число рациональным или целым? Другими словами, возможно ли для библиотеки, которая реализует вычислимые числа, предоставлять функции isIntegerили isRational? Я предполагаю, что это невозможно, и что это как-то связано с тем, что невозможно...
Просто из любопытства, если классические вычисления основаны на матрицах перестановок, а квантовые вычисления - на унитарных матрицах (из которых матрицы подстановок являются подгруппой), то будет ли какая-либо парадигма вычислений помимо унитарных...
В глубине души я физик, и поэтому я считаю, что односторонние квантовые вычисления великолепны. В частности, Quantum Computing (MBQC), основанная на измерениях графических состояний, была действительно хорошей разработкой в исследованиях Quantum Computing, созданной Raussendorf & Briegel ....
В каких университетах существует сильная учебная программа по квантовым вычислениям и предлагаются какие-либо курсы / исследования по квантовым вычислениям? Цель здесь - собрать полезный список для тех, кто рассматривает аспирантуру в этих областях, а не для обсуждения того, что является «лучшим»....
Недавно Ватроус и др. Доказали, что QIP (3) = PSPACE - замечательный результат. Это был удивительный результат для меня, если не сказать больше, и это заставило меня задуматься ... Я задавался вопросом, что если бы Quantum Computers могла эффективно моделироваться классическими компьютерами. Может...
Квантовые вычисления - это активная область исследований, целью которой является использование квантовой физики (например, квантовой запутанности) для повышения эффективности компьютеров (не изменяет тезис Черча-Тьюринга ). Каковы наиболее значимые эксперименты, которые были проведены для...
Одна вещь, которую могут сделать квантовые компьютеры (возможно, даже с использованием только квантовых цепей с логарифмической глубиной BPP +), - это аппроксимировать выборку преобразования Фурье булевой -значной функции в P.± 1±1\pm 1 Здесь и ниже, когда я говорю о выборке преобразования Фурье, я...
Давайте предположим, что мы создали универсальный квантовый компьютер. За исключением вопросов, связанных с безопасностью (криптография, конфиденциальность, ...), какие текущие проблемы реального мира могут извлечь выгоду из его использования? Я заинтересован в обоих: проблемы, в настоящее время...
Метод отрицательного противника ( ) - это SDP, характеризующий сложность квантового запроса. Это обобщение широко используемого метода противника ( A D V ), и оно преодолевает два барьера, мешающих противнику:A D V±ADВ±ADV^\pmA D VADВADV Барьер тестирования свойств: если все 0-экземпляры находятся...
(также спрашивается здесь , без ответов) -квантовый расширитель является распределение над унитарной группой со свойством , что: а) , b) , где \ mu_H - мера Хаара. Если вместо распределений по унитарным мы рассмотрим распределения по матрицам перестановок, нетрудно увидеть, что мы восстанавливаем...
Как хорошо известно, PARITY не может быть выполнено в многоразмерных схемах с постоянной глубиной, и на самом деле схемы с постоянным углублением требуют количества входов EXP. А как насчет схем QUANTUM? а) Можно ли выполнить PARITY с помощью квантового контура, который имеет постоянную глубину и...
Ограниченные во времени квантовые вычисления, очевидно, очень интересны. Как насчет квантовых вычислений, ограниченных пространством? Я знаю много интересных результатов для квантовых вычислений с сублогарифмическими пространственными границами и различными типами моделей квантовых автоматов. С...
Что я должен прочитать, чтобы понять эту проблему? Мощность квантовых цепей малой глубины. Является ли ? Другими словами, может ли «квантовая» часть любого квантового алгоритма быть сжата до глубины полилога (n), если мы хотим выполнить классическую постобработку за полиномиальное время? (Известно,...
В «Квантовых вычислениях и квантовой информации» Майка и Айка алгоритм Гровера объясняется очень подробно. Тем не менее, в книге и во всех объяснениях, которые я нашел в Интернете для алгоритма Гровера, кажется, нет упоминания о том, как устроен Оракул Гровера, если только мы уже не знаем, какое...
Следующая проблема появляется в списке Ааронсона « Десять полуградовых вызовов для теории квантовых вычислений» . IsB Q P = B P PB Q N CВQпзнак равноВппВQNС\mathsf{BQP}=\mathsf{BPP}^{\mathsf{BQNC}} р о л у л о г (п) В В Р В Р Р Б В Н С Другими словами, может ли «квантовая» часть любого квантового...
Класс сложности BQP соответствует квантовым подпрограммам полиномиального времени, принимающим классические входы и выпадающим вероятностным классическим выходом. Квантовый совет изменяет это, чтобы включить копии некоторых заранее определенных состояний квантового совета, но с классическими...