Learning Q#. Grover’s algorithm. Do not wake the sleeping Caesar / Hebrew

Learning Q#. Grover’s algorithm. Do not wake the sleeping Caesar / Hebrew

Dedicated to crypto-hamsters.

Grover’s algorithm is a generalized, task-independent search whose function represents a “black box” f: {0,1}^n -> {0,1}^n, for which it is known that EXIST!w:f(w ) =a, where a is a given value.

We assume that for f and a given a it is possible to construct an oracle Uf: {w->1, x->0 if x!=w}

Grover’s algorithm is quite simple

  1. We set the initial value H|0> in the register (array of qubits).
  2. We repeat several times (based on the evaluation) a pair of transformations over the register

    • Display of the solution Uw: { w->-w, x->x if x!=w } or Uw = I-2|w>
    • The mapping s=H|0> Us = 2|s>
  3. We take the necessary decision from the register (with a high probability that it is correct)

Let’s apply this algorithm to solve the problem of finding the Caesar cipher key.

The Caesar cipher is one of the monoalphabetic ciphers, where the alphabet can be represented as a ring of deductions Z | m.

And if key is a number from 0..(m-1), and x(i) is where i=0..(l-1) and are numbers from 0..(m-1), then
y(i) = (x(i)+key) mod m is a ciphertext.

Accordingly, x(i) = (y(i) – key) mod m = (y(i) + (m-key)) mod m – is the decryption procedure.

Formulation of the problem

Suppose that in the plaintext some symbols Z|m occur rarely or not at all.

What will this fact mean?

That given the ciphertext y(i), we can do the following

  1. let’s go through all possible values ​​of the key key
  2. for this key we will get plaintext x(i)
  3. in this plaintext x(i), let’s count the number of “incorrect” characters – that is, those that do not occur at all (or occur very rarely)
  4. among all the keys, we will choose the one in which the number of “incorrect” characters obtained is zero (or minimal)

Thus, using the ciphertext, knowing the limitations of the symbols of the plaintext, we will obtain the value of the Caesar cipher key using the brute force method.

It is obvious that the given algorithm is, in its essence, an implementation of the following task

  • Given Error(y):Z|m->N
  • You need to find such a key that Error(key)=0

And this is a condition for the application of Grover’s algorithm

N.B. Obviously, similar considerations can be made for any block cipher in both ECB and CBC modes

Let’s move on to the implementation on Q

Let m=2^n and it is known about the plaintext that the highest digit in the binary representation of the number-symbol of the plaintext is always equal to 0

