Мера вычислительных ресурсов, необходимых для моделирования, которая удваивается с каждым добавленным кубитом.Сложность в контексте квантовых вычислений относится к экспоненциальному росту вычислительных ресурсов, необходимых для моделирования квантовой системы на классическом компьютере. С добавлением каждого кубита пространство состояний удваивается, поэтому для полного описания системы из n кубитов требуется 2^n комплексных амплитуд. Это экспоненциальное масштабирование является фундаментальной причиной того, почему квантовые компьютеры так трудно моделировать классически — даже несколько сотен кубитов превышают память любой мыслимой классической машины. Эта сложность является одновременно вызовом и возможностью: она делает квантовые системы трудными для понимания, но также лежит в основе потенциала квантовых компьютеров решать задачи, неразрешимые для классических компьютеров.
Экспоненциальная сложность квантового моделирования была впервые сформулирована Ричардом Фейнманом в 1982 году, который предложил квантовые компьютеры как способ эффективного моделирования квантовых систем. Формальная теоретико-сложностная основа была разработана Дэвидом Дойчем и другими в 1980–1990-х годах.
Сложность возникает из-за квантовой запутанности и суперпозиции. Классическое моделирование должно отслеживать амплитуды вероятностей всех возможных состояний, которые растут как 2^n. Для n=50 это около 10^15 амплитуд, что уже превышает практическую классическую память. Квантовые компьютеры используют эту сложность, манипулируя этими амплитудами напрямую с помощью квантовых вентилей, выполняя операции, которые потребовали бы экспоненциально много классических шагов. Сложность также проявляется в трудности исправления ошибок, так как квантовые состояния хрупки и требуют избыточности для защиты от декогеренции.
Эта сложность является основой квантового преимущества в моделировании молекул, материалов и других квантовых систем, с приложениями в открытии лекарств, криптографии и оптимизации.
Квантовому компьютеру всего с 300 кубитами потребовалось бы больше классических битов для моделирования, чем атомов в наблюдаемой Вселенной.



















