Quantum Fourier Sampling and Q#

Motivation

Quantum Computing is a recent interest for me and I don't unerstand many basics yet, however I am very impressed with the promises and all the research already proving success. This posts motivation is to contibute to the Microsoft Q# Advent Calendar initiated by Mariia Mykhailova.

I have mainly benefited from Umesh Vezirani's Quantum Computing training videos and the PDF's I found from edX. I will focus on the Non-recursive Bernstein-Vezirani Algorithm. In the beginning scientists were thinking that quantum computing may have additional boundaries and may not be able to compute everything that a classical computer does. The importance of this agoritm is that, it clearly shows a problem where quantum computing can actually have advantages over classical computing.

The Problem

We are given a n bit function f : {0, 1} n → {0, 1} which outputs a single bit, think of it like a black box and we don't know how this function does what it does at this point. This function is guaranteed to be of the form fs(x) = x · s where s is an unknown n bit string and x · s = x1s1 + x2s2 + · · · + xnsn mod 2. The goal of the Bernstein-Vazirani problem is to find the unknown string s.

You can imagine as a circuit with n legs, with n inputs and one output. Inside the circuit there is a hidden n bit multplier circuit, when this multiplication is done with the input, the sum of result terms in mod 2 produces the output we want.

Solution

Classical solution : A single query to the function can retrieve at most one bit of information about s (because f outputs only one bit.) Thus the exact query complexity must be at least n. An example algorithm may look like : Set a single input bit 1 and the rest 0, do a query for each of the input bits this way and the sum of result string for each single input will tell us the secret.

Quantum solution : We need to understand the problem deeper. The multplication of x1 and s1 terms would contribute to the x.s if and only if both x1 and s1 are equal to 1. Looks like a parity problem.

Perhaps we can look at available quantum gates and see if they are any use. Looking at a Hadamard Transform formula gives us a clue, it may be similar to what we want.

Perform Hadamard on two qubits = for 00, ½|00> + ½|01> + ½|10> + ½|11>
                                                            for 01, ½|00> - ½|01> + ½|10> - ½|11>
                                                            for 10, ½|00> + ½|01> - ½|10> - ½|11>
                                                            for 11, ½|00> - ½|01> - ½|10> + ½|11>

Observe that only the signs are changing, depending on where the 1 is. For n bits of input, Hadamard gives us 2n superposition of n bits, with different sign pattern for each input. When we measure this set of qubits in superposition, we get insight into how the amplitudes of inputs are affecting the output amplitude.

s1,s2,…,sn input bits
x1,x2,…,xn output (n bit strings, x E {0,1}n
n = 3
s = 111, x = 101
ux = 1.1+1.0+1.1 = 2  
(-1)sx / 2n/2 = (-1)2/23/2

General form of Hadamard Transform for |s>:
12n−−√∑x∈{0,1}n(−1)s⋅x|x⟩.

Because the sign of the x is dependant on the evennes/oddness of the matching 1 values of x and s, the fs transformation becomes:
|x⟩−→fs|x⟩=(−1)s⋅x|x⟩.

Using a "0" input in a Hadamard transform and then applying the fs:
s: 
|0⟩−→−H⊗n12n−−√∑x∈{0,1}n|x⟩−→fs12n−−√∑x∈{0,1}n(−1)s⋅x|x⟩.

Running the secret string trough Hadamard is equivalent to running a "0" trough Hadamard and then running the qubits in superposition trough the function which contains the secret.

In our case we don't have the secret, we are trying to find it. We have the function itself and can provide as many zeros as the length of the secret. Then all we need to do is to run the output of the black box which was fed with qubits in superposition once more trough the Hadamard and measure to get the secret.



Below is some Q# code, implementing the algorithm. I made use of the Simple Algorithms sample provided by Microsoft. I tried to explain parts which were not so obvious for me, like what a Control expression is or what a within/apply block is. The operation takes an integer input such as 15 (which actually is the secret we are trying to find by running the operation). Then it prints the secret it found. For secret  = 15, it will print "One, One, One" as it's limited to 3 qubits, (15 mod 8) = 7 = "111".

The better implementation given at the above link is taking the black box function as a parameter however may be more difficult to understand for a beginner.

namespace Quantum.QSharpApplicationTest
{
    open Microsoft.Quantum.Intrinsic;
    open Microsoft.Quantum.Canon;
    open Microsoft.Quantum.Measurement;
    open Microsoft.Quantum.Arrays;
    open Microsoft.Quantum.Convert;
    open Microsoft.Quantum.Math;

    operation BernsteinVezirani_QuantumFourierSampling (patternInt: Int) : Unit {

        let nQubits = 3; // number of  qubits used to represent s;
        let pattern = ModI (patternInt, PowI (2, nQubits)); // the hidden integer, making sure it fits the size of Qubits we have
        let s = IntAsBoolArray (pattern, nQubits); // Convert it into a bit array

        using ((queryRegister, target) = (Qubit[nQubits], Qubit ())) {

            X (target);

            // Initialize query register, setting all to 0
            for (bit in queryRegister) {
                if (Zero != M (bit)) {
                    X (bit);
                }
            }

            // within/apply block is used to implement a conjugation
// In our case, outer operation is applying Hadamard
            //    outerOperation(target);
            //    innerOperation(target);
            //    Adjoint outerOperation(target);

            within { //Outer operation
                // Put qbits in superposition
                for (bit in queryRegister) {
                    H (bit);
                }
                H (target);
            }
            apply { //Inner operation
                // Run the black box function with the secret provided
                // The Controlled X is eqivalent to the CNOT, so we are actually toggling the target each time pattern is 1
                for ((patternBit, controlQubit) in Zip (s, queryRegister)) {
                    if (patternBit) {
                        Controlled X ([controlQubit], target);
                    }
                }
            }

            let parity = M (target);
            Message ($"Parity operation result : {parity}");

            // MResetZ operation measures in Z base and resets,
            // foreach runs this operation on each element of the queryRegister
            let resultArray = ForEach (MResetZ, queryRegister);

            Reset (target);

            Message ($"Measured secret: {resultArray}");

        }

    }

}


Host Program in C#

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

namespace Quantum.QSharpApplicationTest
{
    class Driver
    {
        static void Main(string[] args)
        {
            using (var qsim = new QuantumSimulator())
            {
                BernsteinVezirani_QuantumFourierSampling.Run(qsim, 15).Wait();
            }
        }
    }
}

References

Microsoft Q# Documentation

CSE 599d - Quantum Computing The Recursive and Nonrecursive Bernstein-Vazirani Algorithm Dave Bacon Department of Computer Science & Engineering, University of Washington

Qiskit Textbook 

Wikipedia

Yorumlar

Yorum Gönder