We implement the following methods

  1. The method of arithmetic over the qubit register is to increase the value by one, i.e. the transformation Inc:|k>->|k+1>
    /// # Описание
    /// увеличение на единицу числового значения в массиве кубитов (рассматриваемых как регистр)
    /// то есть трансформация вида |k> -> |k+1>
    operation Inc(target: Qubit[]) : Unit is Ctl {
        let n = Length(target);
        for idx in 1..n {
            Controlled X(target[0..n-idx-1], target[n-idx]);
        } 
    }
  2. The method of arithmetic over the register from qubits is to increase the value by the specified value value, i.e. the transformation Add(value):|k>->|k+value>

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

  3. Methods of generating a random key and a random plaintext sequence (taking into account the introduced restriction on plaintext characters)

    /// # Описание
    /// генерация последовательности со случайными символами алфавита (с учётом ограничений)
    operation RandomPlain(n: Int, l: Int) : Int[] {
        mutable plain = [0, size = l];
        use qubits = Qubit[n-1] { // !!! здесь мы ограничили набор входных символов - только числа без старшего разряда
            for idx in 0..l-1 {
                ApplyToEach(H, qubits);
                set plain w/= idx <- Measure(qubits);
                ResetAll(qubits);
            }
        }
        return plain;
    }
    
    /// # Описание
    /// генерация случайного ключа
    operation RandomKey(n: Int) : Int {
        use qubits = Qubit[n] {
            ApplyToEach(H, qubits);
            let key = Measure(qubits);
            ResetAll(qubits);
            return key;
        }
    }

  4. Caesar cipher encryption method

    /// # Описание
    /// получение шифрованного текста из открытого на указанном ключе (key)
    /// соответсвенно, для обратного преобазования используем эту же функцию, но с отрицательным ключем (-key)
    operation Encrypt(n: Int, plain: Int[], key: Int) : Int[] {
        let l = Length(plain);
        mutable m = 1;
        for i in 1..n {
            set m *= 2;
        }
        mutable cipher = [0, size = l];
        for idx in 0..l-1 {
            set cipher w/= idx <- (plain[idx]+key) % m;
        }
        return cipher;
    }
    
    /// # Описание
    /// вспомогательный метод для копирования значений массива кубитов
    operation Copy(source: Qubit[], target: Qubit[]) : Unit {
        let n = Length(source);
        for i in 0..(n-1) {
            Controlled X([source[i]], target[i]);
        }
    }
    
    /// # Описание
    /// реализация шифра цезаря (для одного символа) на кубитах
    /// то есть, для возможных вариантов ключа key имеем возможные варианты выхода
    /// и, соответственно, наоборот - при использовании отрицательного значения ключа (-key)
    /// получим возможные варианты открытого текста, для заданного шифросимвола
    operation EncryptChar(n: Int, ch: Int, cipher: Qubit[], key: Qubit[]) : Unit {
        Copy(key, cipher);
        Add(cipher, ch);
    } 

  5. A method of counting the number of “wrong” characters for a given ciphertext and a given key

    /// # Описание
    /// подсчёт количества "неправильных" символов, полученных в результате попытки дешифрования
    /// шифротекста в открытый текст на указанном ключе
    operation CountErrorsOnDecrypt(n: Int, cipher: Int[], key: Qubit[], error: Qubit[]) : Unit {
        // Для шифра Цезаря plain = cipher - key = chiper + (-key)
        // а поскольку мы реализовали только метод Add, то изменим знак числа key
        // key = -key = ~key+1
        ApplyToEach(X, key);
        Inc(key);
    
        use (plain) = (Qubit[n]) {
            for ch in cipher {
                EncryptChar(n, ch, plain, key);
                // поскольку мы ограничивали входные символы только числами без старшего разряда
                // то каждое наличие единицы в старшем разряде должно считаться ошибкой
                // найдём число таких ошибок в регистре error
                Controlled Inc([plain[n-1]], error);
                ResetAll(plain);
            }
        }
    
        ApplyToEach(X, key);
        Inc(key);
    }

  6. Oracle implementation – which issues |1> if the number of “incorrect” characters is 0 for the tested key

    /// # Описание
    /// реализация оракла, необходимого для алгоритма гровера
    /// соответственно, мы считаем, что правильное решение - это то, которое не имеет ошибок
    operation NoErrorOracle(n: Int, cipher: Int[], key: Qubit[], target: Qubit): Unit {
        let l = Length(cipher);
        let k = BitSizeI(l);
    
        use (error) = (Qubit[k]) {
            CountErrorsOnDecrypt(n, cipher, key, error);
            // очевидно, что если для error == 0, то это означает, что мы нашли нужный ключ
            // тогда, в соответствии с правилом построения оракула Uf(x,y)=(x,y^f(x)),
            // инвертируем последний кубит, если error == 0
            ApplyToEach(X, error);
            Controlled X(error, target);
            ResetAll(error);
        }
    }

  7. Methods of Grover’s algorithm.

    • Display solution
      /// # Описание
      /// шаг для алгоритма гровера
      /// отражение от решения    
      operation ReflectAboutSolution(oracle : (Qubit[], Qubit) => Unit, register : Qubit[]) : Unit {
      use (target)=(Qubit()){
          within {
              X(target);
              H(target);
          }
          apply {
              oracle(register, target);
          }
      }
      }
    • Reflection from H|0>
      /// # Описание
      /// шаг для алгоритма гровера
      /// отражение от H|0>
      operation ReflectAboutUniform(inputQubits : Qubit[]) : Unit {
      within {
          ApplyToEachA(H, inputQubits);
          ApplyToEachA(X, inputQubits);
      }
      apply {
          Controlled Z(Most(inputQubits), Tail(inputQubits));
      }
      }
    • And, actually, the main cycle of Grover’s algorithm
      /// # Описание
      /// алгоритм гровера
      operation RunGroversSearch(register : Qubit[], oracle : (Qubit[], Qubit) => Unit, iterations : Int) : Unit {
      ApplyToEach(H, register);
      for _ in 1 .. iterations {
          ReflectAboutSolution(oracle, register);
          ReflectAboutUniform(register);
      }
      }

