Существуют ли примеры случаев, когда классическое моделирование квантового алгоритма для задачи превосходит лучший ранее известный классический алгоритм для этой задачи? «Превосходит» не обязательно означает другой класс сложности, это может быть просто лучшее масштабирование. Этот вопрос был...
Недавно я подумал об «импорте» некоторых связанных с физикой вопросов в квантовую CS: Понятие явления закона площади в гамильтоновых системах обычно означает локальный гамильтониан на некоторой решетке, у основного состояния которого есть свойство, при котором запутывание любой замкнутой области...
В сложности дерева решений для булевой функции очень хорошо известный метод нижней границы состоит в том, чтобы найти (приблизительный) многочлен, который представляет функцию. Патури дал характеристику для симметричных булевых (частичных и полных) функций в терминах величины, обозначаемой...
Рассмотрим гильбертово пространство ЧАСзнак равноЧАС1⊗ ⋯ ⊗ЧАСNH=H1⊗⋯⊗HnH = H_1 \otimes \dots \otimes H_n, Неописуемая основа продукта (UPB) - это набор векторов продукта|vя⟩ = |v1я⟩ ⊗ ⋯ ⊗ |vNя⟩|vi⟩=|vi1⟩⊗⋯⊗|vin⟩\vert v_i \rangle = \vert v_i^1 \rangle \otimes \dots \otimes \vert v_i^n \rangle такой...
Определите, что вычислительная модель MPostBQP идентична PostBQP, за исключением того, что мы разрешаем полиномиально много измерений в кубитах перед последующим выбором и окончательным измерением. Можем ли мы привести какие-либо доказательства того, что MPostBQP более мощный, чем PostBQP?...
Поскольку ответа не было дано, был установлен флаг с просьбой преобразовать этот вопрос в вики сообщества. Комментарии Аарона Стерлинга, Сашо Николова и Вора были объединены в следующую резолюцию, которая открыта для обсуждения в вики сообщества: Решено: Что касается классических алгоритмов,...
Хорошо известно, что сложность квантового запроса с ограниченной функцией функции равна . Теперь вопрос в том, что если мы хотим, чтобы наш квантовый алгоритм работал успешно для каждого входа с вероятностью а не обычным . Теперь с точки зрения какие будут соответствующие верхние и нижние...
Существует ли известное семейство групповых действий с назначенным элементом в наборе, над которым выполняется действие, где известно, как эффективно \: выборка (по существу, равномерно) из групп, вычисление обратных операций, вычисление групповых операций и вычисление групповых действий \: и нет...
Большая часть литературы по квантовым вычислениям фокусируется на схемотехнической модели. Адиабатические квантовые вычисления основаны не на применении последовательности унитарных операторов, а на изменении зависящего от времени гамильтониана. Я ищу понимание любого из следующего. Являются ли...