optimisation2_solution_quantum_challenge_2020.py

import typing as ty
from itertools import permutations

from qiskit import (Aer, ClassicalRegister, QuantumCircuit, QuantumRegister,
                    execute)
from qiskit.transpiler import PassManager
from qiskit.transpiler.passes import Unroller
from qprof import profile


def mcz(register_size: int) -> QuantumCircuit:
    """Returns a multi-controlled Z gate."""
    assert register_size > 1, "Cannot apply a multi-controlled Z without any control."
    ancilla_size = max(0, register_size - 2)
    qr = QuantumRegister(register_size)
    if ancilla_size > 0:
        qa = QuantumRegister(ancilla_size)
        circuit = QuantumCircuit(qr, qa, name="mcz")
        circuit.h(qr[-1])
        circuit.mcx(qr[:-1], qr[-1], qa, mode="v-chain")
        circuit.h(qr[-1])
    else:
        circuit = QuantumCircuit(qr, name="mcz")
        circuit.cz(qr[:-1], qr[-1])
    return circuit


def U_amp(qubit_numbers: int) -> QuantumCircuit:
    """Apply the amplification step of Grover's algorithm."""
    mcz_gate = mcz(qubit_numbers)

    q = QuantumRegister(qubit_numbers)
    if qubit_numbers > 2:
        qancill = QuantumRegister(qubit_numbers - 2)
        circuit = QuantumCircuit(q, qancill, name="U_amp")
    else:
        qancill = list()
        circuit = QuantumCircuit(q, name="U_amp")
    circuit.h(q)
    circuit.x(q)
    circuit.append(mcz_gate, [*q, *qancill])
    circuit.x(q)
    circuit.h(q)
    return circuit


BoardEncoding = ty.List[ty.Tuple[str, str]]


def encode_problem(problem: BoardEncoding) -> QuantumCircuit:
    """
    Encode the given problem on the qboard register if the
    qstate register is in the |1> state.

    This function returns a quantum circuit that encodes the given problem
    on the |qboard> register only if the |qstate> register is |1>.

    :param problem: a list of asteroid coordinates, given as tuples
        of strings.
    """
    qboard = QuantumRegister(16)
    qstate = QuantumRegister(1)
    circuit = QuantumCircuit(qboard, qstate, name="encode_problem")

    for x, y in problem:
        index = 4 * int(x) + int(y)
        circuit.cx(qstate[0], qboard[index])
    return circuit


def qram(problem_set: ty.List[BoardEncoding]):
    """
    Encodes the given problem set into the |qboard> register.

    The returned routine takes as inputs:
    - |qindex> that encodes the indices for which we want to encode the
      boards. The |qindex> register will likely be given in a
      superposition of all the possible states.
    - |qboard> that should be given in the |0> state and that is returned
      in the state that encodes the problem_set given. For each qindex,
      the |qboard> state in |qindex>|qboard> is full of |0> except on the
      locations where there is an asteroid, in which case the state is |1>.
    - |qancilla> that is a 3-qubit ancillary register.
    """
    qindex = QuantumRegister(4)
    qboard = QuantumRegister(16)
    qstate = QuantumRegister(1)
    qancilla = QuantumRegister(2)
    circuit = QuantumCircuit(qindex, qboard, qstate, qancilla, name="qram")

    for i, problem in enumerate(problem_set):
        bin_str = bin(i)[2:].zfill(4)
        x_qubits = [j for j in range(4) if bin_str[j] == "0"]
        # setting qstate to |1> if we are in the index "i".
        if x_qubits:
            circuit.x([qindex[j] for j in x_qubits])
        circuit.mcx(qindex, qstate, ancilla_qubits=qancilla, mode="v-chain")
        circuit.append(encode_problem(problem), [*qboard, *qstate])
        # Undo the qstate thing
        circuit.mcx(qindex, qstate, ancilla_qubits=qancilla, mode="v-chain").inverse()
        if x_qubits:
            circuit.x([qindex[j] for j in x_qubits]).inverse()
    return circuit


def check_if_match_permutation(permutation: ty.List[int]) -> QuantumCircuit:
    """
    Construct a quantum circuit to check if the given qboard state
    "includes" the given permutation.

    The |qresult> qubit is flipped if |qboard> includes the given
    permutation.
    """
    qboard = QuantumRegister(16)
    qresult = QuantumRegister(1)
    qancilla = QuantumRegister(2)
    circuit = QuantumCircuit(
        qboard, qresult, qancilla, name="check_if_match_permutation"
    )

    qubit_indices = [4 * row + col for row, col in enumerate(permutation)]
    circuit.mcx(
        [qboard[i] for i in qubit_indices],
        qresult,
        ancilla_qubits=qancilla,
        mode="v-chain",
    )

    return circuit


def get_2_qubit_adder_gate():
    """
    Returns a quantum circuit implementing an adder.

    The adder adds a 1-qubit value to a 2-bit register without
    any overflow check.
    """
    a = QuantumRegister(1)
    b = QuantumRegister(2)
    circuit = QuantumCircuit(a, b, name="2_qubit_adder_gate")

    circuit.ccx(a, b[0], b[1])
    circuit.cx(a, b[0])

    return circuit


