"""This module implements the LEAPSynthesisPass."""
from __future__ import annotations
import logging
from typing import Any
import numpy as np
from scipy.stats import linregress
from bqskit.compiler.passdata import PassData
from bqskit.ir.circuit import Circuit
from bqskit.ir.opt.cost.functions import HilbertSchmidtResidualsGenerator
from bqskit.ir.opt.cost.generator import CostFunctionGenerator
from bqskit.passes.search.frontier import Frontier
from bqskit.passes.search.generator import LayerGenerator
from bqskit.passes.search.generators.seed import SeedLayerGenerator
from bqskit.passes.search.heuristic import HeuristicFunction
from bqskit.passes.search.heuristics import AStarHeuristic
from bqskit.passes.synthesis.synthesis import SynthesisPass
from bqskit.qis.state.state import StateVector
from bqskit.qis.state.system import StateSystem
from bqskit.qis.unitary import UnitaryMatrix
from bqskit.runtime import get_runtime
from bqskit.utils.typing import is_integer
from bqskit.utils.typing import is_real_number
_logger = logging.getLogger(__name__)
[docs]
class LEAPSynthesisPass(SynthesisPass):
"""
A pass implementing the LEAP search synthesis algorithm.
References:
Ethan Smith, Marc G. Davis, Jeffrey M. Larson, Ed Younis,
Lindsay Bassman, Wim Lavrijsen, and Costin Iancu. 2022. LEAP:
Scaling Numerical Optimization Based Synthesis Using an
Incremental Approach. ACM Transactions on Quantum Computing
(June 2022). https://doi.org/10.1145/3548693
"""
[docs]
def __init__(
self,
heuristic_function: HeuristicFunction = AStarHeuristic(),
layer_generator: LayerGenerator | None = None,
success_threshold: float = 1e-8,
cost: CostFunctionGenerator = HilbertSchmidtResidualsGenerator(),
max_layer: int | None = None,
store_partial_solutions: bool = False,
partials_per_depth: int = 25,
min_prefix_size: int = 3,
instantiate_options: dict[str, Any] = {},
) -> None:
"""
Construct a search-based synthesis pass.
Args:
heuristic_function (HeuristicFunction): The heuristic to guide
search.
layer_generator (LayerGenerator | None): The successor function
to guide node expansion. If left as none, then a default
will be selected before synthesis based on the target
model's gate set. (Default: None)
success_threshold (float): The distance threshold that
determines successful termintation. Measured in cost
described by the cost function. (Default: 1e-8)
cost (CostFunction | None): The cost function that determines
distance during synthesis. The goal of this synthesis pass
is to implement circuits for the given unitaries that have
a cost less than the `success_threshold`.
(Default: HSDistance())
max_layer (int): The maximum number of layers to append without
success before termination. If left as None it will default
to unlimited. (Default: None)
store_partial_solutions (bool): Whether to store partial solutions
at different depths inside of the data dict. (Default: False)
partials_per_depth (int): The maximum number of partials
to store per search depth. No effect if
`store_partial_solutions` is False. (Default: 25)
min_prefix_size (int): The minimum number of layers needed
to prefix the circuit.
instantiate_options (dict[str: Any]): Options passed directly
to circuit.instantiate when instantiating circuit
templates. (Default: {})
Raises:
ValueError: If `max_depth` or `min_prefix_size` is nonpositive.
"""
if not isinstance(heuristic_function, HeuristicFunction):
raise TypeError(
'Expected HeursiticFunction, got %s.'
% type(heuristic_function),
)
if layer_generator is not None:
if not isinstance(layer_generator, LayerGenerator):
raise TypeError(
f'Expected LayerGenerator, got {type(layer_generator)}.',
)
if not is_real_number(success_threshold):
raise TypeError(
'Expected real number for success_threshold'
', got %s' % type(success_threshold),
)
if not isinstance(cost, CostFunctionGenerator):
raise TypeError(
'Expected cost to be a CostFunctionGenerator, got %s'
% type(cost),
)
if max_layer is not None and not is_integer(max_layer):
raise TypeError(
'Expected max_layer to be an integer, got %s' % type(max_layer),
)
if max_layer is not None and max_layer <= 0:
raise ValueError(
'Expected max_layer to be positive, got %d.' % int(max_layer),
)
if min_prefix_size is not None and not is_integer(min_prefix_size):
raise TypeError(
'Expected min_prefix_size to be an integer, got %s'
% type(min_prefix_size),
)
if min_prefix_size is not None and min_prefix_size <= 0:
raise ValueError(
'Expected min_prefix_size to be positive, got %d.'
% int(min_prefix_size),
)
if not isinstance(instantiate_options, dict):
raise TypeError(
'Expected dictionary for instantiate_options, got %s.'
% type(instantiate_options),
)
self.heuristic_function = heuristic_function
self.layer_gen = layer_generator
self.success_threshold = success_threshold
self.cost = cost
self.max_layer = max_layer
self.min_prefix_size = min_prefix_size
self.instantiate_options: dict[str, Any] = {
'cost_fn_gen': self.cost,
}
self.instantiate_options.update(instantiate_options)
self.store_partial_solutions = store_partial_solutions
self.partials_per_depth = partials_per_depth
[docs]
async def synthesize(
self,
utry: UnitaryMatrix | StateVector | StateSystem,
data: PassData,
) -> Circuit:
"""Synthesize `utry`, see :class:`SynthesisPass` for more."""
# Initialize run-dependent options
instantiate_options = self.instantiate_options.copy()
# Seed the PRNG
if 'seed' not in instantiate_options:
instantiate_options['seed'] = data.seed
# Get layer generator for search
layer_gen = self._get_layer_gen(data)
# Begin the search with an initial layer
frontier = Frontier(utry, self.heuristic_function)
initial_layer = layer_gen.gen_initial_layer(utry, data)
initial_layer.instantiate(utry, **instantiate_options)
frontier.add(initial_layer, 0)
# Track best circuit, initially the initial layer
best_dist = self.cost.calc_cost(initial_layer, utry)
best_circ = initial_layer
best_layer = 0
best_dists = [best_dist]
best_layers = [0]
last_prefix_layer = 0
# Track partial solutions
psols: dict[int, list[tuple[Circuit, float]]] = {}
_logger.debug(f'Search started, initial layer has cost: {best_dist}.')
# Evalute initial layer
if best_dist < self.success_threshold:
_logger.debug('Successful synthesis.')
return initial_layer
# Main loop
while not frontier.empty():
top_circuit, layer = frontier.pop()
# Generate successors
successors = layer_gen.gen_successors(top_circuit, data)
if len(successors) == 0:
continue
# Instantiate successors
circuits = await get_runtime().map(
Circuit.instantiate,
successors,
target=utry,
**instantiate_options,
)
# Evaluate successors
for circuit in circuits:
dist = self.cost.calc_cost(circuit, utry)
if dist < self.success_threshold:
_logger.debug('Successful synthesis.')
if self.store_partial_solutions:
data['psols'] = psols
return circuit
if self.check_new_best(layer + 1, dist, best_layer, best_dist):
plural = '' if layer == 0 else 's'
_logger.debug(
f'New best circuit found with {layer + 1} layer{plural}'
f' and cost: {dist:.12e}.',
)
best_dist = dist
best_circ = circuit
best_layer = layer + 1
if self.check_leap_condition(
layer + 1,
best_dist,
best_layers,
best_dists,
last_prefix_layer,
):
_logger.debug(f'Prefix formed at {layer + 1} layers.')
last_prefix_layer = layer + 1
frontier.clear()
if self.max_layer is None or layer + 1 < self.max_layer:
frontier.add(circuit, layer + 1)
if self.store_partial_solutions:
if layer not in psols:
psols[layer] = []
psols[layer].append((circuit.copy(), dist))
if len(psols[layer]) > self.partials_per_depth:
psols[layer].sort(key=lambda x: x[1])
del psols[layer][-1]
if self.max_layer is None or layer + 1 < self.max_layer:
frontier.add(circuit, layer + 1)
_logger.warning('Frontier emptied.')
_logger.warning(
'Returning best known circuit with %d layer%s and cost: %e.'
% (best_layer, '' if best_layer == 1 else 's', best_dist),
)
if self.store_partial_solutions:
data['psols'] = psols
return best_circ
[docs]
def check_new_best(
self,
layer: int,
dist: float,
best_layer: int,
best_dist: float,
) -> bool:
"""
Check if the new layer depth and dist are a new best node.
Args:
layer (int): The current layer in search.
dist (float): The current distance in search.
best_layer (int): The current best layer in the search tree.
best_dist (float): The current best distance in search.
"""
better_layer = (
dist < best_dist
and (
best_dist >= self.success_threshold
or layer <= best_layer
)
)
better_dist_and_layer = (
dist < self.success_threshold and layer < best_layer
)
return better_layer or better_dist_and_layer
[docs]
def check_leap_condition(
self,
new_layer: int,
best_dist: float,
best_layers: list[int],
best_dists: list[float],
last_prefix_layer: int,
) -> bool:
"""
Return true if the leap condition is satisfied.
Args:
new_layer (int): The current layer in search.
best_dist (float): The current best distance in search.
best_layers (list[int]): The list of layers associated
with recorded best distances.
best_dists (list[float]): The list of recorded best
distances.
last_prefix_layer (int): The last layer a prefix was formed.
"""
with np.errstate(invalid='ignore', divide='ignore'):
# Calculate predicted best value
m, y_int, _, _, _ = linregress(best_layers, best_dists)
predicted_best = m * (new_layer) + y_int
# Track new values
best_layers.append(new_layer)
best_dists.append(best_dist)
if np.isnan(predicted_best):
return False
# Compute difference between actual value
delta = predicted_best - best_dist
_logger.debug(
'Predicted best value %f for new best best with delta %f.'
% (predicted_best, delta),
)
layers_added = new_layer - last_prefix_layer
return delta < 0 and layers_added >= self.min_prefix_size
def _get_layer_gen(self, data: PassData) -> LayerGenerator:
"""
Set the layer generator.
If a layer generator has been passed into the constructor, then that
layer generator will be used. Otherwise, a default layer generator will
be selected by the gateset.
If seeds are passed into the data dict, then a SeedLayerGenerator will
wrap the previously selected layer generator.
"""
# TODO: Deduplicate this code with qsearch synthesis
layer_gen = self.layer_gen or data.gate_set.build_mq_layer_generator()
# Priority given to seeded synthesis
if 'seed_circuits' in data:
return SeedLayerGenerator(data['seed_circuits'], layer_gen)
return layer_gen