Несколько кубитов: тензорное произведение и 2^n

Откуда у n кубитов берётся 2^n амплитуд — и почему отсюда и мощь, и сложность симуляции.

Тензорное произведение объединяет состояния отдельных кубитов в одно состояние системы; для n кубитов оно имеет 2^n амплитуд.

Два кубита — четыре амплитуды

У одного кубита два базисных состояния: |0>, |1>. У двух кубитов базисных состояний уже четыре: |00>, |01>, |10>, |11> — все комбинации. Состояние системы — вектор из четырёх амплитуд. Чтобы получить его из состояний отдельных кубитов, берут тензорное произведение: перемножают все пары амплитуд.

def tensor(u, v):
    # u, v - векторы амплитуд; результат - все попарные произведения
    return [x * y for x in u for y in v]

q0 = [1+0j, 0+0j]              # |0>
q1 = [0+0j, 1+0j]              # |1>
state = tensor(q0, q1)        # |0> (x) |1> = |01>
labels = ['00', '01', '10', '11']
for lab, amp in zip(labels, state):
    print(lab, '->', amp)

Вывод:

00 -> 0j
01 -> (1+0j)
10 -> 0j
11 -> 0j

Получили ровно |01>: амплитуда 1 при «01», нули в остальных.

Экспоненциальный рост

Добавили кубит — удвоили число амплитуд. 3 кубита: 8 чисел. 10 кубитов: 1024. 50 кубитов: 2^50 — больше квадриллиона комплексных чисел, которые надо хранить, чтобы честно симулировать систему на классическом компьютере. Вот почему симуляция квантовых компьютеров классически так быстро упирается в стену памяти, и почему сам квантовый компьютер потенциально мощен: он «держит» эти 2^n амплитуд физически, не выписывая их.

for n in [1, 5, 10, 20, 30, 50]:
    amps = 2 ** n
    bytes_needed = amps * 16   # complex128 ~ 16 байт
    print('n=%2d  амплитуд=%-16d  память~%.1e байт' % (n, amps, bytes_needed))

Вывод:

n= 1  амплитуд=2                 память~3.2e+01 байт
n= 5  амплитуд=32                память~5.1e+02 байт
n=10  амплитуд=1024              память~1.6e+04 байт
n=20  амплитуд=1048576           память~1.7e+07 байт
n=30  амплитуд=1073741824        память~1.7e+10 байт
n=50  амплитуд=1125899906842624  память~1.8e+16 байт

50 кубитов — это уже около 18 петабайт только на хранение вектора состояния. Поэтому 50–60 кубитов — примерная граница классической симуляции «в лоб».

Как работает под капотом

Ключевая тонкость: не всякое состояние двух кубитов можно записать как тензорное произведение двух одиночных. Те, что можно, называют разделимыми. Те, что нельзя, — запутанными. Именно запутанные состояния занимают «лишнее» пространство и дают квантовому компьютеру его силу. Без запутанности n кубитов хранили бы лишь 2n чисел (по два на кубит), и никакого экспоненциального богатства не было бы.

Частые ошибки

Думать, что 2^n амплитуд = 2^n «параллельных компьютеров». Прочитать их все нельзя.
Считать порядок кубитов неважным: |01> не равно |10>.
Полагать, что любое многокубитное состояние раскладывается в произведение одиночных. Запутанные — нет.

Итог

Состояния кубитов объединяются тензорным произведением; n кубитов = 2^n амплитуд.
Рост экспоненциальный — отсюда и мощь, и предел классической симуляции (~50 кубитов).
Неразделимые состояния называются запутанными.