def check_if_match_any_permutation():
    """
    Flip the phase of the boards that include at least 1 permutation.

    This quantum circuit takes a board on 16 qubits and flip the phase
    of the quantum state if the board includes at least 1 permutation.
    """
    qboard = QuantumRegister(16)
    qadded = QuantumRegister(1)
    qcounter = QuantumRegister(2)
    qancilla = QuantumRegister(2)
    circuit = QuantumCircuit(
        qboard, qadded, qcounter, qancilla, name="check_if_match_any_permutation"
    )

    add_gate = get_2_qubit_adder_gate()
    all_permutations = list(permutations(range(4), 4))

    for perm in all_permutations:
        checker = check_if_match_permutation(perm)
        circuit.append(checker, [*qboard, *qadded, *qancilla])
        circuit.append(add_gate, [*qadded, *qcounter])
        circuit.append(checker.inverse(), [*qboard, *qadded, *qancilla])

    circuit.z(qcounter)

    for perm in reversed(all_permutations):
        checker = check_if_match_permutation(perm)
        circuit.append(checker.inverse(), [*qboard, *qadded, *qancilla])
        circuit.append(add_gate.inverse(), [*qadded, *qcounter])
        circuit.append(checker, [*qboard, *qadded, *qancilla])

    return circuit


def grover_oracle_week3(problem_set) -> QuantumCircuit:
    """
    Flip the phase of the only index representing a non-solvable board.

    This oracle needs a total of 23 qubits:
    - 4 qubits for the |index> register
 qubits for the |board> register, that should be given in the
      |0> state.
    - 3 ancilla qubits.
    """
    qindex = QuantumRegister(4)
    qboard = QuantumRegister(16)
    qancilla = QuantumRegister(5)
    circuit = QuantumCircuit(qindex, qboard, qancilla, name="grover_oracle_week3")

    qram_gate = qram(problem_set)
    checker = check_if_match_any_permutation()

    circuit.append(qram_gate, [*qindex, *qboard, *qancilla[:3]])
    circuit.append(checker, [*qboard, *qancilla])
    circuit.append(qram_gate.inverse(), [*qindex, *qboard, *qancilla[:3]])

    return circuit


def week3_ans_func(problem_set) -> QuantumCircuit:
    """
    Returns a quantum circuit solving the given problem.
    """
    qindex = QuantumRegister(4)
    qboard = QuantumRegister(16)
    qancilla = QuantumRegister(5)
    cindex = ClassicalRegister(4)
    circuit = QuantumCircuit(qindex, qboard, qancilla, cindex, name="week3_ans_func")

    oracle = grover_oracle_week3(problem_set)
    diffusion = U_amp(4)

    circuit.h(qindex)

    # Perform only 1 iteration to stick to the rules.
    for _ in range(1):
        circuit.append(oracle, [*qindex, *qboard, *qancilla])
        circuit.append(diffusion, [*qindex, *qancilla[:2]])

    circuit.measure(qindex, cindex)
    circuit = circuit.reverse_bits()
    return circuit


def cost(circuit: QuantumCircuit) -> int:
    """Compute the cost of a circuit"""
    pass_ = Unroller(["u3", "cx"])
    pm_unroll = PassManager(pass_)
    unrolled_circuit = pm_unroll.run(circuit)
    ops = unrolled_circuit.count_ops()
    return 10 * ops.get("cx", 0) + ops.get("u3", 0)


problem_set = [
    [["0", "2"], ["1", "0"], ["1", "2"], ["1", "3"], ["2", "0"], ["3", "3"]],
    [["0", "0"], ["0", "1"], ["1", "2"], ["2", "2"], ["3", "0"], ["3", "3"]],
    [["0", "0"], ["1", "1"], ["1", "3"], ["2", "0"], ["3", "2"], ["3", "3"]],
    [["0", "0"], ["0", "1"], ["1", "1"], ["1", "3"], ["3", "2"], ["3", "3"]],
    [["0", "2"], ["1", "0"], ["1", "3"], ["2", "0"], ["3", "2"], ["3", "3"]],
    [["1", "1"], ["1", "2"], ["2", "0"], ["2", "1"], ["3", "1"], ["3", "3"]],
    [["0", "2"], ["0", "3"], ["1", "2"], ["2", "0"], ["2", "1"], ["3", "3"]],
    [["0", "0"], ["0", "3"], ["1", "2"], ["2", "2"], ["2", "3"], ["3", "0"]],
    [["0", "3"], ["1", "1"], ["1", "2"], ["2", "0"], ["2", "1"], ["3", "3"]],
    [["0", "0"], ["0", "1"], ["1", "3"], ["2", "1"], ["2", "3"], ["3", "0"]],
    [["0", "1"], ["0", "3"], ["1", "2"], ["1", "3"], ["2", "0"], ["3", "2"]],
    [["0", "0"], ["1", "3"], ["2", "0"], ["2", "1"], ["2", "3"], ["3", "1"]],
    [["0", "1"], ["0", "2"], ["1", "0"], ["1", "2"], ["2", "2"], ["2", "3"]],
    [["0", "3"], ["1", "0"], ["1", "3"], ["2", "1"], ["2", "2"], ["3", "0"]],
    [["0", "2"], ["0", "3"], ["1", "2"], ["2", "3"], ["3", "0"], ["3", "1"]],
    [["0", "1"], ["1", "0"], ["1", "2"], ["2", "2"], ["3", "0"], ["3", "1"]],
]

circuit = week3_ans_func(problem_set)

print(f"Cost of the generated quantum circuit: {cost(circuit)}")