qiskit.circuit.library.fourier_checking

qiskit.circuit.library.fourier_checking(f, g)

Fourier checking circuit.

The circuit for the Fourier checking algorithm, introduced in [1], involves a layer of Hadamards, the function $f$, another layer of Hadamards, the function $g$, followed by a final layer of Hadamards. The functions $f$ and $g$ are classical functions realized as phase oracles (diagonal operators with {-1, 1} on the diagonal).

The probability of observing the all-zeros string is $p(f,g)$. The algorithm solves the promise Fourier checking problem, which decides if f is correlated with the Fourier transform of g, by testing if $p(f,g) <= 0.01$ or $p(f,g) >= 0.05$, promised that one or the other of these is true.

The functions $f$ and $g$ are currently implemented from their truth tables but could be represented concisely and implemented efficiently for special classes of functions.

Fourier checking is a special case of $k$-fold forrelation [2].

Reference Circuit:

from qiskit.circuit.library import fourier_checking
circuit = fourier_checking([1, -1, -1, -1], [1, 1, -1, -1])
circuit.draw('mpl')

Reference:

[1] S. Aaronson, BQP and the Polynomial Hierarchy, 2009 (Section 3.2). arXiv:0910.4698

[2] S. Aaronson, A. Ambainis, Forrelation: a problem that optimally separates quantum from classical computing, 2014. arXiv:1411.5729

Parameters

• f (Sequence[int]) –
• g (Sequence[int]) –

Return type

QuantumCircuit