Phase polynomial synthesis

Phase polynomials form another efficiently representable class of unitary operators. They take the following form:

$$ \sum_{x} e^{2i\pi f(x)} |x\rangle\langle x| $$

where $f: x \mapsto \sum_{y \in \mathbb{F}_2^n} \hat{f}(y) (x\cdot y)$, with Fourier coefficients $\hat{f}$.

This definition is sometimes relaxed to: $$ \sum_{x} e^{2i\pi f(x)} |Ax\rangle\langle x| $$

where $A$ is a linear boolean operator.

These corresponds to unitary that can be implemented using CNOT and RZ gates.

They are usually described by a collection of pairs $(y, \hat{f}(y))$ of non-zero Fourier coefficients.

from qat.lang.AQASM import Program, CNOT, PH
from qat.synthopline.phase_polynomials import extract_phase_polynomial

prog = Program()
qbits = prog.qalloc(3)
CNOT(qbits[0], qbits[1])
PH(prog.new_var(float, "a"))(qbits[1])
CNOT(qbits[1], qbits[2])
PH(prog.new_var(float, "b"))(qbits[2])
CNOT(qbits[2], qbits[0])
PH(prog.new_var(float, "c"))(qbits[0])
circuit = prog.to_circ()
circuit.display()

phase_poly, table = extract_phase_polynomial(circuit)
print("Fourier coefficients:")
for parity, angle in phase_poly.items():
    print(parity, angle)
print("Final linear operator:")
print(table)

Fourier coefficients:
(1, 1, 0) a
(1, 1, 1) b
(0, 1, 1) c
Final linear operator:
[[0 1 1]
 [1 1 0]
 [1 1 1]]

Synthesising phase polynomials

The method qat.synthopline.phase_polynomials.phase_polynomial_synthesis automatically produces a quantum circuit implementing a phase polynomial described by a dictionnary of Fourier coefficients.

The default behavior is to call an algorithm called GraySynth (see the documentation for references).

By default, the method will make sure that the resulting circuit implements exactly the phase polynomial by synthesizing the final linear operator:

from qat.synthopline.phase_polynomials import phase_polynomial_synthesis
new_circuit, final_table = phase_polynomial_synthesis(phase_poly)
new_circuit.display()
print(final_table)

[[1 0 0]
 [0 1 0]
 [0 0 1]]

It is possible to skip this step to save up on CNOTs (depending on the application):

from qat.synthopline.phase_polynomials import phase_polynomial_synthesis
new_circuit, final_table = phase_polynomial_synthesis(phase_poly, synthesize_final=False)
new_circuit.display()
print(final_table)

[[1 0 0]
 [1 1 0]
 [0 0 1]]

Architecture aware synthesis

The phase_polynomial_synthesis method can also produce harware compatible quantum circuits.

Two different backend methods have this ability: gray_synth_on_graph and lazy_synthesis.

They both need a connectivity graph to work on:

from qat.synthopline.phase_polynomials import random_phase_polynomial
from qat.devices import GridDevice
device = GridDevice(3, 3)
print(device)

phase_poly = random_phase_polynomial(9, 5)

circuit, table = phase_polynomial_synthesis(phase_poly, method="gray_synth_on_graph", graph=device.as_graph(), synthesize_final=False)
circuit.display()
circuit, table = phase_polynomial_synthesis(phase_poly, method="lazy_synth", depth=6, graph=device.as_graph(), synthesize_final=False)
circuit.display()

0 -- 1 -- 2
|    |    |    
|    |    |    
3 -- 4 -- 5
|    |    |    
|    |    |    
6 -- 7 -- 8