gusucode.com > qit_matlab_0.10.0工具箱源码程序 > qit/examples/bernstein_vazirani.m

    function p = bernstein_vazirani(n, linear)
% BERNSTEIN_VAZIRANI  Bernstein-Vazirani algorithm demo.
%  p = bernstein_vazirani(n, linear)
%
%  Simulates the Bernstein-Vazirani algorithm, which, given a black box oracle
%  implementing a linear Boolean function f_a(x) := a \cdot x, returns the bit
%  vector a (and thus identifies the function) with just a single oracle call.
%  If the oracle function is not linear, the algorithm will fail.

%! See \cite{BV}.
% Ville Bergholm 2011-2014

fprintf('\n\n=== Bernstein-Vazirani algorithm ===\n')
fprintf('\nUsing %d qubits.', n);

if nargin < 2
    linear = true;
end


dim = qubits(n);
H = gate.walsh(n); % n-qubit Walsh-Hadamard gate
N = 2^n;

% random black box oracle encoding the Boolean function f (given as the diagonal)
if linear
    % linear f
    a = (rand(1, n) > 0.5) +0;
    f = linear_func(a);
    fprintf('\nUsing the linear function f_a(x) := dot(a, x), defined by the binary vector\n');
    a
else
    % general f
    f = (rand(1, N) > 0.5) +0;
    % special case: not(linear)
    %a = (rand(n, 1) > 0.5) +0; 
    %f = 1-linear_func(a);
    fprintf('\nNonlinear function f:\n');
    f
end
U_oracle = oracle(f);

% start with all-zero state
s = state(0, dim);
% initial superposition
s = s.u_propagate(H);
% oracle phase flip
s.data = U_oracle .* s.data;
% final Hadamards
s = s.u_propagate(H);

figure();
s.plot();
tt = 'Bernstein-Vazirani algorithm, ';
if linear
    temp = 'linear oracle';
else
    temp = 'nonlinear oracle (fails)';
end
tt = [tt, temp];
title(tt);

[p, res] = measure(s);
% measured binary vector
b = unravel_index(res, dim) -1;
fprintf('\nMeasured binary vector\n');
b
if ~linear
    g = linear_func(b);
    fprintf('\nCorresponding linear function g_b:\n');
    g
    fprintf('\nNormalized Hamming distance: |f - g_b| = %g.\n', sum(abs(f-g)) / N);
end
end


function U = oracle(f)
% Returns a unitary oracle for the Boolean function f(x), given as a truth table.
    U = (-1) .^ f.';
end
    
function f = linear_func(a)
% Builds the linear Boolean function f(x) = a \cdot x as a truth table.
    n = length(a);
    dim = qubits(n);
    N = prod(dim);
    f = zeros(1, N);
    for ind = 1:N
        % convert each index ind into the corresponding bitstring x
        x = unravel_index(ind, dim) -1;  % into zero-based multi-index
        % compute f(x)
        f(ind) = mod(dot(a, x), 2);
    end
end