Версия уценки, если вы ненавидите макет Medium: https://hirasawakinko.github.io/chika_home/toward_science/Qubit%20Matrix%20Chain%20Multiplication%20in%20O(n)/

Ориентир

Основы

Любая матрица может быть выражена в виде суммы операторов Паули.

Оператор Паули — набор операций в квантовых вычислениях. Они обозначаются как

I, X, Y, Z

В их матричной форме

I := [ 1  0 ]
     [ 0  1 ]
X := [ 0  1 ]
     [ 1  0 ]
Y := [ 0 -i ]
     [ i  0 ]
Z := [ 1  0 ]
     [ 0 -1 ]
The "i" in Y is the "i" of imaginary number.

Допустим, есть матрица A, к ней можно отнести разложение Паули.

Pauli decomposition:
matrix A = summation(i)[ coefficient i * pauli{I, X, Y, Z} ]
for example 4I + 2Y + 7X - 4Z + 3Y ...

Затем вы можете выполнить тензорное произведение, чтобы увеличить матрицу.

I tensor X
= [ 1  0 ] tensor X
  [ 0  1 ]
= [ X  0 ]
  [ 0  X ]
= [ 0  1  0  0 ]
  [ 1  0  0  0 ]
  [ 0  0  0  1 ]
  [ 0  0  1  0 ]

А правила умножения таковы:

I* == + *
*I == + *
XY ==  iZ
YX == -iZ
YZ ==  iX
ZY == -iX
ZX ==  iY
XZ == -iY

Вы можете попробовать умножить их вручную, чтобы убедиться, что они действительны.

И очевидно, что эти символические правила действительны, вы можете избежать умножения матриц и просто выполнять манипуляции со строками.

IX -> X
XY -> Z
YZ -> X
...

Например:

matrix A = 4I + 2Y + 7X - 4Z + 3Y
matrix A * Pauli X
= (4I + 2Y + 7X - 4Z + 3Y) * X
= (4A + 2Z + 7I - 4Y + 3Z)

Я пропустил все эти изменения коэффициентов. Не потому, что вам это не нужно, а просто потому, что коэффициент не является главной задачей в этом исследовании.

Текущее состояние

Есть много библиотек Python, которые могут выполнять такие символьные квантовые вычисления, однако недостаточно быстро.

Алгоритм, который они используют, наивен, что приводит к большому избыточному времени выполнения. Например, ОпенФермион.

Некоторые даже не используют символьные вычисления. Это просто ввод строки в матрицу, а затем выполнение умножения матрицы на вектор. Например Qiskit, Qulacs. Что делает их абсурдно медленными в некоторых из самых простых задач.

Например это.

(*) represent tensor product
matrix A 
= I (*) I (*) I (*) I (*) I (*) I (*) 
  I (*) I (*) I (*) I (*) I (*) I (*) 
  I (*) I (*) I (*) I (*) I (*) I (*) 
  I (*) I (*) I (*) I (*) I (*) I (*) 
  I (*) I (*) I (*) I (*) I (*) I (*) 
  I (*) I (*) I (*) I (*) I (*) I (*) 
  I (*) I (*) I (*) I (*) I (*) I (*) 
  I (*) I (*) I (*) I (*) I (*) I (*) 
  I (*) I (*) I (*) I (*) I (*) I (*) 
  I (*) I (*) I (*) I (*) I (*) I (*) 
  I (*) I (*) I (*) I (*) I (*) I (*) 
  I (*) I (*) I (*) I (*) I (*) I (*) 
  I (*) I (*) I (*) I (*) I (*) I (*) 
  I (*) I (*) I (*) I (*) I (*) I (*) 
  I (*) I (*) I (*) I (*) I (*) I (*) 
  I (*) I (*) I (*) I (*) I (*) I (*) 
  I (*) I (*) I (*) I (*) I (*) I (*) 
  I (*) I (*) I (*) I (*) I (*) I (*) 
  I (*) I (*) I (*) I (*) I (*) I (*) 
  I (*) I (*) I (*) I (*) I (*) I (*)
