По вопросам, касающимся анализа сложности квантовых алгоритмов и сравнений со сложностями классических алгоритмов.
Известно, что квантовые компьютеры способны за полиномиальное время взломать широкий спектр криптографических алгоритмов, которые ранее считались разрешимыми только за счет экспоненциального увеличения ресурсов с увеличением размера ключа. Примером этого является алгоритм Шора . Но, насколько я...
Обычно считается и утверждается, что квантовые компьютеры могут превзойти классические устройства по крайней мере в некоторых задачах. Одним из наиболее часто цитируемых примеров проблемы, в которой квантовые компьютеры будут превосходить классические устройства, является , но, опять же, также не...
Алгоритм поиска Гровера обеспечивает доказуемое квадратичное ускорение поиска в несортированной базе данных. Алгоритм обычно выражается следующей квантовой схемой: В большинстве представлений важнейшая часть протокола - «врата оракула» UωUωU_\omega , который «волшебным образом» выполняет операцию...
Этот пост от Скотта Ааронсона - очень полезное и простое объяснение алгоритма Шора . Мне интересно, есть ли такое объяснение для второго наиболее известного квантового алгоритма: алгоритм Гровера для поиска в неупорядоченной базе данных размера в O ( √O ( n )O(n)O(n)времяO ( n--√)O(n)O(\sqrt{n}) В...
Стандартный популярный новостной отчет о квантовых вычислениях состоит в том, что квантовый компьютер (КК) будет работать, разбивая экспоненциально много невзаимодействующих параллельных копий себя в разных вселенных и имея каждую попытку проверить другой сертификат, а затем в конце вычисления...
Есть ли общее утверждение о том, какие проблемы можно решить более эффективно с помощью квантовых компьютеров (только модель с квантовыми воротами)? Имеют ли общие проблемы проблемы, для которых сегодня известен алгоритм? Насколько я понимаю, квантовые вычисления помогают с проблемой скрытой...
Во многих работах утверждается, что гамильтоново моделирование является BQP-полным (например, гамильтоново моделирование с почти оптимальной зависимостью от всех параметров и гамильтоново моделирование с помощью кубитизации ). Легко видеть, что гамильтоново моделирование является BQP-сложным,...
На первый взгляд, квантовые алгоритмы имеют мало общего с классическими вычислениями и P против NP, в частности: решение задач из NP с квантовыми компьютерами ничего не говорит нам об отношениях этих классических классов сложности 1 . С другой стороны, «альтернативное описание» классического класса...
Квантовый компьютер может эффективно решать задачи, лежащие в классе сложности BQP . Я видел утверждение, которое можно (потенциально, потому что мы не знаем, является ли BQP правильным подмножеством или равным PP), чтобы повысить эффективность квантового компьютера путем применения поствыбора и...
В результате превосходного ответа на мой вопрос о квантовой bogosort мне стало интересно, каково современное состояние квантовых алгоритмов сортировки. Чтобы быть точным, сортировка здесь определяется как следующая проблема: Учитывая массив AAA целых чисел (не стесняйтесь выбирать ваше...
Я запутался в алгоритме Гровера и его связи с классами сложности. Алгоритм Гровера находит и элемент в базе данных с (таким, что ) элементов с обращениями к оракулу.kkkN=2nN=2nN=2^nf(k)=1f(k)=1f(k)=1∼N−−√=2n/2∼N=2n/2\sim \sqrt{N}=2^{n/2} Итак, у нас есть следующая проблема: Проблема: Найти в базе...
Как видно из названия, этот вопрос является продолжением этого другого . Я был в восторге от качества ответов, но я чувствовал, что было бы очень интересно, если бы были добавлены идеи по оптимизации и методам аппроксимации, но они могут не соответствовать теме, отсюда и этот вопрос. Из ответа Блю:...
Существуют ли какие-либо комплекты шифрования, которые могут быть взломаны обычными компьютерами или суперкомпьютерами, но не квантовыми компьютерами? Если это возможно, от каких предположений это будет зависеть? (Факторизация больших чисел, ab(modd)ab(modd)a^b\pmod d ac(modd)ac(modd)a^c\pmod d...
Я хочу знать, какая временная сложность считается эффективной / неэффективной для квантовых компьютеров. Для этого мне нужно знать, сколько операций может выполнять квантовый компьютер в секунду. Может кто-нибудь сказать мне, как рассчитать его и от каких факторов это зависит (детали реализации или...
Я хочу больше узнать о классах вычислительной сложности в контексте квантовых вычислений. Среда не так важна; это может быть книга, онлайн лекционные заметки или тому подобное. Важнее всего содержание. Материал должен охватывать основы классов квантовой сложности вычислений и обсуждать сходства,...
Я смотрел на эту лекцию, где автор дает разделение оракула междуBQPBQP\mathsf{BQP} а также NPNP\mathsf{NP}, Он намекает на то, как «стандартные методы диагонализации могут использоваться, чтобы сделать это строгим». Может ли кто-нибудь подробно описать метод диагонализации, который следует...
Класс сложности BQP (квантовое полиномиальное время с ограниченной ошибкой), по-видимому, определяется только с учетом фактора времени. Это всегда значимо? Существуют ли алгоритмы, где вычислительное время масштабируется полиномиально с размером входного сигнала, но другие ресурсы, такие как...
Недавно я прочитал о «квантовом богосорте» в некоторых вики. Основная идея заключается в том, что, подобно bogosort, мы просто перетасовываем наш массив и надеемся, что он отсортирован «случайно», и повторяем попытку при сбое. Разница в том, что теперь у нас есть « магический квант», поэтому мы...
Божье число является худшим случаем Божьего алгоритма, который понятие, возникающее в обсуждении способов решения головоломки кубика Рубика, но которое также может быть применено к другим комбинаторным головоломкам и математическим играм. Это относится к любому алгоритму, который дает решение,...