Deutsch-Jozsa Algorithm

Deutsch Jozsa Algorithm is related to implementation of a function 

f : {0,1}^m -> {0,1} on a black box quantum computer known as an oracle.  The algorithm was proposed by  David Deutsch and Richard Jozsa in 1992.  Richard Cleve, Artur Ekert, Chiara Macchiavello and Michele Mosca improved it in 1998. The pseudo code for the algorithm is shown below.

• The initial state is n+1 bit state  |0> bits |1>  .
• Hadamard transform is applied to each bit 
• quantum oracle function is applied
• For every x, possibilities of 0 or 1 is tested.

Q#  project  and solution is created using the following commands.

dotnet new console -lang Q# --output Deutsch

Visual  Studio Code is used to open the project. The project will have two files Driver.cs (C# driver) and Operations.qs (Q# ). The Operations.qs is renamed as Quantum.qs.

The code snippet below shows the Quantum.qs after adding the operation Set and StateTest.

namespace DeutschJozsaAlgorithm {
    
    open Microsoft.Quantum.Primitive;
    open Microsoft.Quantum.Canon;   
    /// IsConstantBooleanFunction Operation 
    /// # Summary
    /// The operation `CheckConstantBooleanFunction` answers this question by returning the
    /// Boolean value `true` if the function is constant and `false` if it is not. Note
    /// that the promise that the function is either constant or balanced is assumed.
    ///
    /// # Parameters
    /// ## Uf
    /// A quantum operation that implements |𝑥〉|𝑦〉 ↦ |𝑥〉|𝑦 ⊕ 𝑓(𝑥)〉,
    /// where 𝑓 is a Boolean function, 𝑥 is an 𝑛 bit register and 𝑦 is a single qubit.
    /// ## n
    /// The number of bits of the input register |𝑥〉.
    ///
    /// # Return
    /// A boolean value `true` that indicates that the function is constant and `false`
    /// that indicates that the function is balanced.
    ///
   operation CheckConstantBooleanFunction (Uf : (Qubit[] => Unit), n : Int) : Bool {
        
        
        mutable resultArray = new Result[n];
        
        
        using (qubits = Qubit[n + 1]) {
            
        
            X(qubits[n]);
            
            ApplyToEach(H, qubits);
            
            
            Uf(qubits);
            
            
            ApplyToEach(H, qubits[0 .. n - 1]);
            
            
            for (idx in 0 .. n - 1) {
                set resultArray[idx] = MResetZ(qubits[idx]);
            }
            
            
            Reset(qubits[n]);
        }
        
        
        return ForAll(IsResultZero, resultArray);
    }
    
    

    
    
    operation ExecuteDeutschJozsaAlgorithm (nQubits : Int, markedElements : Int[]) : Bool {
        
        return CheckConstantBooleanFunction(GetBooleanFunctionFromMarkedElements(nQubits, markedElements), nQubits);
    }
    
    operation GetBooleanFunctionFromMarkedElementsImpl (n : Int, markedElements : Int[], qs : Qubit[]) : Unit {
       
       let target = qs[Length(qs) - 1];
       let inputs = qs[0 .. Length(qs) - 2];
       
       
       let nMarked = Length(markedElements);
       
       for (idxMarked in 0 .. nMarked - 1) {
           

           (ControlledOnInt(markedElements[idxMarked], ApplyToEachCA(X, _)))(inputs, [target]);
       }
   }


   
   
   /// # Summary
   /// Constructs an operation representing a query to a boolean function
   /// # Parameters
   /// ## nQubits
   /// The number of qubits to be used in representing the query operation.
   /// ## markedElements
   /// An array of the elements {𝑘ᵢ} for which 𝑓 should return 1.
   ///
   /// # Return
   /// An operation representing the unitary 𝑈 |𝑧〉 |𝑘〉 = |𝑧 ⊕ 𝑥ₖ〉 |𝑘〉.
   function GetBooleanFunctionFromMarkedElements (nQubits : Int, markedElements : Int[]) : (Qubit[] => Unit) {
       
       return GetBooleanFunctionFromMarkedElementsImpl(nQubits, markedElements, _);
   }
   
     
     
     
   
    
    
    
}

The Driver file will have the following code to execute DeutschJozsaAlgorithm.

/////////////////////////////////////////////////////////////////////
// This file contains the driver class.
//////////////////////////////////////////////////////////////////////

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


namespace DeutschJozsaAlgorithm
{
    class Driver
    {
     

        static void Main(string[] args)
        {
           
            var sim = new QuantumSimulator(throwOnReleasingQubitsNotInZeroState: true);         
            var balancedTestCase = new QArray<long> { 1, 2 }; 
            if (ExecuteDeutschJozsaAlgorithm.Run(sim, 2, balancedTestCase).Result)
            {
                throw new Exception("Both the test cases  are constant!");
            }

            var constantTestCase = new QArray<long> { 0, 1, 2, 3, 4, 5, 6, 7 };
            if (!ExecuteDeutschJozsaAlgorithm.Run(sim, 3, constantTestCase).Result)
            {
                throw new Exception("All test cases are balanced!");
            }
            System.Console.WriteLine("constant and balanced functions - success");

           
           

          

        }
    }
}

Run the following commands  to execute the project in Visual Studio Code:

^F5 

In the terminal, you can execute the build by running the command below.

dotnet run

The screenshot of the output is attached below: