Хороший вводный материал по классам квантовой сложности вычислений

10

Я хочу больше узнать о классах вычислительной сложности в контексте квантовых вычислений.

Среда не так важна; это может быть книга, онлайн лекционные заметки или тому подобное. Важнее всего содержание.

Материал должен охватывать основы классов квантовой сложности вычислений и обсуждать сходства, различия и взаимосвязи между ними, а также, возможно, и с классическими классами сложности вычислений.

Я бы предпочел строгое отношение к интуитивному. Авторский стиль не имеет значения.

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

Что касается доступности, я бы, конечно, предпочел материалы, которые не находятся за платным доступом, и их можно найти в Интернете, но это не является строгим требованием.

Что вы порекомендуете?

complexity-theory resource-request Киро
источник
Вообще говоря, получение рекомендаций для класса или других материалов не рассматривается по теме сайта Stack Exchange; но если оставить в стороне этот вопрос, тема вашего поста на самом деле не относится к теме «квантовых вычислений». Обучение понятиям вычислительной сложности лучше подходит для нашего сайта по информатике .
Роберт Картейно
@RobertCartaino Спасибо за отзыв, позвольте мне попытаться ответить на ваши вопросы. Я запрашивал материал для самостоятельного изучения, и запросы на доступ к ресурсам разрешены в рамках параметров . Я сделаю все возможное, чтобы изменить вопрос, чтобы быть по теме.
Киро
1
@MEE За исключением того, что вы не заметили суть этого не по теме - обучение основам вычислительной сложности просто является совпадением с опытом квантовых вычислений. Я называю эту проблему "любимым безалкогольным напитком программистов" . Это проблема информатики, когда добавление «в контексте квантовых вычислений» больше не делает этого более подходящим для данной темы в данном случае. Не важно; У пользователя нет вопросов по этому вопросу, и он просто хочет пойти в другое место, чтобы найти эту информацию. Что бы вы ни решили.
Роберт Картейно
@RobertCartaino хорошо, теперь я понимаю вашу точку зрения, я неправильно понял причину закрытия. Поэтому я хотел бы сейчас отозвать свой вновь открытый голос, но, поскольку это невозможно, я проголосовал за закрытие этого вопроса.
MEE - Восстановить Монику
1
@RobertCartaino «зачатки вычислительной сложности просто совпадают с опытом квантовых вычислений». Я согласен, что «зачатки» совпадают, но я думаю, что вопрос в том виде, в котором он задан в настоящее время, достаточно тематический, поэтому я могу сослаться на примечания к лекциям по квантовые вычисления как ответ. Я согласен, что предыдущая версия действительно была бы « любимым безалкогольным напитком программистов », но я думаю, что это уже решено.
Дискретная ящерица

Ответы:

7

Я думаю, что исследование Джона Уотроуса - отличное место для начала (профессор Уотроус рекомендовал его мне очень давно, и с тех пор меня зацепили!):

J. Watrous. Квантовая вычислительная сложность. Энциклопедия сложности и системной науки, Springer, 2009. arXiv: 0804.3401 [Quant-Ph]

Насколько мне известно, он имеет самые высокие классы сложности на соотношение страниц.

Мне также очень нравятся примечания лекции Барбадоса Скотта Ааронсона 2016 года:

С. Ааронсон (с А. Буландом и Л. Шеффером). Сложность квантовых состояний и преобразований: от квантовых денег к черным дырам. ECCC TR16-109

Санкет менда
источник
3

Я могу порекомендовать лекционные заметки Рональда де Вольфа, используемые для семестрового курса, который он преподает по квантовым вычислениям в контексте голландской программы «Mastermath».

Глава 10 «Квантовая теория сложности» кратко охватывает «классические» классы сложности, но дает достаточно оснований, чтобы говорить о «квантовых» классах сложности и сравнивать их с классическими. Это не охватывает все, но относится к другому материалу для дальнейшего чтения.

Глава 12 «Квантовая сложность связи» также актуальна и носит более технический характер, главным образом потому, что в теории сложности связи есть интересные приложения в квантовых вычислениях.

Дискретная ящерица
источник