Skip to content

Instantly share code, notes, and snippets.

@nelimee
Created December 9, 2020 15:15
Show Gist options
  • Save nelimee/addea854eb2099a3ad49fabe3734e96e to your computer and use it in GitHub Desktop.
Save nelimee/addea854eb2099a3ad49fabe3734e96e to your computer and use it in GitHub Desktop.
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)}")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment