unoptimised_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


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."
    qr = QuantumRegister(register_size)
    circuit = QuantumCircuit(qr)
    circuit.h(qr[-1])
    circuit.mcx(qr[:-1], qr[-1])
    circuit.h(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)
    circuit = QuantumCircuit(q)
    circuit.h(q)
    circuit.x(q)
    circuit.append(mcz_gate, q)
    circuit.x(q)
    circuit.h(q)
    return circuit


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


def encode_problem(problem: BoardEncoding, problem_index: int) -> QuantumCircuit:
    """
    Encode the given problem on the qboard register if the
    qindex register matches the given problem_index.

    This function returns a quantum circuit that encodes the given problem
    on the |qboard> register only if the |qindex> register encodes the
    given problem_index.

    :param problem: a list of asteroid coordinates, given as tuples
        of strings.
    :param problem_index: the index of the board.
    """
    qindex = QuantumRegister(4)
    qboard = QuantumRegister(16)
    circuit = QuantumCircuit(qindex, qboard)

    bin_index = bin(problem_index)[2:].zfill(4)

    for i, bit_value in enumerate(bin_index):
        if bit_value == "0":
            circuit.x(qindex[i])

    for x, y in problem:
        cell_index = 4 * int(x) + int(y)
        circuit.mcx(qindex, qboard[cell_index])

    # Uncompute.
    # We do not have to reverse the order here because all the
    # gates can be executed in parallel.
    for i, bit_value in enumerate(bin_index):
        if bit_value == "0":
            circuit.x(qindex[i])

    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>.
    """
    qindex = QuantumRegister(4)
    qboard = QuantumRegister(16)
    circuit = QuantumCircuit(qindex, qboard)

    for problem_index, problem in enumerate(problem_set):
        circuit.append(
            encode_problem(problem, problem_index),
            # List of all the qubits we apply the problem encoding
            # procedure to.
            [*qindex, *qboard],
        )
    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 |qancilla> qubit is flipped if |qboard> includes the given
    permutation.
    """
    qboard = QuantumRegister(16)
    qancilla = QuantumRegister(1)
    circuit = QuantumCircuit(qboard, qancilla)

    qubit_indices = [4 * row + col for row, col in enumerate(permutation)]
    circuit.mcx([qboard[i] for i in qubit_indices], qancilla)

    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)

    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)
    circuit = QuantumCircuit(qboard, qadded, qcounter)

    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])
        circuit.append(add_gate, [*qadded, *qcounter])
        circuit.append(checker.inverse(), [*qboard, *qadded])

    circuit.z(qcounter)

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

    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
    - 16 qubits for the |board> register, that should be given in the
      |0> state.
    - 3 ancilla qubits.
    """
    qindex = QuantumRegister(4)
    qboard = QuantumRegister(16)
    qancilla = QuantumRegister(3)
    circuit = QuantumCircuit(qindex, qboard, qancilla)

    qram_gate = qram(problem_set)
    checker = check_if_match_any_permutation()

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

    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(3)
    cindex = ClassicalRegister(4)
    circuit = QuantumCircuit(qindex, qboard, qancilla, cindex)

    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)

    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)

# backend_sim = Aer.get_backend("qasm_simulator")
# job = execute(circuit, backend_sim, shots=8192)
# result = job.result()
# counts = result.get_counts()

# print(counts)

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