mqgrover.py

""" Given a system of quadratic equations over F_2, output a quantum
    circuit (in Nielsen and Chuang's qasm format), that can be used
    as the oracle in Grover's algorithm, to solve it.

    We use a standard form for the system of equations.  A system of
    m quadratic equations over n variables is given by a `cube' (l^k_ij)
    over F_2 where l^k_ij = 0 if i > j.  x_1, ..., x_n is a solution if

        \sum_{1 <= i <= j <= n} l^k_ij x_i x_j = 1

    for each 1 <= k <= m.  """

# NOTE this file is autogenerated from mqgrover-{1,2,3}.py
def create_circuit(n, m, sqe):
    """ Creates Circuit for Grover oracle that solves the system of
        quadratic equations sqe over F_2 in standard form
    
            n: number of variables x_i in sqe
            m: number of equations in sqe
            sqe[k][i][j]: true if x_ix_j occurs in the k-th equation. """
    # First, create helper circuit that puts E^(k) into e_k
    E_circuit = Circuit()
    for k in range(1, m+1):
        for i in range(1, n+1):
            if not any(sqe[k-1][i-1]): continue
            # Another helper circuit, that XORs y_i^(k) into t
            y_circuit = Circuit()
            for j in range(i+1, n+1):
                if sqe[k-1][i-1][j-1]:
                    y_circuit.CNOT('x'+str(j), 't')
            if sqe[k-1][i-1][i-1]:
                y_circuit.X('t')

            # XOR the value (x_i AND  y_i^(k)) into e_k
            # and clear t afterwards
            E_circuit.extend(y_circuit)  # first put y_i^(k) into t
            E_circuit.toffoli('x'+str(i), 't', 'e'+str(k))
            E_circuit.extend(y_circuit.inverse())  # uncompute t

    # Now, assemble the whole circuit
    circuit = Circuit()
    circuit.extend(E_circuit)  # put E^(k) into e_k
    # put result into y
    circuit.add('toffoli{0}'.format(m),
                    ['e{0}'.format(i) for i in range(1,m+1)] + ['y'])
    circuit.extend(E_circuit.inverse())  # uncompute e_k
    return circuit
import sys
import textwrap

def main():
    n, m, sqe = parse_args()
    # Hack to let qasm use n-qubit toffoli gate:
    print("    def toffoli{0},{1},'o'".format(m, m))
    create_circuit(n, m, sqe).print_qasm()

def parse_args():
    if len(sys.argv) != 4:
        print(textwrap.dedent('   '+__doc__))
        print("")
        usg = ("usage: {0} [n] [m] [l^1_(1,1)][l^1_(1,2)]..."
                        "[l^1_(2,1)]...")
        print(usg.format(sys.argv[0]))
        sys.exit()
    n, m = int(sys.argv[1]), int(sys.argv[2])
    idx = 0
    ret = []
    for k in range(m):
        row = []
        for i in range(n):
            term = []
            for j in range(0, i):
                term.append(False)
            for j in range(i, n):
                term.append(bool(int(sys.argv[3][idx])))
                idx += 1
            row.append(term)
        ret.append(row)
    return n, m, ret


class Circuit:
    INVERSES = {'X': 'X',
                'toffoli': 'toffoli',
                'cnot': 'cnot'}
    def __init__(self, gates=None):
        self._gates = [] if gates is None else list(gates)
        self._registers = set()
        for gatename, args in self._gates:
            self._registers.update(args)

    def add(self, gatename, args):
        self._registers.update(args)
        self._gates.append((gatename, args))

    def extend(self, circuit):
        self._gates.extend(circuit._gates)
        self._registers.update(circuit._registers)

    def CNOT(self, reg1, reg2):
        self.add('cnot', (reg1, reg2))
    def X(self, reg):
        self.add('X', (reg,))
    def toffoli(self, reg1, reg2, reg3):
        self.add('toffoli', (reg1, reg2, reg3))

    def inverse(self):
        inverted_gates = [(Circuit.INVERSES[gate[0]], gate[1])
                                for gate in reversed(self._gates)]
        return Circuit(inverted_gates)

    def print_qasm(self):
        for reg in self._registers:
            print("    qubit {0}".format(reg))
        for regname, args in self._gates:
            print("    {0} {1}".format(regname, ','.join(args)))


if __name__ == '__main__':
    main()