Now we multiply it by
matrix B 
= X (*) X (*) X (*) X (*) X (*) X (*) 
  X (*) X (*) X (*) X (*) X (*) X (*) 
  X (*) X (*) X (*) X (*) X (*) X (*) 
  X (*) X (*) X (*) X (*) X (*) X (*) 
  X (*) X (*) X (*) X (*) X (*) X (*) 
  X (*) X (*) X (*) X (*) X (*) X (*) 
  X (*) X (*) X (*) X (*) X (*) X (*) 
  X (*) X (*) X (*) X (*) X (*) X (*) 
  X (*) X (*) X (*) X (*) X (*) X (*) 
  X (*) X (*) X (*) X (*) X (*) X (*) 
  X (*) X (*) X (*) X (*) X (*) X (*) 
  X (*) X (*) X (*) X (*) X (*) X (*) 
  X (*) X (*) X (*) X (*) X (*) X (*) 
  X (*) X (*) X (*) X (*) X (*) X (*) 
  X (*) X (*) X (*) X (*) X (*) X (*) 
  X (*) X (*) X (*) X (*) X (*) X (*) 
  X (*) X (*) X (*) X (*) X (*) X (*) 
  X (*) X (*) X (*) X (*) X (*) X (*) 
  X (*) X (*) X (*) X (*) X (*) X (*) 
  X (*) X (*) X (*) X (*) X (*) X (*)

Как вы думаете, сколько времени это займет? Я могу сделать это под вторым в одиночку, но их? Вероятно, потребуется более 1 года, чтобы вывести ответ.

Для тензорного произведения вы умножаете вещи побитово. Что касается I*X -> X, результатом является просто сама матрица B. Прохладный?

Наивное кодирование

Итак, как насчет наивного кодирования OpenFermion? Ну, они почти поняли, но не совсем. Скажем, вы умножаете две матрицы A и B:

matrix A  |  matrix B
= I Y     |  = X Z
+ Y X     |  + Y Y
+ X Y     |  + X Y
+ Z X     |  
+ Y Z     |

Точно так же, как то, что вы сделаете с (x + 3)(x + 2), вы сделаете то же самое с этой матрицей.

first lable them...
matrix A  |  matrix B
= I Y     |  = X Z  (b1)
+ Y X     |  + Y Y  (b2)
+ X Y     |  + X Y  (b3)
+ Z X     |  
+ Y Z     |
matrix A * matrix B
= matrix A * b1 + matrix A * b2 + matrix A * b3 ...

Таким образом, вы будете выполнять побитовое умножение следующим образом:

      X Z (b1)    Y Y  (b2)    X Y  (b3)  
    matrix A    matrix A     matrix A     
    = I Y       = I Y        = I Y        
    + Y X    +  + Y X    +   + Y X      
    + X Y       + X Y        + X Y        
    + Z X       + Z X        + Z X        
    + Y Z       + Y Z        + Y Z
                     Y Y  (b2)    X Y  (b3)   
                   matrix A     matrix A      
                   = I Y        = I Y         
    = something +  + Y X    +   + Y X   
                   + X Y        + X Y         
                   + Z X        + Z X         
                   + Y Z        + Y Z
                     X Y  (b3)  
                   matrix A     
                   = I Y        
    = something +  + Y X    
                   + X Y      
                   + Z X        
                   + Y Z

На каждом шаге вы распространяете одну строку матрицы B на все строки матрицы A.

matrix A
= I Y * X Z (b1)
+ Y X * X Z (b1)
+ X Y * X Z (b1)
+ Z X * X Z (b1)
+ Y Z * X Z (b1)

Такой подход кажется законным, но абсолютно точно мы можем сделать лучше и быстрее.

Что я сделал в SymPauli

Как вы можете видеть в драгоценном разделе, мы должны вызвать матрицу A несколько раз, чтобы выполнить полный процесс умножения матриц. Отсюда мы знаем, что матрица A в принципе не изменится в любом случае.

Также не столь очевидным является то, что оператор Паули обладает свойством циклической группы. Это означает, что мы можем полностью предсказать результат.

Когда вы объединили подобные термины, то есть 2y + 3y +7x = 5y + 7x, в пуле остались только уникальные тензоры Паули.

Допустим, у вас есть I X Y Z, по-прежнему игнорируя коэффициент.

  (I X Y Z) * X
= (X I Z Y)

(I + X + Y + Z) — это простейшая форма самой себя, вы не можете ее больше упростить. После умножения чего-либо результат остается в самой простой форме. И вы должны заметить, что здесь умножение буквально означает перестановку.

  (I X Y Z) * Y
= (Y Z I X)
  (I X Y Z) * Z
