Вопросы с тегом «complexity-theory»

По вопросам, касающимся анализа сложности квантовых алгоритмов и сравнений со сложностями классических алгоритмов.

41
Возможно ли существование метода шифрования, который невозможно взломать, даже используя квантовые компьютеры?

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

27
Существуют ли проблемы, при которых квантовые компьютеры обладают экспоненциальным преимуществом?

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

27
Как реализован оракул в алгоритме поиска Гровера?

Алгоритм поиска Гровера обеспечивает доказуемое квадратичное ускорение поиска в несортированной базе данных. Алгоритм обычно выражается следующей квантовой схемой: В большинстве представлений важнейшая часть протокола - «врата оракула» UωUωU_\omega , который «волшебным образом» выполняет операцию...

27
Есть ли объяснение непрофессионала, почему работает алгоритм Гровера?

Этот пост от Скотта Ааронсона - очень полезное и простое объяснение алгоритма Шора . Мне интересно, есть ли такое объяснение для второго наиболее известного квантового алгоритма: алгоритм Гровера для поиска в неупорядоченной базе данных размера в O ( √O ( n )O(n)O(n)времяO ( n--√)O(n)O(\sqrt{n}) В...

26
Почему квантовый компьютер в некотором смысле более мощный, чем недетерминированная машина Тьюринга?

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

24
Есть ли общее утверждение о том, какие проблемы можно решить более эффективно с помощью квантового компьютера?

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

14
Гамильтоново моделирование является BQP-полным

Во многих работах утверждается, что гамильтоново моделирование является BQP-полным (например, гамильтоново моделирование с почти оптимальной зависимостью от всех параметров и гамильтоново моделирование с помощью кубитизации ). Легко видеть, что гамильтоново моделирование является BQP-сложным,...

14
Есть ли результаты квантовых алгоритмов или сложности, которые приводят к успехам в проблеме P против NP?

На первый взгляд, квантовые алгоритмы имеют мало общего с классическими вычислениями и P против NP, в частности: решение задач из NP с квантовыми компьютерами ничего не говорит нам об отношениях этих классических классов сложности 1 . С другой стороны, «альтернативное описание» классического класса...

13
Что такое поствыбор в квантовых вычислениях?

Квантовый компьютер может эффективно решать задачи, лежащие в классе сложности BQP . Я видел утверждение, которое можно (потенциально, потому что мы не знаем, является ли BQP правильным подмножеством или равным PP), чтобы повысить эффективность квантового компьютера путем применения поствыбора и...

13
Каково современное состояние в алгоритмах квантовой сортировки?

В результате превосходного ответа на мой вопрос о квантовой bogosort мне стало интересно, каково современное состояние квантовых алгоритмов сортировки. Чтобы быть точным, сортировка здесь определяется как следующая проблема: Учитывая массив AAA целых чисел (не стесняйтесь выбирать ваше...

12
Алгоритм Гровера и его связь с классами сложности?

Я запутался в алгоритме Гровера и его связи с классами сложности. Алгоритм Гровера находит и элемент в базе данных с (таким, что ) элементов с обращениями к оракулу.kkkN=2nN=2nN=2^nf(k)=1f(k)=1f(k)=1∼N−−√=2n/2∼N=2n/2\sim \sqrt{N}=2^{n/2} Итак, у нас есть следующая проблема: Проблема: Найти в базе...

11
Есть ли какое-либо общее утверждение о том, какие проблемы можно аппроксимировать более эффективно с помощью квантового компьютера?

Как видно из названия, этот вопрос является продолжением этого другого . Я был в восторге от качества ответов, но я чувствовал, что было бы очень интересно, если бы были добавлены идеи по оптимизации и методам аппроксимации, но они могут не соответствовать теме, отсюда и этот вопрос. Из ответа Блю:...

11
Существуют ли какие-либо комплекты шифрования, которые могут быть взломаны классическими компьютерами, но не квантовыми компьютерами?

Существуют ли какие-либо комплекты шифрования, которые могут быть взломаны обычными компьютерами или суперкомпьютерами, но не квантовыми компьютерами? Если это возможно, от каких предположений это будет зависеть? (Факторизация больших чисел, ab(modd)ab(modd)a^b\pmod d ac(modd)ac(modd)a^c\pmod d...

11
Сколько операций может выполнять квантовый компьютер в секунду?

Я хочу знать, какая временная сложность считается эффективной / неэффективной для квантовых компьютеров. Для этого мне нужно знать, сколько операций может выполнять квантовый компьютер в секунду. Может кто-нибудь сказать мне, как рассчитать его и от каких факторов это зависит (детали реализации или...

10
Хороший вводный материал по классам квантовой сложности вычислений

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

10
Отделение NP от BQP относительно оракула

Я смотрел на эту лекцию, где автор дает разделение оракула междуBQPBQP\mathsf{BQP} а также NPNP\mathsf{NP}, Он намекает на то, как «стандартные методы диагонализации могут использоваться, чтобы сделать это строгим». Может ли кто-нибудь подробно описать метод диагонализации, который следует...

9
BQP только о времени? Это имеет смысл?

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

9
Чему мы можем научиться у «квантового богосорта»?

Недавно я прочитал о «квантовом богосорте» в некоторых вики. Основная идея заключается в том, что, подобно bogosort, мы просто перетасовываем наш массив и надеемся, что он отсортирован «случайно», и повторяем попытку при сбое. Разница в том, что теперь у нас есть « магический квант», поэтому мы...

9
Квантовый алгоритм для числа Бога

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