quantum counting algorithm

[friguzzi]

trafficstars

@tcNickolas I'm submitting a pull request for quantum counting. Haven't yet had tim to do the jupyther notebook

[msftclas]

All CLA requirements met.

[tcNickolas]

It's fine to start with just a Q# project for now, and polish the Notebook later - depending on what exactly you do in the testing harness it might be a bit tricky, and it is usually easier to convert the final versions of the tasks to Notebook format than to update both presentations at each review iteration.

I'll take a closer look a bit later - I didn't expect that you have the kata ready, and I'm a bit busy today. Sorry about the delay, and thank you for the PR!

[friguzzi]

@tcNickolas the complexity of quantum counting is O(sqrt(N)), see the Nilsson Cheung book. Thanks for the comments to the pull request, I will implement them

[friguzzi]

Hi @tcNickolas, I've written this code

// Copyright (c) Microsoft Corporation. All rights reserved.
// Licensed under the MIT license.

//////////////////////////////////////////////////////////////////////
// This file contains reference solutions to all tasks.
// The tasks themselves can be found in Tasks.qs file.
// We recommend that you try to solve the tasks yourself first,
// but feel free to look up the solution if you get stuck.
//////////////////////////////////////////////////////////////////////

namespace Quantum.Kata.Counting {
    
    open Microsoft.Quantum.Arrays;
    open Microsoft.Quantum.Intrinsic;
    open Microsoft.Quantum.Canon;
	open Microsoft.Quantum.Math;
    open Microsoft.Quantum.Oracles;
    open Microsoft.Quantum.Convert;
    open Microsoft.Quantum.Arithmetic;    
    open Microsoft.Quantum.Characterization;


    //////////////////////////////////////////////////////////////////
    // Part I. Oracle for Counting
    //////////////////////////////////////////////////////////////////
    
	operation Oracle_SolutionCount_Reference (queryRegister : Qubit[], target : Qubit, nSol : Int) : Unit is Ctl+ Adj {
    // Designate first nSol integers solutions (since we don't really care which ones are solutions)
		for (i in 0 .. nSol - 1) {
        (ControlledOnInt(i, X))(queryRegister, target);
		}
	}
    
    //////////////////////////////////////////////////////////////////
    // Part II. The Grover iteration
    //////////////////////////////////////////////////////////////////
   

    // Helper operation which converts marking oracle into phase oracle using an extra qubit
    operation ApplyMarkingOracleAsPhaseOracle (markingOracle : ((Qubit[], Qubit) => Unit is Ctl+Adj), 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)) : Unit  is Ctl+Adj
    {

            // apply oracle
            ApplyMarkingOracleAsPhaseOracle(oracle, register);
            // apply inversion about the mean
            ApplyToEachCA(H, register);
            ApplyToEachCA(X, register);
            Controlled Z(Most(register), Tail(register));
            ApplyToEachCA(X, register);
            ApplyToEachCA(H, register);
	}
    
    
    //////////////////////////////////////////////////////////////////
    // Part III. Putting it all together: Quantum Counting
    //////////////////////////////////////////////////////////////////
    

	operation Counting_Reference(n_bit : Int, n_sol: Int, precision: Int) : Double {
        mutable phase = -1.0;

        using ((reg,phaseRegister)=(Qubit[n_bit],Qubit[precision]))
        {                                  
        let oracle = OracleToDiscrete(GroverIteration(_, Oracle_SolutionCount_Reference(_,_,n_sol)));


        // Allocate qubits to hold the eigenstate of U and the phase in a big endian register 
            
            let phaseRegisterBE = BigEndian(phaseRegister);
            // Prepare the eigenstate of U
                ApplyToEach(H, reg);
            // Call library
            QuantumPhaseEstimation(oracle, reg, phaseRegisterBE);
            // Read out the phase
            set phase = IntAsDouble(MeasureInteger(BigEndianAsLittleEndian(phaseRegisterBE))) / IntAsDouble(1 <<< (n_bit));

            ResetAll(reg);
            ResetAll(phaseRegister);
        }
        let angle = PI()*phase;
        let res = (PowD(Sin(angle),2.0));

        return PowD(2.0,IntAsDouble(n_bit))*res;
    }

     operation CR(): Double {
	   return  Counting_Reference(4, 4, 3);
	 }
}

but I get this error

Errore	QS6207	The given argument does not support the required functor(s). Missing support for the functor(s) Controlled.	Counting	C:\Users\Fabrizio\source\repos\QuantumKatas\Counting\ReferenceImplementation.qs	61	

Line 61 is the following

  ApplyMarkingOracleAsPhaseOracle(oracle, register);

in GroverIteration. It seems to me that Adj and Ctl are available for ApplyMarkingOracleAsPhaseOracle

[friguzzi]

I found the problem.

[friguzzi]

Hi @tcNickolas I've prepared a draft, it's commit d5d5daf87a3e0e83b62cf33bd9c27dccc37e6415 Unfortunately I get values far from the correct answer, can you have a look?

[friguzzi]

The problem is the number of solutions found is 2^N-n_sol instead of n_sol

[friguzzi]

Hi, the kata now works but I had to add a global phase

            R(PauliI, 2.0 * PI(), register[0]);

to GroverIteration. The kata has now 3 tests with 7 bits, 5 precision bits and number of solution 16, 20 and 40