# This program is adapted for use as a benchmark in controlled software testing experiments.
# Modifications made to the original code include:
# - Structural reorganization to fit benchmarking framework:
# - Encapsulated functionality within a class inheriting from QuantumCircuit.
# - Alter `oracle: Gate` to `oracle: QuantumCircuit | Statevector` to support both circuit and statevector oracles.
# - Remove `ngate_bits` and the ancilla qubit from oracle application to match the usage of phase oracle.
# - Correct the formula for calculating the number of Grover iterations, since the target states may be more than one.
# - Make changes for compatibility with the phase oracle representation.
# - Input validation:
# - Check `oracle` type
# -----------------------------------------------------------------------------
# Original code: https://github.com/LuisLlana/metamorphic_testing/blob/main/adder_mod.py
# Original repository: https://github.com/LuisLlana/metamorphic_testing/tree/main
# Original author: Luis Llana
# Copyright (C) <original year> <original author>
#
# This program includes code licensed under the GNU General Public License v3.
# You can redistribute and/or modify it under the terms of the GNU GPL v3:
# https://www.gnu.org/licenses/gpl-3.0.html
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU GPL for details.
import math
from qiskit import QuantumCircuit
from qiskit.circuit import Gate
from qiskit.circuit.library import MCXGate
from qiskit.quantum_info import Statevector
import numpy as np
from qolumbina.programs.diagonal import Diagonal
'''
This functions habe been taken from
https://qiskit.org/textbook/ch-algorithms/grover.html
'''
# ---------- benchmark registration ----------
from ..benchmark_registry import register_benchmark
from pathlib import Path
@register_benchmark(
Path(__file__).stem,
family=Path(__file__).resolve().parent.name,
description="Construct a complete Grover search quantum circuit",
class_name="GroverSearch",
source={
"repo": "https://github.com/LuisLlana/metamorphic_testing/tree/main",
"file": "adder_mod.py",
"sdk": "Qiskit",
"available_doc": False
},
testability_refactoring=[
"Input validation",
"Structure reorganization"
],
)
def create_grover_search(
oracle: QuantumCircuit | Statevector,
steps: int | None = None,
barrier: bool = False
) -> QuantumCircuit:
return GroverSearch(oracle=oracle, steps=steps, barrier=barrier)
[docs]
class GroverSearch(QuantumCircuit):
r"""Grover's search algorithm circuit."""
def __init__(
self,
oracle: QuantumCircuit | Statevector,
steps: int | None = None,
barrier: bool = False,
name: str | None = None
):
r"""
Args:
oracle: The phase oracle implementing a reflection about the **bad** state(s).
Note that the number of qubits :math:`n` is inferred from the oracle.
steps: Number of Grover iterations to perform. If ``None``, it is calculated
as :math:`\left\lfloor \frac{\pi}{4} \sqrt{N/|T|} \right\rfloor`, where
:math:`N` is the total number of states and :math:`|T|` is the number of
target states.
barrier: Whether to insert barriers between steps for clarity.
name: Optional name for the circuit.
Raises:
TypeError: If ``oracle`` is not a ``QuantumCircuit`` or ``Statevector``.
ValueError: If ``oracle`` is a ``Statevector`` and its entries are not close to
either 0 or 1 (indicating an invalid phase oracle).
ValueError: If ``steps`` is ``None`` and cannot be calculated from the oracle
(e.g., if oracle is a QuantumCircuit and steps is not provided).
"""
if not isinstance(oracle, (QuantumCircuit, Statevector)):
raise TypeError("oracle must be a QuantumCircuit or Statevector")
if isinstance(oracle, Statevector):
# Check whether all entries are +/-1 (allow small numerical error)
if not all(np.isclose(abs(ampl), 1) or np.isclose(ampl, 0) for ampl in oracle.data):
raise ValueError("The entries of ``oracle`` in Statevector are either 0 or 1")
# Determine number of variable bits and Grover iterations
if isinstance(oracle, QuantumCircuit):
nvar_bits = oracle.num_qubits
if steps is None:
raise ValueError("When `oracle` is a QuantumCircuit, steps must be provided")
elif isinstance(oracle, Statevector):
nvar_bits = int(math.log2(len(oracle.data)))
num_targets = sum(1 for ampl in oracle.data if np.isclose(ampl, 1))
if steps is None:
steps = int(round(math.pi * math.sqrt(2 ** nvar_bits / num_targets) / 4))
self._nvar_bits = nvar_bits
self._grover_steps = steps
self._oracle = oracle # Note that it should be a phase oracle
self._steps = steps
self._insert_barriers = barrier
super().__init__(nvar_bits, name=name or "GroverSearch")
self._build()
[docs]
def diffuser(self, nqubits: int) -> Gate:
"""
Constructs the diffuser (inversion about the mean) operator for Grover's algorithm.
"""
qc = QuantumCircuit(nqubits)
# Apply transformation |s> -> |00..0> (H-gates)
for qubit in range(nqubits):
qc.h(qubit)
# Apply X to all qubits
for qubit in range(nqubits):
qc.x(qubit)
# Apply multi-controlled-Z
qc.h(nqubits - 1)
controls = list(range(nqubits - 1))
target = nqubits - 1
mcx = MCXGate(len(controls))
qc.append(mcx, controls + [target])
qc.h(nqubits - 1)
# Undo X gates
for qubit in range(nqubits):
qc.x(qubit)
# Undo H gates
for qubit in range(nqubits):
qc.h(qubit)
U_s = qc.to_gate()
U_s.name = "Diffuser"
return U_s
[docs]
def grover_step(
self,
nvar_bits: int,
oracle_gate: Gate,
diffuser_gate: Gate
) -> QuantumCircuit:
"""
Constructs a single Grover iteration step consisting of the oracle and diffuser.
"""
qc = QuantumCircuit(nvar_bits)
# The original code is retained as follows:
# `qc.append(oracle_gate, range(nvar_bits + ngate_bits + 1))``
# However, it appears that the phase oracle should only act on the variable qubits.
qc.append(oracle_gate, range(nvar_bits))
qc.append(diffuser_gate, range(nvar_bits))
return qc
def _build(self):
"""
Constructs the full Grover search circuit.
- Initializes input qubits in uniform superposition and output qubit in |-> state
- Calculates the number of Grover iterations more robustly
- Generates the diffuser gate once and reuses it
"""
nvar_bits = self._nvar_bits
# Prepare oracle gate
if isinstance(self._oracle, Statevector):
# Create reflection about the statevector
diag = Diagonal((-1) ** self._oracle.data).to_gate() # type: ignore
oracle_gate = diag
else:
oracle_gate = self._oracle.to_gate(label="Oracle")
# Unnecessary output qubit preparation removed, as we use phase oracle
# # Initialize output bit to |-> state
# self.x(nvar_bits)
# self.h(nvar_bits)
# Initialize input bits in uniform superposition
self.h(range(nvar_bits))
if self._insert_barriers:
self.barrier()
# Generate diffuser once
diffuser = self.diffuser(nvar_bits)
# Grover iterations
for _ in range(self._grover_steps):
self.append(
self.grover_step(
nvar_bits,
oracle_gate,
diffuser
).to_gate(label='Oracle+Diffuser'),
range(nvar_bits)
)
if self._insert_barriers:
self.barrier()