Большая часть литературы по квантовым вычислениям фокусируется на схемотехнической модели. Адиабатические квантовые вычисления основаны не на применении последовательности унитарных операторов, а на изменении зависящего от времени гамильтониана. Я ищу понимание любого из следующего.
- Являются ли адиабатические квантовые вычисления такими же мощными, как схемная модель, или они по своей природе менее мощные?
- Существуют ли классы сложности, конкретно связанные с адиабатическими вычислениями, в отличие от схемной модели?
- Как количественно измерить мощность адиабатических вычислений по сравнению с мощностью модели схемы?
cc.complexity-theory
reference-request
complexity-classes
quantum-computing
quantum-information
ВЗН
источник
источник
Ответы:
Квантовое адиабатическое вычисление эквивалентно стандартному квантовому вычислению - Дорит Ааронов, Вим ван Дам, Джулия Кемпе, Зеф Ландау, Сет Ллойд, Одед Регев
источник
Два быстрых разъяснения:
Адиабатический КК, как правило, «основан на кубитах» так же, как и КК, основанный на схемах - я не знаю, откуда у вас мысль, что это не так! (Хотя можно также использовать цитриты или другие строительные блоки в схемах или адиабатических моделях.)
Как указал Матеус, справедливо известный результат Ааронова и соавт. говорит, что «адиабатический контроль качества эквивалентен стандартному контролю качества». Но этот результат нужно интерпретировать с осторожностью. Это верно, если конечное состояние адиабатического вычисления может быть произвольным, так что, в частности, конечное состояние может кодировать всю историю квантовых вычислений на основе схемы. Однако, если конечное состояние должно быть классическим вычислительным базисным состоянием - как это обычно бывает в алгоритме адиабатической оптимизации(«оригинальный» пример адиабатического контроля качества) - тогда адиабатический контроль качества, безусловно, может быть смоделирован в схемной модели, но обратное не известно и далеко не ясно. Таким образом, с последним предположением, возможно, что адиабатическая оптимизация действительно порождает новый промежуточный класс сложности между BPP и BQP.
источник