Linear Toffoli-gate bound for simple periodic-function synthesis

Let pp be an odd period represented by an nn-bit binary number, and let SpS_p be a simple periodic function, namely a periodic injective function whose synthesized circuit minimizes the number NTN_T of Toffoli gates.

Toffoli-gate bound conjecture. To synthesize the circuit for SpS_p, one needs at most nn Toffoli gates:

NTn.N_T\leq n.

The bound is inferred from circuits computed for odd periods through five bits. Its validity for arbitrary bit-lengths is left conjectural.

Sources & referencesView supporting material

Primary source

Omar Gamel and Daniel F. V. James, “Synthesizing Quantum Circuits for Simple Periodic Functions”, arXiv:1305.3642 (2013).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.