Let’s prepare the test

  1. Let’s check the correctness of the constructed oracle using the brute force algorithm
            // проверка оракла
            // прогоним его через брутто-форс
            for i in 0..m-1 {
                use (qubits, oracle) = (Qubit[n], Qubit()){
                    Add(qubits, i);
                    noErrorOracle(qubits, oracle);
                    let hacked = Measure(qubits);
                    Message($"BruteForce: {key}=={hacked} ... oracle = {M(oracle)}");
                    if(M(oracle)==One){
                        let plain = Encrypt(n, cipher, m-hacked);
                        Message($"BruteForce: Success!!! {key}=={hacked} ... plain = {plain}");
                    }
                    ResetAll(qubits);
                    Reset(oracle);
                }
            }
  2. Let’s run Grover’s algorithm in two modes:

    • with the calculated number of iterations until the answer is obtained
          // применяем алгоритм гровера
          // указываем точное число шагов у алгоритма
          set isSuccess = false;
          repeat {
              use (qubits, oracle) = (Qubit[n], Qubit()){
                  let iterations = Round(PI()/4.0*Sqrt(IntAsDouble(m)));
                  RunGroversSearch(qubits, noErrorOracle, iterations);
                  noErrorOracle(qubits, oracle);
                  let hacked = Measure(qubits);
                  Message($"GroversSearch: iterations = {iterations} ... {key}=={hacked} ... oracle = {M(oracle)}");
                  if(M(oracle)==One){
                      set isSuccess = true;
                      let plain = Encrypt(n, cipher, m-hacked);
                      Message($"GroversSearch: Success!!! {key}=={hacked} ... plain = {plain}");
                  }
                  ResetAll(qubits);
                  Reset(oracle);
              }
          }
          until(isSuccess);
    • with different values ​​of the number of iterations until the answer is obtained

          // применяем алгоритм гровера
          // точное число шагов у алгоритма мы не знаем (знаем только оценку)
          // поэтому запускаем с разными значениями итераций
          // Повторение итераций после groverIterations сопровождается снижением этой вероятности
          // вплоть до практически нулевой вероятности успеха на итерации 2*groverIterations.
          // После этого вероятность снова возрастает до итерации 3*groverIterations и т. д.
          // В практических приложениях обычно неизвестно, сколько решений имеет ваша задача, 
          // прежде чем вы решите ее. Эффективной стратегией для решения этой проблемы является 
          // "предположение" количества решений путем постепенного увеличения степени двойки (т. е. 1,2,4,8,...).
          // Одно из этих предположений будет достаточно близким для того, чтобы алгоритм нашел решение
          // со средним числом итераций около SQRT(2^n/S) 
      
          mutable currenIterations = 0;
          set isSuccess = false;
          repeat{
              set currenIterations = currenIterations+1;
              use (qubits, oracle) = (Qubit[n], Qubit()){
                  RunGroversSearch(qubits, noErrorOracle, currenIterations);
                  noErrorOracle(qubits, oracle);
                  let hacked = Measure(qubits);
                  Message($"GroversSearch: iterations = {currenIterations} ... {key}=={hacked} ... oracle = {M(oracle)}");
                  if(M(oracle)==One){
                      set isSuccess = true;
                      let plain = Encrypt(n, cipher, m-hacked);
                      Message($"GroversSearch: Success!!! {key}=={hacked} ... plain = {plain}");
                  }
                  ResetAll(qubits);
                  Reset(oracle);
              }
          }
          until (isSuccess);

Full code text

namespace qcaesarianae {

    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;

    /// # Описание
    /// увеличение на единицу числового значения в массиве кубитов (рассматриваемых как регистр)
    /// то есть трансформация вида |k> -> |k+1>
    operation Inc(target: Qubit[]) : Unit is Ctl {
        let n = Length(target);
        for idx in 1..n {
            Controlled X(target[0..n-idx-1], target[n-idx]);
        } 
    }

    /// # Описание
    /// увеличение на указанную величину числового значения в массиве кубитов (рассматриваемых как регистр)
    /// то есть трансформация вида |k> -> |k+value>
    operation Add(target: Qubit[], value: Int) : Unit {
        let n = Length(target);
        let bools = IntAsBoolArray(value, n);
        use (qubits) = (Qubit[2]) {
            for idx in 0..n-1 {
                let carry = qubits[idx%2];
                let next = qubits[1-(idx%2)];
                // вычисляем следующее значение флага переноса разряда
                if(bools[idx]) {
                    // next = carry*target[idx]^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);
                }

                // добавляем текушее значение флага переноса и добавляемого бита
                Controlled X([carry], target[idx]);
                if(bools[idx]) {
                    X(target[idx]);
                }
                Reset(carry);
            } 
            ResetAll(qubits);
        }
    }

