Изучаем Q#. Делаем реализацию биноминального распределения

Биномиальное распределение с параметрами n и p в теории вероятностей — распределение количества «успехов» в последовательности из n независимых случайных экспериментов, таких, что вероятность «успеха» в каждом из них постоянна и равна p.

Рассмотрим случай, когда p=0.5 — это делается только для упрощения примера.

В этом случае, согласно теории, вероятность выпадения исхода k на вероятностном пространстве из целых чисел равно P(k)=C(k,n)/2**n, где C(k,n) = n!/(k!(n-k)!) — коэффициент бинома Ньютона.

Поставим перед собой цель — сформировать в массиве кубитов, который мы будем рассматривать как регистр из нескольких кубитов, состояние SUM SQRT(C(k,n))|k>

Из теории вероятности имеем, что если x1,…,xn — конечная последовательность независимых случайных величин, и имеющих одинаковое распределение Бернулли с параметром p, то есть при каждом i=1..n величина 1 («успех») и 0 («неудача») с вероятностями p и q=1-p соответственно, тогда случайная величина y=x1+…+xn имеет биноминальное распределение с параметрами n и p.

В квантовых вычислениях, мы имеем факт, что применение трансформации Адамара H к кубиту в состоянии |0> даёт нам его в равновероятном состоянии для исходов |0> и |1>, то есть в состоянии |0>+|1>

Воспользуемся этими фактами, и сформируем значение нужного нам регистра, как «сумму значений» n независимых кубитов, находящихся в состоянии |0>+|1>

Таким образом алгоритм прост:

1. Берём несколько кубитов в состоянии |0> (регистр), для хранения значения в диапазоне [0..n] в двоичном представлении,

2. Берём n кубитов xi в состоянии |0>

3. Применяем преобразование Адамара к xi

4. Суммируем xi с накоплением суммы в регистре (да, нам потребуется реализовать аналог двоичной арифметики, но на кубитах)

5. Очищаем и освобождаем кубиты xi

В результате данных преобразований, получаем регистр в состоянии SUM SQRT(C(k,n))|k>

Для получения конкретного значения с биноминальным распределением, нам надо коллапсировать регистр (то есть провести измерение значений его кубитов)
и преобразовать полученный вектор из |0> и |1> в целое число (двоичное представление числа)

Перейдём к кодированию с помощью QDK от Microsoft

1. Воспользуемся инструкциями с сайта microsoft.com по установки QDK под VS Code (https://learn.microsoft.com/ru-ru/training/modules/qsharp-create-first-quantum-development-kit/2-install-quantum-development-kit-code).

2. Создадим новый проект (или клонируйте мой https://github.com/dprotopopov/qbinom)

3. Добавим

   3.1. Трансформацию «инкремента регистра»

   /// Реализация операции инкремента, то есть трансформации |k> -> |k+1>      operation Inc(register: Qubit[]) : Unit is Ctl {         let n = Length(register);         for idx in 1..n {             Controlled X(register[0..n-idx-1], register[n-idx]);         }     }

   3.2. Трансформацию «сумма битов»

   /// Реализация операции суммирования, то есть трансформации |abcde...> -> |a+b+c+d+e+...>      /// Это не самая эффективная реализация, но самая простая для кодирования      operation Sum(qubits: Qubit[], register: Qubit[]) : Unit {         for q in qubits {             Controlled Inc([q], register);         }     } 

   3.3. И, соответственно, операцию заполнения регистра суммой значений случайных битов

   /// Реализация операции биноминального распределения, то есть n -> SUM SQRT(C(k,n))|k>      operation Binom(n: Int, register: Qubit[]) : Unit {         use qubits = Qubit[n] {             ApplyToEach(H, qubits);             Sum(qubits, register);             ResetAll(qubits);         }     }

4. Создадим пример для проверки

   4.1. то есть несколько раз повторим эксперимент

   4.1.1. Заполним регистр из кубитов состоянием SUM SQRT(C(k,n))|k>

   4.1.2. Коллапсируем регистр, и получим конкретное значение k

   4.1.3. Запишем, что нам выпал исход k

   4.2. Выведем статистику выпадения исходов

        // Параметры нашего примера          let n = 10;         let tests = 1000;         let k = BitSizeI(n+1);          use register = Qubit[k] {              // Аллокируем массив для подсчёта количества исходов экспериментов              mutable arr = [0, size = n + 1];              // Повторям эксперимент несколько раз, с подсчётом колличества полученных исходов              for _ in 1..tests {                  // Установим в register состояние SUM|k>                  Binom(n, register);                   // Для получения конкретного значения необходимо измерить значения кубиртов в регистре                  // и преобразовать полученный результат (вектор из |0> или |1>) в целое  число                  let results = ForEach(M, register);                 let i = ResultArrayAsInt(results);                  // Добавим полученное значение в счётчик                  set arr w/= i <- arr[i] + 1;                  // Очищаем кубиты после использования                  ResetAll(register);             }              // Выводим полученную таблицу частот               for s in arr {                 let p = 100 * s / tests;                 Message($"{p}%");             }         } }

namespace qbinom {      open Microsoft.Quantum.Canon;     open Microsoft.Quantum.Intrinsic;     open Microsoft.Quantum.Arrays;     open Microsoft.Quantum.Math;     open Microsoft.Quantum.Measurement;     open Microsoft.Quantum.Convert;          /// Реализация операции инкремента, то есть трансформации |k> -> |k+1>     operation Inc(register: Qubit[]) : Unit is Ctl {         let n = Length(register);         for idx in 1..n {             Controlled X(register[0..n-idx-1], register[n-idx]);         }     }      /// Реализация операции суммирования, то есть трансформации |abcde...> -> |a+b+c+d+e+...>     /// Это не самая эффективная реализация, но самая простая для кодирования     operation Sum(qubits: Qubit[], register: Qubit[]) : Unit {         for q in qubits {             Controlled Inc([q], register);         }     }      /// Реализация операции биноминального распределения, то есть n -> SUM SQRT(C(k,n))|k>     operation Binom(n: Int, register: Qubit[]) : Unit {         use qubits = Qubit[n] {             ApplyToEach(H, qubits);             Sum(qubits, register);             ResetAll(qubits);         }     }      @EntryPoint()     operation Main() : Unit {         Message("Hello quantum world!");          // Параметры нашего примера         let n = 10;         let tests = 1000;           let k = BitSizeI(n+1);         use register = Qubit[k] {              // Аллокируем массив для подсчёта количества исходов экспериментов             mutable arr = [0, size = n + 1];              // Повторям эксперимент несколько раз, с подсчётом колличества полученных исходов             for _ in 1..tests {                 // Установим в register состояние SUM SQRT(C(k,n))|k>                 Binom(n, register);                   // Для получения конкретного значения необходимо измерить значения кубиртов в регистре                 // и преобразовать полученный результат (вектор из |0> или |1>) в целое  число                 let results = ForEach(M, register);                 let i = ResultArrayAsInt(results);                  // Добавим полученное значение в счётчик                 set arr w/= i <- arr[i] + 1;                  // Очищаем кубиты после использования                 ResetAll(register);             }              // Выводим полученную таблицу частот              for s in arr {                 let p = 100 * s / tests;                 Message($"{p}%");             }         }     } } 

Итог

PS C:\Projects\qbinom> dotnet run
Hello quantum world!
0%
1%
4%
11%
20%
25%
20%
11%
3%
1%
0%

Похоже? Мне кажется, что — да.

Ссылки

https://github.com/dprotopopov/qbinom