Recursive Fourier sampling

To present the recursive Fourier sampling (RFS) problem, we begin by defining a type of tree. Let and be positive integers and consider a symmetric tree where each node, except the leaves, has children, and the depth is . Let the root be labeled by . The root’s children are labeled with . Each child of is, in turn, labeled with . We continue until we have reached the leaves, which are labeled by . Thus each node’s label can be thought of as a path describing how to find the node from the root.

Now we add the Fourier component to a tree. We begin by fixing an efficiently computable function . With each node of the tree , we associate a "secret" string . These secrets are promised to obey and the inner product has taken modulo 2. If , we take to mean . In this way, each node’s secret encodes one bit of information about its parent’s secret.

Now suppose that we are given an oracle which behaves as Note that works for the leaves of the tree only. Our goal is to find . This is the recursive Fourier sampling problem.

The recursive nature of the RFS problem is obvious. First, note that the subtree rooted at any node obeys the same promises as the whole tree. Thus each subtree defines an RFS problem. (The subtree rooted at a leaf is a trivial problem, where the oracle just returns the solution.) Thus we have a methodology for solving RFS problems: solve subtrees in order to determine information about the root’s secret, then calculate the secret. Solving subtrees uses the same method, except when we reach a leaf, where the oracle is used instead. This is a type of top-down recursive structure, where the tree is built from a number of subtrees with the same structure.

Before presenting the quantum solution, we first define the behavior of oracles and : The main idea behind the algorithm is to use the fact that transforms into and vice versa. We have phase feedback and a call to to create the state , then apply to obtain . After calculating , we uncompute to disentangle this register from others.

The process of algorithm QRFS is as follows:

  Input: oracle and (G), , quantum registers

​    1. If then apply to , then return.

​   2. Introduce ancilla in the state

​   3. Introduce ancilla in state

​   4. Call

​   5. Apply on register .

​   6. Apply to .

​   7. Apply on register .

​   8. Call

​   9. Discard and .

Now, we use isQ to compose an example of solving RFS. We set . So there are two labels , each one is 2 bits. is a unitary gate acting on 5 bits, and acts on 3 bits. Implement the function recursive_fourier_sampling according to the above algorithm process.

In this example, according to the previous formula, we can calculate . So the measurement result of should be 1

import std;

oracle A(4,1) = [0,1,1,0,0,0,0,0,0,0,1,1,0,1,0,1];
oracle g(2,1) = [0,1,1,0]; 

int a;
qbit q[4], p[3];

procedure hadamard_layer(int k){
    H(q[2*k]);
    H(q[2*k+1]);
}

procedure recursive_fourier_sampling(int k){
    if (k == 2){
        A(q[0], q[1], q[2], q[3], p[2]);
    }else{
        hadamard_layer(k);
        X(p[k+1]);
        H(p[k+1]);

        recursive_fourier_sampling(k+1);

        hadamard_layer(k);
        g(q[2*k],q[2*k+1], p[k]);
        hadamard_layer(k);

        recursive_fourier_sampling(k+1);

        hadamard_layer(k);
        H(p[k+1]);
        X(p[k+1]);
    }
}

procedure main(){
    a = 0;
    recursive_fourier_sampling(a);
    print M(p[0]);
}

Reference

  1. McKague, Matthew. "Interactive proofs with efficient quantum prover for recursive Fourier sampling." arXiv preprint arXiv:1012.5699, 2010.

  2. Ethan Bernstein and Umesh Vazirani. Quantum complexity theory. SIAM Journal on Computing, 26(5):1411–1473, 1997.