Квантовые компьютеры очень хороши для выборочных распределений, которые мы не знаем, как делать выборки с использованием классических компьютеров. Например, если f - булева функция (от до - 1 , 1 ), которая может быть вычислена за полиномиальное время, то с квантовыми компьютерами мы можем...
Рассмотрим следующую вычислительную задачу: мы хотим отобрать 3-SAT формулу из переменных (вариант: переменных предложений) относительно равномерного распределения вероятностей, при условии, что формула выполнима:NNnNNnммm Q1: может ли это быть эффективно достигнуто с помощью классического...
Я пытаюсь понять связь между изоморфизмом графов и проблемой скрытой подгруппы. Есть хорошая ссылка для
Важная статья 2003 года Childs et al.представил «проблему соединенных деревьев»: проблему, допускающую экспоненциальное квантовое ускорение, которое не похоже ни на одну другую подобную проблему, о которой мы знаем. В этой задаче нам дан экспоненциально большой граф, подобный изображенному ниже,...
В квантовых вычислениях нас часто интересуют случаи, когда группа специальных унитарных операторов G для некоторой d-мерной системы дает либо целую группу SU (d) в точности, либо даже просто приближение, обеспечиваемое плотным покрытием SU (d). Группа конечного порядка, такая как группа Клиффорда...
В «Вычислительной сложности линейной оптики» ( ECCC TR10-170 ) Скотт Ааронсон и Алекс Архипов утверждают, что если квантовые компьютеры можно эффективно моделировать на классических компьютерах, то иерархия полиномов падает на третий уровень. Задачей мотивации является выборка из распределения,...
Этот вопрос является продолжением вопроса об алгоритмах ДНК, заданного Аадитой Мехра . В комментариях Джо Фитцсиммонс сказал, частично: [T] Радиус системы должен масштабироваться пропорционально массе, чтобы избежать этого. Вычислительная мощность масштабируется максимально линейно по массе. Таким...
Равен ли BQP BPP с доступом к оракулу скрытой абелевой
Название более или менее говорит само за себя, но я думаю, я мог бы добавить немного фона и некоторые конкретные примеры, которые меня интересуют. Теоретики описательной сложности, такие как Иммерман и Фагин, охарактеризовали многие из наиболее известных классов сложности с использованием логики....
Хорошо известно, что модульное возведение в степень (основная часть операции RSA) является вычислительно дорогим, и, насколько я понимаю, метод модульного возведения в степень Монтгомери является предпочтительным методом. Модульное возведение в степень также заметно присутствует в алгоритме...
Сегодня в Нью-Йорке и во всем мире отмечается день рождения Христоса Пападимитриу. Это хорошая возможность задать вопрос об отношениях между классом сложности Christos PPAD (и его смежными классами) и квантовыми компьютерами. В своей знаменитой работе 1994 года Пападимитриу представил и...
С некоторыми рандомизированными алгоритмами вы можете дерандомизировать алгоритм, удаляя (при возможной стоимости во время выполнения) использование случайных битов и максимизируя некоторую нижнюю границу для цели (обычно вычисляемую с использованием факта, что теоремы об ожидаемой...
Хотя теорема Адлемана показывает, что , мне неизвестна литература, исследующая возможное включение . Какие теоретически сложные последствия будет иметь такое включение?B Q P ⊆ P / полиB P P ⊆ P / полиBPP⊆P/poly\mathsf{BPP} \subseteq \mathsf{P}/\text{poly}B Q P ⊆ P / полиBQP⊆P/poly\mathsf{BQP}...
Два связанных вопроса об ограниченных вычислениях глубины: 1) Предположим, что вы начинаете с n битов, и начинаться с бита i может быть 0 или 1 с некоторой вероятностью p (i) независимо. (Если это упрощает задачу, мы можем предположить, что все p (i) s равны 0,1 или 1/2.или даже то, что все они...
Читая некоторые недавние темы о квантовых вычислениях ( здесь , здесь и здесь ), я вспоминаю интересный вопрос о мощности некоторой машины, сохраняющей ℓpℓp\ell_p норму. Для людей, работающих в области теории сложности, которые идут на квантовую сложность, хорошим вступительным текстом является...
Обратимые вычисления - это вычислительная модель, которая допускает только термодинамически обратимые операции. В соответствии с принципом Ландауэра, который гласит, что стирание небольшого количества информации высвобождает джоулей тепла, это исключает переходные функции, которые не являются...
В Википедии перечислены четыре проблемы, которые есть в но предположительно находятся вне : целочисленная факторизация; Дискретный логарифм; Моделирование квантовых систем; Вычисление полинома Джонса на определенных корнях единства.PB Q PВQпBQPппP Есть ли еще такие...
В своей статье 1995 года « Алгоритмы полиномиального времени для первичной факторизации и дискретных логарифмов на квантовом компьютере» Питер У. Шор обсуждает усовершенствование порядка упорядочения своего алгоритма факторизации. Стандартные выходы алгоритма r′r′r' , делитель порядка rrr из xxx по...
В квантовой теории информации расстояние между двумя квантовыми каналами часто измеряется с использованием алмазной нормы. Существует также ряд способов измерения расстояния между двумя квантовыми состояниями, таких как расстояние следа, точность и т. Д. Изоморфизм Ямиолковского обеспечивает...
Моя любимая теорема в теории сложности - это теорема об иерархии времени. Однако это было сделано в 1965 году. Тогда я хотел узнать, есть ли что-нибудь подобное для квантовых вычислений. Кроме того, если нет, что люди / группы работают в этом...