    /// # Описание
    /// измерение значений (коллапсирование) кубитов в массиве (который рассматриваем как один регистр)
    /// и возврат числа (равного полученной двоичной последовательности)
    operation Measure(qubits: Qubit[]) : Int {
        let results = ForEach(M, qubits);
        let bools = ResultArrayAsBoolArray(results);
        let i = BoolArrayAsInt(bools);
        return i;
    }

    /// # Описание
    /// генерация последовательности со случайными символами алфавита (с учётом ограничений)
    operation RandomPlain(n: Int, l: Int) : Int[] {
        mutable plain = [0, size = l];
        use qubits = Qubit[n-1] { // !!! здесь мы ограничили набор входных символов - только числа без старшего разряда
            for idx in 0..l-1 {
                ApplyToEach(H, qubits);
                set plain w/= idx <- Measure(qubits);
                ResetAll(qubits);
            }
        }
        return plain;
    }

    /// # Описание
    /// генерация случайного ключа
    operation RandomKey(n: Int) : Int {
        use qubits = Qubit[n] {
            ApplyToEach(H, qubits);
            let key = Measure(qubits);
            ResetAll(qubits);
            return key;
        }
    }

    /// # Описание
    /// получение шифрованного текста из открытого на указанном ключе (key)
    /// соответсвенно, для обратного преобазования используем эту же функцию, но с отрицательным ключем (-key)
    operation Encrypt(n: Int, plain: Int[], key: Int) : Int[] {
        let l = Length(plain);
        mutable m = 1;
        for i in 1..n {
            set m *= 2;
        }
        mutable cipher = [0, size = l];
        for idx in 0..l-1 {
            set cipher w/= idx <- (plain[idx]+key) % m;
        }
        return cipher;
    }

    /// # Описание
    /// вспомогательный метод для копирования значений массива кубитов
    operation Copy(source: Qubit[], target: Qubit[]) : Unit {
        let n = Length(source);
        for i in 0..(n-1) {
            Controlled X([source[i]], target[i]);
        }
    }

    /// # Описание
    /// реализация шифра цезаря (для одного символа) на кубитах
    /// то есть, для возможных вариантов ключа key имеем возможные варианты выхода
    /// и, соответственно, наоборот - при использовании отрицательного значения ключа (-key)
    /// получим возможные варианты открытого текста, для заданного шифросимвола
    operation EncryptChar(n: Int, ch: Int, cipher: Qubit[], key: Qubit[]) : Unit {
        Copy(key, cipher);
        Add(cipher, ch);
    } 

    /// # Описание
    /// подсчёт количества "неправильных" символов, полученных в результате попытки дешифрования
    /// шифротекста в открытый текст на указанном ключе
    operation CountErrorsOnDecrypt(n: Int, cipher: Int[], key: Qubit[], error: Qubit[]) : Unit {
        // Для шифра Цезаря plain = cipher - key = chiper + (-key)
        // а поскольку мы реализовали только метод Add, то изменим знак числа key
        // key = -key = ~key+1
        ApplyToEach(X, key);
        Inc(key);

        use (plain) = (Qubit[n]) {
            for ch in cipher {
                EncryptChar(n, ch, plain, key);
                // поскольку мы ограничивали входные символы только числами без старшего разряда
                // то каждое наличие единицы в старшем разряде должно считаться ошибкой
                // найдём число таких ошибок в регистре error
                Controlled Inc([plain[n-1]], error);
                ResetAll(plain);
            }
        }

        ApplyToEach(X, key);
        Inc(key);
    }

