Изучаем Q#. Орёл или решка? / Хабр

Про кубит и про Дирака

Как и бит, кубит допускает два собственных состояния, обозначаемых |0> и |1> (обозначения Дирака), но при этом может находиться и в их суперпозиции.

В общем случае его волновая функция имеет вид A|0>+B|1>, где A и B называются амплитудами вероятностей и являются комплексными числами, удовлетворяющими условию |A|^2+|B|^2=1 (но это не обязательно соблюдать при записи - всегда подразумевается, что происходит нормирование величин).

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

Вероятности получить каждое из них равны соответственно |A|^2 и |B|^2.

Как правило, при измерении состояние кубита необратимо разрушается, чего не происходит при измерении классического бита.

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

Но как нам задать нужное состояние кубита, то есть с заранее заданными значениями A и B ?

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

Ну а мы ограничимся в данном примере операциями H и Controlled X.

Как будем решать проблему?

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

Предположим у нас есть регистр (массив) кубитов, находящийся в состоянии SUM |k> где k=0..N-1 - то есть при попытке измерения мы получим значение из диапазона 0..N-1 с одинаковой вероятностью.

Если мы разделим множество 0..N-1 на два множества A и B то можем сделать функцию f(k)={0, if k in A, и 1, if k in B}. Очеводно, что для произвольно выбранного значения k выполнено P(f(k)==0)=|A|/N и P(f(k)==1)=|B|/N и при этом |A|+|B|=N.

А как проще всего разделить 0..N-1 на два подмножества - конечно пороговой функцией fw(k)={0, if k lt w, и 1, if k ge w} или, в другой записи fw(k)=SIGN(w-k-1), где SIGN(x)={0 if x ge 0, 1 if x lt 0}

При этом p=P(0)=w/N и q=P(1)=(N-w)/N

Рассмотрим классическую схему построения трансформации, для булевой функции fw

Uw(x,y)=(x,y xor fw(x))

Имеем, что после применения трансформации Uw к регистру в состоянии SUM |k>|0> он перейдёт в состояние SUM |k>|fw(k)>, а при измерении выходного кубита, будет происходить его коллапсирование и измерение вернёт значение |0> с вероятностью p=w/N и |1> с вероятностью q=1-p=(N-w)/N. То есть, если мы в дальнейшем перестанем обращать внимание на значения входных кубитов, то для нас выходной кубит будет просто находиться в состоянии SQRT(p)|0>+SQRT(q)|1>, то есть мы решили задачу - как задать параметры у возможных состояний кубита (мы задали состояние кубита).

Как проверить, что рассуждения корректны?

Ответ - практика. То есть для заданных значений p и q многократно повторим эксперимент задание начального состояния кубита и измерение его значения (коллапсирование). Статистика полученных результатов |0> и |1> должна совпасть с заданными параметрами p и q.

А вот и программка и её результат

namespace qrnd {

    open Microsoft.Quantum.Canon;
    open Microsoft.Quantum.Intrinsic;
    open Microsoft.Quantum.Arrays;
    open Microsoft.Quantum.Convert;
    open Microsoft.Quantum.Math;
    open Microsoft.Quantum.Logical;
    open Microsoft.Quantum.Diagnostics;
    open Microsoft.Quantum.Bitwise;
    
    /// # Описание
    /// измерение значений (коллапсирование) кубитов в массиве (который рассматриваем как один регистр)
    /// и возврат числа (равного полученной двоичной последовательности)
    operation Measure(qubits: Qubit[]) : Int {
        let results = ForEach(M, qubits);
        let i = ResultArrayAsInt(results);
        return i;
    }

    /// # Описание
    /// вычисления знака переноса при арифметической операции сложения
    /// то есть трансформация вида |k>|0> -> |k>|sign(k+value)>
    operation Sign(target: Qubit[], sign: Qubit, value: Int) : Unit {
        let k = Length(target);
        let bools = IntAsBoolArray(2^k-value, k);
        use (qubits) = (Qubit[2]) {
            for idx in 0..k-1 {
                let carry = qubits[idx%2];
                let next = qubits[1-(idx%2)];
                // вычисляем следующее значение флага переноса разряда
                if(bools[idx]) {
                    // next = carry*target[idx]^carry^target[idx]
                    Controlled X([carry, target[idx]], next);
                    Controlled X([carry], next);
                    Controlled X([target[idx]], next);
                }
                else {
                    // next = carry*target[idx] = carry&target[idx]
                    Controlled X([carry, target[idx]], next);
                }
                Reset(carry);
            } 
            Controlled X([qubits[k%2]], sign);
            ResetAll(qubits);
        }
    }

    @EntryPoint()
    operation Main(n: Int, w: Int, tests: Int) : Unit {
        Message("Hello quantum world!");

        let N=2^n;
        let p=100*w/N;
        let q=100*(N-w)/N;
        
        Message($"n={n} w={w} N={N} p={p}% q={q}% tests={tests}");

        mutable counters = [0, size=2];
        use (x,y)=(Qubit[n],Qubit()){
            for _ in 1..tests {
                ApplyToEach(H,x);
                Sign(x,y,w);
                let res = Measure([y]);
                set counters w/= res <- counters[res]+1;
                ResetAll(x);
                Reset(y);
            }
        }

        let f = [w,N-w];

        mutable total = 0;
        for element in f {
            set total+=element;
        }
        for idx in 0..1 {
            let expect = tests*f[idx]/N;
            let fact = counters[idx];
            Message($"{idx}: ... expect={expect} ... fact={fact}");
        }
    }
}

PS C:\Projects\qrnd> dotnet run -n 4 -w 5 --tests 1000
Hello quantum world!
n=4 w=5 N=16 p=31% q=68% tests=1000
0: ... expect=312 ... fact=289
1: ... expect=687 ... fact=711
PS C:\Projects\qrnd> dotnet run -n 4 -w 5 --tests 1000
Hello quantum world!
n=4 w=5 N=16 p=31% q=68% tests=1000
0: ... expect=312 ... fact=275
1: ... expect=687 ... fact=725
PS C:\Projects\qrnd> dotnet run -n 4 -w 5 --tests 1000
Hello quantum world!
n=4 w=5 N=16 p=31% q=68% tests=1000
0: ... expect=312 ... fact=292
1: ... expect=687 ... fact=708
PS C:\Projects\qrnd> dotnet run -n 4 -w 5 --tests 1000
Hello quantum world!
n=4 w=5 N=16 p=31% q=68% tests=1000
0: ... expect=312 ... fact=324
1: ... expect=687 ... fact=676

И задачка со звёздочкой

А давайте рассмотрим трансформацию U(w,x,y)=(w,x,y xor SIGN(w-x-1)) где параметр w так же перебирается с помощью квантовых вычислений, то есть так же описывается суммой возможных состояний (с вероятностями).

Но это, как говорится, уже другая история ... тут и алгоритм Гровера становится более интересным ...

Ссылки

Ранее

UPD. Кто-нибудь понимает, что задача поиска по словарю решается за одну итерацию, а не за SQRT(M/N), как в алгоритме Гровера?