0
$\begingroup$

I have this program derived from Microsoft Quantum Kata for quantum search (Grover algorithm) (see here)

namespace Quantum.Search {


open Microsoft.Quantum.Intrinsic;
open Microsoft.Quantum.Canon;
open Microsoft.Quantum.Convert;
open Microsoft.Quantum.Math;
open Microsoft.Quantum.Oracles;
open Microsoft.Quantum.Arithmetic;
open Microsoft.Quantum.Characterization;
open Microsoft.Quantum.Arrays;
open Microsoft.Quantum.Measurement;


operation SprinklerAnc (queryRegister:  Qubit[],  target : Qubit) : Unit is Adj+Ctl 
{
    using (ancilla=Qubit[3 ])
    {
        X(queryRegister[2]);
        X(ancilla[0]);
        X(ancilla[1]);
        X(ancilla[2]);
    
        CCNOT(queryRegister[0],queryRegister[1],ancilla[0]);
        CCNOT(queryRegister[1],queryRegister[2],ancilla[1]);
        CCNOT(queryRegister[0],queryRegister[2],ancilla[2]);
        (Controlled X)([ancilla[0],ancilla[1],ancilla[2],queryRegister[3]],target);
        CCNOT(queryRegister[0],queryRegister[2],ancilla[2]);
        CCNOT(queryRegister[1],queryRegister[2],ancilla[1]);
        CCNOT(queryRegister[0],queryRegister[1],ancilla[0]);

        X(ancilla[2]);
        X(ancilla[1]);
        X(ancilla[0]);
        X(queryRegister[2]);

    }
}

operation ApplyMarkingOracleAsPhaseOracle (markingOracle : ((Qubit[], Qubit) => Unit is Adj+Ctl),  register : Qubit[] ) :  Unit is Adj+Ctl 
{
    
    using (target = Qubit()) 
    {
        // Put the target into the |-⟩ state
        X(target);
        H(target);
            
        // Apply the marking oracle; since the target is in the |-⟩ state,
        // flipping the target if the register satisfies the oracle condition will apply a -1 factor to the state
        markingOracle(register, target);
            
        // Put the target back into |0⟩ so we can return it
        H(target);
        X(target);
    }
}


// The Grover iteration
operation GroverIteration (register : Qubit[], oracle : ((Qubit[],Qubit) => Unit is Adj+Ctl)) : Unit is Ctl+Adj
{
    
    ApplyMarkingOracleAsPhaseOracle(oracle,register);
    ApplyToEachCA(H, register);
    using (ancilla = Qubit()){
            (ControlledOnInt(0, X))(register, ancilla); // Bit flips the ancilla to |1⟩ if register is |0...0⟩   
            Z(ancilla);                                 // Ancilla phase (and therefore whole register phase) becomes -1 if above condition is satisfied
            
            (ControlledOnInt(0, X))(register, ancilla); // Puts ancilla back in |0⟩  
    } 
    Ry(2.0 * PI(), register[0]);
    ApplyToEachCA(H, register);
}    


operation Search() : Result[] 
{
    
    using (reg=Qubit[4 ])
    {


  H(reg[0]);
  H(reg[1]);
  H(reg[2]);
  H(reg[3]);
  for (i in 1 ..2) {
  GroverIteration(reg, SprinklerAnc);
  }
  let state = MultiM(reg);

  ResetAll(reg);
  return state;
  }

}
}

with driver

using System;
using Microsoft.Quantum.Simulation.Core;
using Microsoft.Quantum.Simulation.Simulators;
using System.Collections.Generic;

namespace Quantum.Search
{
class Driver
{
    static void Main(string[] args)
    {

        using (var qsim = new QuantumSimulator())
        {
            IDictionary<string, int> dict = new Dictionary<string, int>();
            for (int i = 0; i < 1000; i++)
            {
                IQArray<Result> res = QMPE.Run(qsim).Result;
                string s = Convert.ToString(res);
                int result;
                if (dict.TryGetValue(s, out result))
                {
                    dict.Remove(s);
                    dict.Add(s, result + 1);
                }
                else
                {

                    dict.Add(s, 1);
                }
                System.Console.WriteLine($"Res:{s}");

            }
            foreach (KeyValuePair<string, int> item in dict)
            {
                Console.WriteLine("Key: {0}, Value: {1}", item.Key, item.Value);
            }
        }
    }
}
}

It should search for the solutions of the 3 bits formula (not reg[0] or reg[2]) and (not reg1 or reg[2]) and (not reg[0] or not reg1) and reg[3]. This formula has 4 solutions: 0001, 0011, 0111 and 1011. However, the distribution over the solutions that I get in 1000 execution is

Key: [One,One,One,Zero], Value: 57
Key: [One,One,Zero,Zero], Value: 63
Key: [Zero,One,One,One], Value: 58
Key: [Zero,One,One,Zero], Value: 74
Key: [One,Zero,One,One], Value: 70
Key: [One,Zero,One,Zero], Value: 70
Key: [Zero,Zero,One,Zero], Value: 76
Key: [One,Zero,Zero,One], Value: 47
Key: [Zero,Zero,Zero,Zero], Value: 79
Key: [Zero,One,Zero,Zero], Value: 66
Key: [One,One,One,One], Value: 52
Key: [Zero,Zero,Zero,One], Value: 55
Key: [One,Zero,Zero,Zero], Value: 58
Key: [Zero,One,Zero,One], Value: 58
Key: [Zero,Zero,One,One], Value: 63
Key: [One,One,Zero,One], Value: 54

so basically a uniform distribution over the whole set of 16 configurations. I don't understand why the solution of the equations are not getting higher frequencies.

$\endgroup$
2
$\begingroup$

Short answer: for this problem the optimal number of iterations is 1 - change the loop range to do just one iteration and the output will switch to showing only the solutions to the problem:

Key: [Zero,Zero,One,One], Value: 255
Key: [Zero,Zero,Zero,One], Value: 251
Key: [Zero,One,One,One], Value: 233
Key: [One,Zero,One,One], Value: 261

The general formula for the number of solutions is $\frac{\pi}{4}\sqrt{\frac{N}{M}}$, where $N = 16$ and $M = 4$, gives us $\frac{\pi}{2} \approx 1.5$, which can be rounded either up or down.

If we look at the derivation of the formula, however, we'll see that the square root is an approximation made assuming that $M << N$, and the optimal number of iterations is $>> 1$. The exact formula is $\frac12 \big( \frac{\pi}{2\arcsin \sqrt{\frac{M}{N}}}-1\big)$, which will give us $\arcsin \sqrt{\frac{M}{N}} = \arcsin 0.5 = \frac{\pi}{6}$ and the optimal number of iterations equal to 1.

You can see the visual derivation of the formula in this slide deck - it shows where these assumptions come from and how they affect the result.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.