Grover’s Algorithm is related to searching an unstructured database with entries. Classical algorithms for searching n entries will be O(n) queries. The grover’s algorithm requires only O(square root of n). Bohmian mechanics based non local hidden quantum computer can perform the search in O(cube root of n) queries.
Q# project and solution is created using the following commands.
dotnet new console -lang Q# --output BernsteinVisual 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 the Quantum.qs after adding the operation Set and StateTest.
namespace Grovers
{
open Microsoft.Quantum.Primitive;
open Microsoft.Quantum.Canon;
// GetDataFromInts Operation
/// # Summary
/// Database oracle `D` constructed from classical database.
///
/// # Parameters
/// ## markedElements
/// Indices to marked elements in database.
/// ## markedQubit
/// Qubit that indicated whether database element is marked.
/// ## databaseRegister
/// A register of n qubits initially in the |00…0〉 state.
///
operation GetDataFromInts(markedElements : Int[], markedQubit: Qubit, databaseRegister: Qubit[]) : Unit
{
body(...) {
let nMarked = Length(markedElements);
for (idxMarked in 0..nMarked - 1) {
// Note: As X accepts a Qubit, and ControlledOnInt only
// accepts Qubit[], we use ApplyToEachCA(X, _) which accepts
// Qubit[] even though the target is only 1 Qubit.
(ControlledOnInt(markedElements[idxMarked], ApplyToEachCA(X, _)))(databaseRegister, [markedQubit]);
}
}
adjoint auto;
controlled auto;
adjoint controlled auto;
}
// SetupGroverStateOracle Operation
/// # Summary
/// Preparation of start state from database oracle and oracle `U` that
/// creates a uniform superposition over database indices.
///
/// # Parameters
/// ## markedElements
/// Indices to marked elements in database.
/// ## idxMarkedQubit
/// Index to `MarkedQubit`.
/// ## startQubits
/// The collection of the n+1 qubits `MarkedQubit` and `databaseRegister`
/// initially in the |00…0〉 state.
///
operation SetupGroverStateOracleImpl(markedElements : Int[], idxMarkedQubit: Int , startQubits: Qubit[]) : Unit
{
body(...) {
let flagQubit = startQubits[idxMarkedQubit];
let databaseRegister = Exclude([idxMarkedQubit], startQubits);
ApplyToEachCA(H, databaseRegister);
GetDataFromInts(markedElements, flagQubit, databaseRegister);
}
adjoint auto;
controlled auto;
adjoint controlled auto;
}
/// # Summary
/// `StateOracle` type for the preparation of a start state that has a
/// marked qubit entangled with some desired state in the database
/// register.
///
/// # Parameters
/// ## markedElements
/// Indices to marked elements in database.
///
/// # Returns
/// A `StateOracle` type with signature
/// ((Int, Qubit[]) => (): Adjoint, Controlled).
function SetupGroverStateOracle(markedElements : Int[]) : StateOracle
{
return StateOracle(SetupGroverStateOracleImpl(markedElements, _, _));
}
// Execute Search function
/// # Summary
/// Grover's search algorithm using library functions.
///
/// # Parameters
/// ## markedElements
/// Indices to marked elements in database.
/// ## nIterations
/// Number of iterations of the Grover iteration to apply.
/// ## idxMarkedQubit
/// Index to `MarkedQubit`.
///
/// # Returns
/// Unitary implementing Grover's search algorithm.
///
function ExecuteSearch( markedElements: Int[], nIterations: Int, idxMarkedQubit: Int) : (Qubit[] => Unit : Adjoint, Controlled)
{
return AmpAmpByOracle(nIterations, SetupGroverStateOracle(markedElements), idxMarkedQubit);
}
// ExecuteGroversAlgorithm Operation
/// # Summary
/// Performs quantum search for the marked elements and returns an index
/// to the found element in integer format.
///
/// # Parameters
/// ## markedElements
/// Indices to marked elements in database.
/// ## nIterations
/// Number of applications of the Grover iterate (RS · RM).
/// ## nDatabaseQubits
/// Number of qubits in the database register.
///
/// # Returns
/// Measurement outcome of marked Qubit and measurement outcomes of
/// the database register converted to an integer.
operation ExecuteGroversAlgorithm( markedElements: Int[], nIterations : Int, nDatabaseQubits : Int) : (Result,Int) {
body(...){
mutable resultSuccess = Zero;
mutable numberElement = 0;
using (qubits = Qubit[nDatabaseQubits+1]) {
let markedQubit = qubits[0];
let databaseRegister = qubits[1..nDatabaseQubits];
(ExecuteSearch( markedElements, nIterations, 0))(qubits);
set resultSuccess = M(markedQubit);
let resultElement = MultiM(databaseRegister);
set numberElement = PositiveIntFromResultArr(resultElement);
ResetAll(qubits);
}
return (resultSuccess, numberElement);
}
}
}
namespace Bernstein {
open Microsoft.Quantum.Primitive;
open Microsoft.Quantum.Canon;
// GetFourierSamplingParity Operation
/// # Summary
/// ParityViaFourierSampling implements the Bernstein-Vazirani quantum algorithm.
/// # Parameters
/// ## Uf
/// A quantum operation that implements |𝑥〉|𝑦〉 ↦ |𝑥〉|𝑦 ⊕ 𝑓(𝑥)〉,
/// where 𝑓 is a Boolean function that implements a parity Σᵢ 𝑟ᵢ 𝑥ᵢ.
/// ## n
/// The number of bits of the input register |𝑥〉.
///
/// # Returns
/// An array of type `Bool[]` that contains the parity 𝑟⃗ = (𝑟₀, …, 𝑟ₙ₋₁).
///
operation GetFourierSamplingParity (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]);
}
Message($"measure: {resultArray}");
return BoolArrFromResultArr(resultArray);
}
// ExecuteParityImpl Operation
operation ExecuteParityImpl (pattern : Bool[], qs : Qubit[]) : Unit {
let n = Length(pattern);
if (Length(qs) != n + 1) {
fail "Length of qs should be equal to pattern length + 1.";
}
for (idx in 0 .. n - 1) {
if (pattern[idx]) {
Controlled X([qs[idx]], qs[n]);
}
}
}
/// ExecuteParity function
/// # Summary
/// an operation implementing a unitary 𝑈
/// # Parameters
/// ## pattern
/// The bitstring 𝑟⃗ used to define the function 𝑓.
///
/// # Returns
/// An operation implementing 𝑈.
function ExecuteParity (pattern : Bool[]) : (Qubit[] => Unit) {
return ExecuteParityImpl(pattern, _);
}
// ExecuteBernsteinVaziraniAlgorithm Operation
operation ExecuteBernsteinVaziraniAlgorithm (nQubits : Int, patternInt : Int) : Int {
let pattern = BoolArrFromPositiveInt(patternInt, nQubits);
let result = GetFourierSamplingParity(ExecuteParity(pattern), nQubits);
return PositiveIntFromBoolArr(result);
}
}The Driver file will have the following code to execute Grovers Algorithm.
using System;
using Microsoft.Quantum.Simulation.Core;
using Microsoft.Quantum.Simulation.Simulators;
namespace Grovers
{
class Driver
{
static void Main(string[] args)
{
int successfulCnt = ExecuteSearchAlgorithm(100,20);
successfulCnt = ExecuteSearchAlgorithm(100, 3);
successfulCnt = ExecuteSearchAlgorithm(100, 2);
successfulCnt = ExecuteSearchAlgorithm(100, 1);
successfulCnt = ExecuteSearchAlgorithm(100, 0);
}
static int ExecuteSearchAlgorithm(int repeats, int groverIterations)
{
int successfulCount = 0;
using (var sim = new QuantumSimulator(throwOnReleasingQubitsNotInZeroState: true))
{
int nDatabaseQubits = 8;
var databaseSize = Math.Pow(2.0, nDatabaseQubits);
QArray<long> markedElements = new QArray<long>() {23};//{ 0, 39, 101, 234 }};
int nIterations = groverIterations;
for (int i = 0; i < repeats; ++i)
{
var task = ExecuteGroversAlgorithm.Run(sim, markedElements, nIterations, nDatabaseQubits);
var result = task.Result;
if (result.Item1 == Result.One)
{
successfulCount++;
}
}
}
Console.WriteLine(
$"Grover-Iterations {groverIterations}: {successfulCount} of {repeats} had the desired result.");
return successfulCount;
}
}
}
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:
Q# laatste nieuws 