Достижения в области квантовых вычислений привели к разработке новых классических алгоритмов. Известными недавними примерами являются квантово-вдохновенные алгоритмы для линейной алгебры: Квантово-вдохновленный классический алгоритм для систем рекомендаций Квантово-вдохновленные классические...
В настоящее время я ищу хороший справочный материал о нелокальных играх с полезными аспектами квантовой коммуникации. Например, я знаю, что нелокальные игры хороши для более низкой сложности связи, а также для обеспечения безопасности протоколов QKD. То, что я хотел бы знать, - это какие-то большие...
Я читаю статью Харроу, Хасидима и Ллойда « Квантовые алгоритмы для линейных систем уравнений» . На третьей странице этой статьи пишут Далее мы применяем условную гамильтонову эволюцию on| Ψ 0 ⟩ C ⊗ | б ⟩ ...ΣT- 1τ= 0| τ⟩ ⟨ Т|С⊗ ея τTо/ TΣτзнак равно0T-1|τ⟩⟨τ|С⊗еяAτTо/T\sum_{\tau=0}^{T-1}...
Учитывая конечный набор квантовых вентилей , можно ли решить (в теоретическом смысле вычисления), является ли универсальным набором ворот? С одной стороны, «почти все» наборы гейтов являются универсальными, с другой, неуниверсальные наборы гейтов все еще недостаточно понятны (в частности, конечно,...
Для заданного квантового состояния выбрано равномерно случайным образом из набора из N смешанных состояний ρ 1 . , , ρ N , какова максимальная средняя вероятность правильного определения A ?ρAρA\rho_ANNNρ1, , , ρNρ1...ρN\rho_1 ... \rho_NAAA Эту проблему можно превратить в проблему различимости двух...
У меня есть трудности в понимании последних шагов алгоритма AHSP. Пусть абелева группа и е функция , которая скрывает подгруппу H . Пусть G * представляет двойную группу G .GGGfffHHHG∗G∗G^*GGG Вот шаги алгоритма Сначала подготовь государство, .I=1|G|∑g∈G|g⟩|0⟩I=1|G|∑g∈G|g⟩|0⟩\qquad \displaystyle...
Стандартное доказательство того, что BQPSPACE находится в PSPACE, основано на анализе типа игры Савича на интегралах пути. Однако предполагается, что длительность BQPSPACE не должна превышать экспоненциально большую длину. Это верно для PSPACE, но для замкнутых квантовых систем с фиксированным...
Я рассматриваю идеи о точных квантовых алгоритмах. В частности, я рассматриваю вероятные ограничения , который состоит из языков, которые можно точно определить с помощью многочастотных семейств квантовых цепей в произвольном множестве конечных элементов.EQPEQP\mathsf{EQP} Квантовое преобразование...
Мне было интересно, каков список текущих естественных вычислительных проблем, для которых нет никакого известного преимущества в сложности при использовании квантового компьютера. Прежде всего, я думаю, что вычисление расстояния редактирования - это то, для которого самый быстрый из известных...
В универсальных слепых квантовых вычислениях авторы описывают протокол, основанный на измерениях, который позволяет почти классическому пользователю выполнять произвольные вычисления на квантовом сервере, не раскрывая почти ничего о содержании вычислений. В описании протокола авторы упоминают...
Span-программа - это линейно-алгебраический способ задания булевой функции, представленный здесь . Недавно эта модель использовалась, чтобы показать, что метод отрицательного противника обеспечивает точную характеристику (по крайней мере, до ) сложности квантовых...
Хотя экспоненциальное разделение между сложностью квантового запроса с ограниченной ошибкой ( Q ( f)Q(f)Q(f) ) и сложностью детерминированного запроса ( Д ( ф)D(f)D(f) ) или сложностью рандомизированного запроса с ограниченной ошибкой ( R ( f)R(f)R(f) ) известно, они применяются только к...
В Бернштейн и Вазираньте в основополагающей работе «Квантовая теория сложности», они показывают , что - мерное унитарное преобразование может быть эффективно аппроксимировать продукт того , что они называют «рядом с тривиальными севооборотами» и «почти тривиальные фазовыми сдвиги».ddd «Почти...
Существуют ли примеры случаев, когда классическое моделирование квантового алгоритма для задачи превосходит лучший ранее известный классический алгоритм для этой задачи? «Превосходит» не обязательно означает другой класс сложности, это может быть просто лучшее масштабирование. Этот вопрос был...
Мне любопытно, если бы кто-то мог порекомендовать какой-нибудь дополнительный материал для более глубокого понимания статьи: « Некоторые результаты и проблемы о квантовых неравенствах типа Белла - Цирельсон ». В частности, кое-что, что может более подробно рассказать о геометрической интерпретации...
Я читаю превосходный обзорный документ Уотроуса на бумаге по теории квантовой сложности. В нем он заявляет, что было бы удивительно, если бы обнаружилось, что проблема, полная QMA, имеет бессмысленное обещание (т.е. быть языком). Почему это так? Связано ли это с тем фактом, что k-локальная...
Алгоритм Дойча является хорошо известным квантовым вычислением f(0)+f(1)mod2f(0)+f(1)mod2f(0) + f(1)\mod{2} только с одной оценкой fff . Если мы заменим +++ на ⋅⋅\cdot проблема, похоже, станет другой. Мой вопрос: существует ли квантовый алгоритм, вычисляющий значение f(0)⋅f(1)f(0)⋅f(1)f(0)\cdot...
Некоторые из нас читали статью Майкла Нильсена о геометрическом подходе к использованию квантовых нижних границ (вкратце, построение финслеровой метрики на такой, что геодезическое расстояние от I до элемента U является нижней границей на число ворот в квантовой схеме, которая вычисляет U ).SU(...
JBV предложил мне превратить некоторые комментарии в вопрос, так что здесь. Другой вопрос [1] касается применения QM-вычислений. Одним из ответов [2] было «эффективное моделирование квантовой механики». Очевидно, эта идея восходит к ранним работам Фейнмана на эту тему; хотя у меня нет ссылки. Так:...
Хорошо известно, что вычисление недетерминированной машины Тьюринга (NTM) представляется в виде дерева конфигураций, основанного на начальной конфигурации. Любой переход в программе представлен ссылкой «отец-ребенок» в этом дереве. Подобные деревья также могут быть построены для визуализации...