= (Z Y X I)

Вернитесь к матрице A * b1 :

  X Z (b1)
matrix A
= I Y
+ Y X
+ X Y
+ Z X
+ Y Z

Далее сосредоточимся на левых операторах Паули:

  X (b1)
matrix A
= I
+ Y
+ X
+ Z
+ Y

По предыдущему правилу мы уже знаем ответ.

  (I X Y Z) * X
= (X I Z Y)
  X (b1)
matrix A
= I -> X
+ Y -> Z
+ X -> I
+ Z -> Y
+ Y -> Z

Здесь вы видите некоторое дублирование. то есть мы уже знаем, что X*Z -> Y, так почему мы все еще проверяем его построчно? Это просто пустая трата времени.

Вот вам и реляционная структура данных.

Реляционная структура данных и суперпараллелизм

Это одна часть матрицы A. И мы собираемся применить ко всем им единый оператор перестановки.

Только текст

matrix A
= I * X
+ Y * X
+ X * X
+ Z * X
+ Y * X

Здесь я использую реляционную структуру данных для выполнения алгоритма суперпараллелизма.

У вас есть шрифт и бэкэнд для этой структуры данных. И вы сопоставляете каждое значение шрифта с бэкендом, чтобы его значение относилось к тому, что находится сзади.

front and back
fontend   backend
   I      0 = I
   Y      1 = X
   X      2 = Y
   Z      3 = Z
   Y
mapping front to back
fontend   backend
    0      0 = I
    2      1 = X
    1      2 = Y
    3      3 = Z
    2

Когда вы выполняете умножение, мы делаем это на бэкенде, а не на интерфейсе. После этого вы считываете значения frontend из backend.

multiplying X
fontend   backend
    0      0 = I
    2      1 = X     * X
    1      2 = Y
    3      3 = Z
    2
multiplied X
fontend   backend
    0      0 = X
    2      1 = I
    1      2 = Z
    3      3 = Y
    2
multiplied X
fontend   backend
X < 0       0 = X
Z < 2       1 = I
I < 1       2 = Z
Y < 3       3 = Y
Z < 2

После считывания вы можете сбросить матрицу A в исходное состояние исключительно путем сброса бэкенда.

reset backend
fontend   backend
I < 0       0 = I
Y < 2       1 = X
X < 1       2 = Y
Z < 3       3 = Z
Y < 2

Итак, мы вернулись к исходной матрице A. Итак, вы можете выполнить следующее умножение (также потому, что оно требует исходного), а именно:

  Y Y  (b2)
matrix A
= I Y
+ Y X
+ X Y
+ Z X
+ Y Z

Цепное умножение

Последним шагом в последнем разделе мы сбрасываем бэкэнд. Однако это не требуется, если вы собираетесь выполнять цепное умножение, т.е. A * b * c * d * e * ..., {b c d e} пишутся строчными буквами и являются однострочными (не линейной комбинацией).

fontend   backend
   I       0 = I
   Y       1 = X   * b * c * d * e * ...
   X       2 = Y
   Z       3 = Z
   Y

Не сбрасывая серверную часть после каждого хода умножения, вы можете выполнять цепочку действий, использующих драгоценное состояние в качестве отправной точки для следующего действия. Таким образом, вы можете сохранить начальное сопоставление и прочитать результат с этим начальным сопоставлением.

initial mapping
fontend   backend
    0      0 = I
    2      1 = X  * b * c * d * e * ...
    1      2 = Y
    3      3 = Z
    2
after all multiplications
fontend   backend
    0      0 = ?
    2      1 = ?
    1      2 = ?
    3      3 = ?
    2
you can read the result by the very same initial mapping
fontend   backend
? < 0      0 = ?
? < 2      1 = ?
? < 1      2 = ?
? < 3      3 = ?
? < 2

Масштабируемость

Эта реляционная структура данных и алгоритм являются параллельными. Даже не при параллельном программировании, вы все равно сможете получить значительное ускорение.

Из-за того, что все манипуляции с данными выполняются исключительно на бэкенде, а бэкэнд всего лишь константа, т.е. size of backend array = 4 Pauli Operator * N qubits, сложность O(n). С таким размером вы можете легко упаковать его в кеш ЦП и делать все с беспрецедентной скоростью.

Это начальное состояние 6-кубитного бэкэнда, и у вас есть одна строка вашей матрицы (I I I I I I):

