Загадка квантовых вычислений: почему BQP — это не «квантовый P
«Стандартное объяснение звучит так: «квантовые компьютеры не решают NP-полные задачи за полиномиальное время». На деле это слишком упрощённая картина. Реальная граница между тем, что квантовые машины делают хорошо, и тем, что они не ломают в принципе, проходит не там, где многие думают. Класс BQP не просто «квантовый P», это отдельный мир, который переплетается с классической … Читать далее