    /// # Описание
    /// реализация оракла, необходимого для алгоритма гровера
    /// соответственно, мы считаем, что правильное решение - это то, которое не имеет ошибок
    operation NoErrorOracle(n: Int, cipher: Int[], key: Qubit[], target: Qubit): Unit {
        let l = Length(cipher);
        let k = BitSizeI(l);

        use (error) = (Qubit[k]) {
            CountErrorsOnDecrypt(n, cipher, key, error);
            // очевидно, что если для error == 0, то это означает, что мы нашли нужный ключ
            // тогда, в соответствии с правилом построения оракула Uf(x,y)=(x,y^f(x)),
            // инвертируем последний кубит, если error == 0
            ApplyToEach(X, error);
            Controlled X(error, target);
            ResetAll(error);
        }
    }

    /// # Описание
    /// шаг для алгоритма гровера
    /// отражение от решения    
    operation ReflectAboutSolution(oracle : (Qubit[], Qubit) => Unit, register : Qubit[]) : Unit {
        use (target)=(Qubit()){
            within {
                X(target);
                H(target);
            }
            apply {
                oracle(register, target);
            }
        }
    }

    /// # Описание
    /// шаг для алгоритма гровера
    /// отражение от H|0>
    operation ReflectAboutUniform(inputQubits : Qubit[]) : Unit {
        within {
            ApplyToEachA(H, inputQubits);
            ApplyToEachA(X, inputQubits);
        }
        apply {
            Controlled Z(Most(inputQubits), Tail(inputQubits));
        }
    }

    /// # Описание
    /// алгоритм гровера
    operation RunGroversSearch(register : Qubit[], oracle : (Qubit[], Qubit) => Unit, iterations : Int) : Unit {
        ApplyToEach(H, register);
        for _ in 1 .. iterations {
            ReflectAboutSolution(oracle, register);
            ReflectAboutUniform(register);
        }
    }

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

        let tests = 1;
        for _ in 1..tests {
            mutable m = 1;
            for _ in 1..n {
                set m *= 2;
            }
            Message($"n = {n} ... l = {l} ... m = {m}");

            let key = RandomKey(n);
            let cipher = Encrypt(n, RandomPlain(n, l), key);
            Message($"key = {key} cipher = {cipher}");

            let noErrorOracle = NoErrorOracle(n, cipher, _, _);

            let groverIterations = Round(PI()/4.0*Sqrt(IntAsDouble(m)));
            Message($"GroversSearch: groverIterations = {groverIterations}?");

            mutable isSuccess = false;

            // применяем алгоритм гровера
            // указываем точное число шагов у алгоритма
            set isSuccess = false;
            repeat {
                use (qubits, oracle) = (Qubit[n], Qubit()){
                    let iterations = Round(PI()/4.0*Sqrt(IntAsDouble(m)));
                    RunGroversSearch(qubits, noErrorOracle, iterations);
                    noErrorOracle(qubits, oracle);
                    let hacked = Measure(qubits);
                    Message($"GroversSearch: iterations = {iterations} ... {key}=={hacked} ... oracle = {M(oracle)}");
                    if(M(oracle)==One){
                        set isSuccess = true;
                        let plain = Encrypt(n, cipher, m-hacked);
                        Message($"GroversSearch: Success!!! {key}=={hacked} ... plain = {plain}");
                    }
                    ResetAll(qubits);
                    Reset(oracle);
                }
            }
            until(isSuccess);

            // применяем алгоритм гровера
            // точное число шагов у алгоритма мы не знаем (знаем только оценку)
            // поэтому запускаем с разными значениями итераций
            // Повторение итераций после groverIterations сопровождается снижением этой вероятности
            // вплоть до практически нулевой вероятности успеха на итерации 2*groverIterations.
            // После этого вероятность снова возрастает до итерации 3*groverIterations и т. д.
            // В практических приложениях обычно неизвестно, сколько решений имеет ваша задача, 
            // прежде чем вы решите ее. Эффективной стратегией для решения этой проблемы является 
            // "предположение" количества решений путем постепенного увеличения степени двойки (т. е. 1,2,4,8,...).
            // Одно из этих предположений будет достаточно близким для того, чтобы алгоритм нашел решение
            // со средним числом итераций около SQRT(2^n/S) 

            mutable currenIterations = 0;
            set isSuccess = false;
            repeat{
                set currenIterations = currenIterations+1;
                use (qubits, oracle) = (Qubit[n], Qubit()){
                    RunGroversSearch(qubits, noErrorOracle, currenIterations);
                    noErrorOracle(qubits, oracle);
                    let hacked = Measure(qubits);
                    Message($"GroversSearch: iterations = {currenIterations} ... {key}=={hacked} ... oracle = {M(oracle)}");
                    if(M(oracle)==One){
                        set isSuccess = true;
                        let plain = Encrypt(n, cipher, m-hacked);
                        Message($"GroversSearch: Success!!! {key}=={hacked} ... plain = {plain}");
                    }
                    ResetAll(qubits);
                    Reset(oracle);
                }
            }
            until (isSuccess);

            // проверка оракла
            // прогоним его через брутто-форс
            for i in 0..m-1 {
                use (qubits, oracle) = (Qubit[n], Qubit()){
                    Add(qubits, i);
                    noErrorOracle(qubits, oracle);
                    let hacked = Measure(qubits);
                    Message($"BruteForce: {key}=={hacked} ... oracle = {M(oracle)}");
                    if(M(oracle)==One){
                        let plain = Encrypt(n, cipher, m-hacked);
                        Message($"BruteForce: Success!!! {key}=={hacked} ... plain = {plain}");
                    }
                    ResetAll(qubits);
                    Reset(oracle);
                }
            }
        }
    }
}

