В своей знаменитой лекции 1982 года нобелевский лауреат Ричард Фейнман высказал идею квантовых вычислений. Он рассуждал, что объем классической информации, необходимой для описания квантовой системы, масштабируется экспоненциально с ее размерами и, таким образом, не может быть эффективно смоделирован классическим компьютером. Действительно, довольно скромная система из 100 квантовых битов уже потребовала бы больше информации для описания, чем все существующие хранилища данных на Земле. Учитывая...

Квантовые вычисления были рассмотрены Фейнманом как ценное средство решения квантовых задач. Распространенным заблуждением при описании мощности квантового компьютера по сравнению с классическим компьютером является то, что квантовые биты могут быть получены в виде суперпозиции экспоненциального числа состояний, чего нельзя достичь с помощью классических битов. Это утверждение, безусловно, верно, но оно не говорит, в частности, какие проблемы могут эффективно решить квантовые компьютеры, в то время как классические компьютеры этого не делают...