Каков класс сложности для квантовых подпрограмм, принимающих в качестве входных данных произвольные квантовые состояния?

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

Я думаю, что вы хотите знать о квантовых аналогах классов функциональных задач. (Спасибо Петру Шору за то, что он указал на это краткое описание в комментарии.)

Абстрактный процесс, который принимает квантовое состояние фиксированного размера в качестве входа и создает квантовое состояние фиксированного размера в качестве выхода, называется квантовым каналом . В вашей ситуации мы не хотим фиксировать входной размер или выходной размер, и поэтому мы, естественно, рассматриваем семейство квантовых каналов как квантовый аналог функций от классических строк до классических строк.

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

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

Что-то, что вас может заинтересовать, это понятие квантового оракула, введенное Ааронсоном и Купербергом в arXiv: quant-ph / 0604056 . Цитирую из их бумаги:

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

Это не дает прямого ответа на ваш вопрос об определении класса сложности, который представляет модель, которую вы описываете. Тем не менее, понятие квантового оракула имеет отношение к теории сложности: в своей работе Ааронсон и Куперберг используют квантовый оракул для разделения QMA и QCMA .

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

$\Phi_n: \mathrm L(\mathcal H_2^{\otimes n}) \to \mathrm L(\mathcal H_2)$состояния с одним кубитом Конечно, квантовый контур - это очень хороший канал; если мы будем говорить о выполнении определенных каналов, которые ограничены в вычислительном отношении, мы можем также просто говорить об однородных семействах квантовых цепей (или, в этом отношении, о любом едином способе реализации карты CPTP). Для хорошей меры схема должна заканчиваться стандартным базовым измерением, если мы хотим сохранить семантику решения чего-либо с ограниченной вероятностью.

$\mathcal L$$\rho'$$\rho \in \mathcal L$$\rho$$\rho'$$\mathcal L$

$\mathcal L$$\mathcal L$(1), это вероятность, которая становится ближе к определенности по мере увеличения размера ввода - и аналогично вероятность отклонения любого состояния, которое может отклонить процедура принятия решения, также должна сходиться к нулю.

Проблемы квантового обещания, которые схема QBQP (для входов размера n ) сможет различить, будут

• $\mathcal H_2^{\otimes n}$
• Для НЕТ экземпляров - смеси чистых состояний, которые ортогональны этому подпространству (или, по крайней мере, все орто-дополнительные состояния, разрешенные обещанием).

$\mathcal L$$\mathcal L^\bot$ решение или обещание задачи, закодированной в квантовых состояниях, с ошибкой, сходящейся к нулю.

Поправьте меня, если я ошибаюсь, но мне кажется, что вы заинтересованы в классе BQP / qpoly . Определение из зоопарка сложности: «Класс задач, решаемых машиной BQP, которая получает в качестве рекомендации квантовое состояние ψn, которое зависит только от входной длины n».

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

Существует также относительно недавняя работа о « характеристике квантового совета », где вы можете найти следующую иерархию:

Я не знаю, какая часть этой информации уже находится в Зоопарке Сложности. Если вам интересна статья, авторы также выступили с докладом об этом.

Править Интересно, под «произвольным» вы подразумеваете состояние, порожденное более общим квантовым процессом, который «унитарная эволюция действует на вычислительных состояниях», как диссипативная эволюция. В этом конкретном последнем случае вы не обладаете большей вычислительной мощностью, чем BQP, как показано в этой статье .

Вот некоторые ссылки на квантовые языки, т. Е. Решение проблем с квантовыми входами. Есть, вероятно, еще много.

1. Квантовая NP и квантовая иерархия -Томоюки Ямаками
2. О сложности квантовых языков - Эльхам Кашефи, Каролина Мура Алвес
3. Эффективный тест для состояний продукта с приложениями к квантовым играм Мерлина-Артура - Арам Харроу, Эшли Монтанаро, DOI: 10.1109 / FOCS.2010.66, Аннотация: arxiv.org/abs/1001.0017v3