FourierChecking

class qiskit.circuit.library.FourierChecking(f, g)

Bases: QuantumCircuit

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:

[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

Create Fourier checking circuit.

Parameters

• f (Sequence[int]) – truth table for f, length 2**n list of {1,-1}.
• g (Sequence[int]) – truth table for g, length 2**n list of {1,-1}.

Raises

CircuitError – if the inputs f and g are not valid.

Reference Circuit:

Attributes

name

from qiskit import QuantumCircuit

qc = QuantumCircuit(2, 2, name="my_circuit")
print(qc.name)

my_circuit