qubits  0  1  2  3  4  5
0 = I   0  0  0  0  0  0
1 = X   1  1  1  1  1  1
2 = Y   2  2  2  2  2  2
3 = Z   3  3  3  3  3  3
my row : (I I I I I I) -> (0 0 0 0 0 0)

Например, умножить на (X Y Z Y Z X):

qubits  0  1  2  3  4  5
0 = I   1  2  3  2  3  1
1 = X   0  3  2  3  2  0
2 = Y   3  0  1  0  1  3
3 = Z   2  1  0  1  0  2

Вам просто нужно посмотреть на ту же позицию стола, чтобы узнать, какой она становится сейчас.

my row : (I I I I I I) -> (1 2 3 2 3 1) -> (X Y Z Y Z X)

Та же таблица применяется ко всем строкам. Умножь один раз, прочитай много. Поскольку оператор Паули является циклическим, точно так же, как вы вращаете аналоговые часы (они поставляются с булавками часов и минут), внутреннее относительное положение 10 часов, 4 часов и других не изменится.

Во-вторых, все является суммированием, и порядок суммирования не имеет значения из-за коммутативности сложения. Таким образом, вы можете разделить все это на подпроцессы и суммировать их в последнее время.

Кроме того, тензорное произведение оператора Паули выполняется побитово, так что вы можете разбить его на более мелкие подзадачи.

Кроме того, небольшой размер серверной части делает коммуникационные затраты очень низкими.

Но приходит с большим штрафом

Скорость чтения и записи этой структуры данных является фатальной. Так как вам нужно сначала сопоставить информацию о внешнем интерфейсе с бэкэндом, а после этого вы должны сделать обратное. Такая стоимость трансляции очень дорогая, для матрицы 30000 rows of Pauli tensor * 40 qubits она составляет примерно от 0,1 до 0,01X производительности чтения/записи.

Однако в ситуации с цепным умножением R/W выполняется только в начале и в конце, умножая цепочку 30000 rows of Pauli tensor * 40 qubits на матрицу того же размера, но в линейной комбинации, эта структура данных обеспечивает производительность от 30000X до 40000X.

До сих пор я игнорировал коэффициенты, в основном сосредоточенные на операторах Паули. Все сравнение, указанное выше, это:

conventional with coefficient 
VS 
new without coefficient

Так что да, это просто тест BS, и к нему нельзя относиться серьезно. Но это потому, что нет места для улучшения, когда мы включаем коэффициенты в расчет. Максимум 10-кратное ускорение в том же масштабе с использованием Python, и я уже использую Numpy для работы с тяжелым коэффициентом листания. Но отказ от использования Numpy на самом деле не так уж и далек, примерно в 5–6 раз.

Итак, вы видите, что без коэффициентов, 40000X. Да коэффициенты, 10Х. Проклятые коэффициенты отстой.

Заключение

Я самостоятельно изобрел новый алгоритм, использующий реляционную структуру данных, и фантомно произвел революцию в состязательном подходе в 40 000 раз по тому же масштабу, но это только тогда, когда я игнорирую всю вычислительную работу для коэффициентов. С коэффициентами 10X - это максимум, который я могу получить. Итак, да здравствуют символические вычисления, черт возьми, числовые вычисления.

Гитхаб



GitHub — hirasawakinko/SymPauli: символическое умножение операций Паули
Вы не можете выполнить это действие в данный момент. Вы вошли в другую вкладку или окно. Вы вышли на другой вкладке или…github.com



Связанный:

1. Символические квантовые вычисления меняют правила игры, превращая проблему O(2^n) в проблему O(log2 n) («https://hirasawakin.medium.com/symbolic-quantum-computation-is-a-game-changer -превратить-о-2-н-проблему-в-о-лог2-н-проблему-5654307a5255")

2. Cracking Qubit Operator Representation of Any Matrix (https://hirasawakin.medium.com/cracking-qubit-operator-representation-of-any-matrix-4e0451a4c7d7)

3. Нерепрезентативность моделирования химии или физики в области квантовых вычислений («https://hirasawakin.medium.com/unrespresentitivity-of-chemistry-or-physiscs-simulation-in-the-realm-of-Quantum-computing- 51ecd5348d30")

4. Оператор Паули, коммутатор, сфера Блоха, бинарная операция и циклическая группа -1343аб18ф038»