Что я должен прочитать, чтобы понять эту проблему?
Мощность квантовых цепей малой глубины. Является ли ? Другими словами, может ли «квантовая» часть любого квантового алгоритма быть сжата до глубины полилога (n), если мы хотим выполнить классическую постобработку за полиномиальное время? (Известно, что это верно для алгоритма Шора.) Если это так, то создание квантового компьютера общего назначения было бы намного проще, чем принято считать! Между прочим, нетрудно разделить оракула между B Q P и B P P B Q N C, но вопрос в том, есть ли какая-то конкретная функция, "создающая экземпляр" такого оракула. - Скотт Ааронсон http://www.scottaaronson.com/writings/qchallenge.html
источник