Квантовые вычисления и вычислительные проблемы, связанные с квантовой механикой
Это «исторический вопрос» больше, чем вопрос исследования, но было ли классическое сведение к нахождению порядка в алгоритме факторизации Шора первоначально обнаруженным Питером Шором, или это было известно ранее? Есть ли статья, описывающая сокращение, предшествующее Шору, или это просто так...
В свете анонса первого в мире программируемого квантово-фотонного чипа мне стало интересно, каким будет программное обеспечение для компьютера, использующего квантовую запутанность. Одна из первых программ, которые я когда-либо писал for i = 1 to 10 print i next i Кто-нибудь может привести пример...
В своей знаменитой статье «Сопряженное кодирование» (написано около 1970 года) Стивен Виснер предложил схему для квантовых денег, которую безоговорочно невозможно подделать, предполагая, что банк-эмитент имеет доступ к гигантской таблице случайных чисел и что банкноты могут быть принесены обратно в...
Кажется очевидным, что результаты теоретической физики значительно повлияли на ряд подполей теоретической информатики. Два примера этого Квантовые вычисления Результаты статистической механики, используемые в анализе сложности / эвристических алгоритмах. Итак, мой вопрос: есть ли какие-то основные...
Центральная проблема теории сложности, возможно, против .Н ПпPPNпNPNP Однако, поскольку Природа является квантовой, представляется более естественным рассмотреть классы (т. Е. Задачи решения, решаемые квантовым компьютером за полиномиальное время с вероятностью ошибки не более 1/3 для всех случаев)...
Как любитель TCS, я читаю некоторые очень вводные материалы по квантовым вычислениям. Вот несколько элементарных кусочков информации, которые я узнал до сих пор: Известно, что квантовые компьютеры не решают NP-полных задач за полиномиальное время. «Квантовой магии будет недостаточно» (Беннетт и...
Я иногда слышал, как люди говорят о квантовых алгоритмах, о состояниях и о способности рассматривать несколько возможностей одновременно, но мне так и не удалось найти кого-то, кто мог бы объяснить вычислительную модель, стоящую за этим. Чтобы было ясно, я не спрашиваю о том, как физически...
Не похоже, что это известно - но есть ли интересные нижние оценки сложности умножения матриц в модели квантовых вычислений? Есть ли у нас какая-то интуиция, что мы можем победить сложность алгоритма Копперсмита-Винограда, используя квантовые...
Классические алгоритмы могут решать 3-SAT за времени (рандомизированный) или времени (детерминированный). (Ссылка: лучшие верхние границы по SAT )1,3071N1,3071N1.3071^n1,3303N1,3303N1.3303^n Для сравнения, используя алгоритм Гровера на квантовом компьютере, можно было бы найти и найти решение в ,...
Предположим, что P = NP верно. Будет ли тогда какое-либо практическое применение для построения квантового компьютера, такое как быстрое решение определенных задач, или же любое такое улучшение будет неуместным, основываясь на том факте, что P = NP верно? Как бы вы охарактеризовали повышение...
У меня небольшие проблемы с полным пониманием последних шагов алгоритма факторинга Шора. Учитывая мы хотим вычислить, мы выбираем случайный который имеет порядок .NNNxxxrrr Первый шаг включает в себя настройку регистров и применение оператора Адамара. На втором этапе применяется линейный оператор....
Обычно считается маловероятным, что квантовые компьютеры смогут эффективно решать NP-полные задачи. В классическом случае одним из подходов к решению таких проблем является использование приближенных алгоритмов. Проводились ли какие-либо исследования алгоритмов аппроксимации с использованием...
Меня интересуют примеры проблем, в которых теорема, которая, по-видимому, не имеет ничего общего с квантовой механикой / информацией (например, заявляет что-то о чисто классических объектах), тем не менее, может быть доказана с помощью квантовых инструментов. Обзор квантовых доказательств...
Питер Шор показал, что две из наиболее важных NP-промежуточных задач, факторинг и проблема дискретного логарифмирования, находятся в BQP. Напротив, самый известный квантовый алгоритм для SAT (поиск Гровера) дает только квадратичное улучшение по сравнению с классическим алгоритмом, намекая на то,...
В модели черного ящика проблема определения выходного сигнала машины BPP на входе является приближенной задачей подсчета определения с аддитивной ошибкой 1/3 (скажем).M(x,r)M(x,r)M(x,r)xxxErM(x,r)ErM(x,r)E_r M(x,r) Есть ли похожая проблема для BQP? Этот комментарий Кена Ригана наводит на мысль о...
В вычислительной сложности есть важное различие между монотонными и общими вычислениями, и знаменитая теорема Разборова утверждает, что 3-SAT и даже MATCHING не являются полиномами в модели монотонных булевых схем. Мой вопрос прост: есть ли квантовый аналог для монотонных цепей (или нескольких)?...
Запутывание часто считается ключевым компонентом, который делает квантовые алгоритмы хорошо ... квантовыми, и это можно проследить до состояний Белла, которые разрушают идею квантовой физики как вероятностной модели скрытого состояния. В квантовой теории информации (из моего довольно слабого...
Хорошо известно, что существует порог шума для квантовых вычислений, такой, что ниже этого порога вычисление может быть закодировано таким образом, что оно дает правильный результат с ограниченной вероятностью (с не более чем полиномиальными вычислительными издержками). Этот порог зависит от...
В «Требованиях к квантовым вычислениям» Бартлетт и Сандерс суммируют некоторые из известных результатов для квантовых вычислений с непрерывной переменной в следующей таблице: Мой вопрос состоит из трех частей: Девять лет спустя, можно ли заполнить последнюю ячейку? Если столбец добавлен с...
Я пытаюсь понять связь между изоморфизмом графов и проблемой скрытой подгруппы. Есть хорошая ссылка для