And actually, let’s test it…

PS C:\Projects\qcaesarianae> dotnet run -n 3 -l 32
Hello quantum world!
n = 3 ... l = 32 ... m = 8
key = 4 cipher = [6,4,6,6,6,7,6,5,4,4,4,7,4,7,6,4,7,7,6,7,5,6,4,6,6,7,7,5,4,7,6,4]
GroversSearch: groverIterations = 2?
GroversSearch: iterations = 2 ... 4==5 ... oracle = Zero
GroversSearch: iterations = 2 ... 4==6 ... oracle = Zero
GroversSearch: iterations = 2 ... 4==3 ... oracle = Zero
GroversSearch: iterations = 2 ... 4==6 ... oracle = Zero
GroversSearch: iterations = 2 ... 4==1 ... oracle = Zero
GroversSearch: iterations = 2 ... 4==6 ... oracle = Zero
GroversSearch: iterations = 2 ... 4==3 ... oracle = Zero
GroversSearch: iterations = 2 ... 4==2 ... oracle = Zero
GroversSearch: iterations = 2 ... 4==6 ... oracle = Zero
GroversSearch: iterations = 2 ... 4==7 ... oracle = Zero
GroversSearch: iterations = 2 ... 4==5 ... oracle = Zero
GroversSearch: iterations = 2 ... 4==5 ... oracle = Zero
GroversSearch: iterations = 2 ... 4==6 ... oracle = Zero
GroversSearch: iterations = 2 ... 4==1 ... oracle = Zero
GroversSearch: iterations = 2 ... 4==0 ... oracle = Zero
GroversSearch: iterations = 2 ... 4==5 ... oracle = Zero
GroversSearch: iterations = 2 ... 4==4 ... oracle = One
GroversSearch: Success!!! 4==4 ... plain = [2,0,2,2,2,3,2,1,0,0,0,3,0,3,2,0,3,3,2,3,1,2,0,2,2,3,3,1,0,3,2,0]
GroversSearch: iterations = 1 ... 4==1 ... oracle = Zero
GroversSearch: iterations = 2 ... 4==4 ... oracle = One
GroversSearch: Success!!! 4==4 ... plain = [2,0,2,2,2,3,2,1,0,0,0,3,0,3,2,0,3,3,2,3,1,2,0,2,2,3,3,1,0,3,2,0]
BruteForce: 4==0 ... oracle = Zero
BruteForce: 4==1 ... oracle = Zero
BruteForce: 4==2 ... oracle = Zero
BruteForce: 4==3 ... oracle = Zero
BruteForce: 4==4 ... oracle = One
BruteForce: Success!!! 4==4 ... plain = [2,0,2,2,2,3,2,1,0,0,0,3,0,3,2,0,3,3,2,3,1,2,0,2,2,3,3,1,0,3,2,0]
BruteForce: 4==5 ... oracle = Zero
BruteForce: 4==6 ... oracle = Zero
BruteForce: 4==7 ... oracle = Zero

Result

Grover’s algorithm estimates the required number of iterations as PI/4*SQRT(2^n/S), where S is the number of possible solutions to the problem.

N.B. Are you absolutely sure that quantum computers with von Neumann-type architecture will not be made (or not) – after all, there was a lot of talk about the factorization of numbers, that it is technically impossible and difficult … ho-ho-ho?

Link

Related posts