Согласно this, я понимаю, что нам нужно 4^n бит для имитации n-кубитного квантового компьютера. Мне было интересно, можно ли имитировать алгоритмы shor на классическом компьютере с коэффициентом 15? Сколько кубитов требуется для коэффициента 15 с использованием алгоритма shor?Сколько кубитов мне нужно для коэффициента 15 с помощью алгоритма shor?
Квантовые компьютеры, подобные классическим, могут иметь n бит, содержащих 2^n разных значений. Алгоритм Шора в «Подпрограмме поиска периодов» использует два регистра, возможно, равные 2n + 1, где n - количество бит, необходимое для представления числа к коэффициенту. Всего вам нужен 4n + 2 кубитов для запуска алгоритма Шора.
Проделана определенная работа на lowering the qubit requirements. Эта реализация работает только с 2n + 3 кубитами для общего номера.
Чтобы ответить на ваш вопрос, вам понадобится 4 классических (или квантовых) бита для представления 15 и, следовательно, захотите 62 кубита с основным алгоритмом (вы, возможно, не будете использовать некоторые). Конечно, есть некоторые обходные пути, и были successfull experimental implementations, которые использовали всего лишь 7 кубитов из-за специальных свойств 15, известных заранее, но которые нельзя использовать для общего числа, заимствованного с алгоритмом Шора.
Когда вы моделируете квантовый компьютер на классическом, вы обычно хотите представить его с пространством состояний, где каждое базовое состояние соответствует одному возможному выходу. Для этого нужны 2^n размерные векторы мнимых чисел, фактическое количество бит зависит от реализации векторов и мнимых чисел.
Для моделирования n-кубитного квантового компьютера вам не нужны 4^n бита. BQP находится в PSPACE. Вы можете имитировать n-кубитные квантовые компьютеры с битами O (n), используя интегралы пути. Но, тем не менее, интегралы пути будут еще медленнее, чем наивное моделирование, которое требует 2^n бит. –