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

Star Trek. The Next Generation. Q Who?

Star Trek. The Next Generation. Q Who?

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

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

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

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

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

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

  1. Воспользуемся инструкциями с сайта microsoft.com по установки QDK под VS 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 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 C (k, n)|k>

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

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

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

.

        // Параметры нашего примера

        let n = 10;

        let tests = 1000;

        let k = BitSizeI(n);

        use register = Qubit[k] {

            // Аллокируем массив для подсчёта количества исходов экспериментов

            mutable arr = [0, size = n + 1];

            // Повторям эксперимент несколько раз, с подсчётом колличества полученных исходов

            for _ in 1..tests {

                // Установим в register состояние SUM 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}%");

            }

        }

    }

Полный текст кода

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 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);
        use register = Qubit[k] {

            // Аллокируем массив для подсчёта количества исходов экспериментов
            mutable arr = [0, size = n + 1];

            // Повторям эксперимент несколько раз, с подсчётом колличества полученных исходов
            for _ in 1..tests {
                // Установим в register состояние SUM 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

© Habrahabr.ru