В «Вычислительной сложности линейной оптики» ( ECCC TR10-170 ) Скотт Ааронсон и Алекс Архипов утверждают, что если квантовые компьютеры можно эффективно моделировать на классических компьютерах, то иерархия полиномов падает на третий уровень. Задачей мотивации является выборка из распределения, определяемого линейно-оптической сетью; это распределение может быть выражено как перманент конкретной матрицы. В классическом случае все элементы матрицы неотрицательны, и поэтому существует вероятностный алгоритм за полиномиальное время, как показали Марк Джеррум, Алистер Синклер и Эрик Вигода (JACM 2004, doi: 10.1145 / 1008731.1008738). В квантовом случае записи являются комплексными числами. Обратите внимание, что в общем случае (когда записи не должны быть неотрицательными), перманент не может быть аппроксимирован даже в пределах постоянного множителя, согласно классическому результату Valiant 1979 года.
В статье определяется распределение определяемое матрицей A , и проблема выборки.
Вход BosonSampling : матрица Образец: из распределения D A
Использование результата твердости кажется слабым доказательством разделения между классическим и квантовым мирами, поскольку возможно, что класс матриц в конкретной квантовой установке будет иметь особую форму. Они могут иметь сложные записи, но все же могут обладать большой структурой. Следовательно, может существовать эффективная процедура выборки для таких матриц, даже если общая проблема является # P-трудной.
Как использование BosonSampling в статье позволяет избежать легких занятий?
Бумага использует много фона, которого я не имею в квантовой сложности. Учитывая все квантовые люди на этом сайте, я бы очень хотел указатель в правильном направлении. Как бы выдержали аргументы, если бы кто-нибудь обнаружил, что класс комплексных матриц, видимый в конкретной экспериментальной установке, на самом деле соответствует классу распределений, из которых было легко выбирать? Или что-то присуще квантовой системе, которая гарантирует, что этого не произойдет?
источник