qat.synthopline.linear_operator_synthesis

qat.synthopline.linear_operator_synthesis(table: ndarray, method: str = None, **kwargs)

Produces a CNOT circuit equivalent to a reversible linear boolean operator.

This method is wrapper for serveral C++ algorithms. The underlying method can be chosen via the method keyword.

Algorithms:

gauss: standard Gaussian elimination. This is the reference naive algorithm to synthesize linear boolean operators.

pmh: A block-wise Gaussian elimination introduced in [PMH03]

pmh_opt: an optimization of [PMH03] where the block parameter is automatically picked (set to \(log(n)\)).

greedy_gauss: Goubault de Brugière et al greedy Gaussian elimination algorithm. More details to appear in [dBrugiereBV+20a].

syndrome: Goubault de Brugière et al syndrome decoding based heuristic. More details in [dBrugiereBV+20b].

pathfinding: Goubault de Brugière et al greedy pathfinding algorithm(s). This method is a wrapper for a pathfinding meta-heuristics that greedily picks the next CNOT to apply by minimizing some local cost function. The cost function is controlled via various parameters (see below). More details to appear in [dBrugiereBV+20a]. This method can quickly become unstable for large number of qubits (>30) and should be considered as an experimental feature.

divide_and_conquer: Goubault de Brugière et al recursive depth minimization algorithm. As opposed to the other methods, this one tries to minimize the depth of the circuit. Publication to appear.

steiner_gauss: Kissinger et al architecture aware Gaussian elimination. This algorithm also takes an architecture connectivity graph and outputs a compliant circuit. It more or less performs a Gaussian elimination while smartly routing information accross the chip. Notice that this method requires you to provide a Hamiltonian path of the connectivity graph. More details in [KdG19].

The default method is greedy_gauss. Some methods, such as syndrome or steiner_gauss can take additional parameters. These can be passed in kwargs (see below).

Parameters

  • table (np.ndarray) – the linear operator to synthesize as a square numpy array

  • method (str) – the method to use

  • **kwargs – additional parameters

Returns

a circuit

Return type

Circuit

Additional parameters:
syndrome:

  • p (list of int): the final permutation of the qubits (the input list is modified in place). Any following circuit must be permuted according to p

  • width (int): the width of the search when solving a syndrome decoding instance. A larger width implies better results and longer computation time. Defaults to 2.

  • depth (int): the depth of the search when solving a syndrome decoding instance. A larger depth implies better results and longer computation time. Defaults to 3.

pmh:

  • m (int): block size of the PMH algorithm (see reference)

steiner_gauss:

  • graph (nx.Graph): a connectivity graph

  • ham_path (list or int): a Hamiltonian path of the connectivity graph

pathfinding:

  • p (list of int): the final permutation of the qubits (the input list is modified in place). Any following circuit must be permuted according to p

  • width (optional, int): the width of the search when picking the next CNOT. A larger width implies better results and longer computation time. Defaults to 10.

  • depth (optional, int): the depth of the search when picking the next CNOT. A larger depth implies better results and longer computation time. Defaults to 1.

  • niter (optional, int): the number of retries to perform. The algorithm will be run niter times and the best solution will be returned. Defaults to 1.

  • metric (optional, str): the metric to use (“ones” for the number of ones in the table or “log” for the log of the number of ones). Defaults to “ones”.

  • escape (optional, bool): enable a heuristic to get out of local minima. Only available with method “ones”. Mutually exclusive with option inv. Ignored for metric “log”. Defaults to False.

  • inv (optional, bool): also computes the metric for the inverse method. Mutually exclusive with option escape. Ignored for metric “log”. Defaults to False.

Final permutation:

Warning

Both methods syndrome and pathfinding return circuits that implement the target operator up to some permutation. This means that the qubit ordering must be modified after the circuit. Below is an example on how to obtain this permutation from the synthesis method.

import numpy as np
from qat.synthopline import linear_operator_synthesis
from qat.synthopline.linear_synthesis import random_linear_operator, extract_linear_operator

np.random.seed(881)
operator = random_linear_operator(5)
permutation = list(range(5))
circuit = linear_operator_synthesis(operator, p=permutation, method="syndrome")

table_implemented = extract_linear_operator(circuit)
print("Target table:\n", operator)
print("Implemented table:\n", table_implemented)

new_table = np.zeros((5, 5), dtype=np.byte)
for i in range(5):
    new_table[i] = table_implemented[permutation[i]]
assert np.allclose(new_table, operator)

Target table:
 [[1 0 1 0 0]
 [1 1 0 0 1]
 [0 0 1 0 0]
 [1 0 0 1 0]
 [1 1 0 1 0]]
Implemented table:
 [[1 0 1 0 0]
 [1 1 0 1 0]
 [0 0 1 0 0]
 [1 0 0 1 0]
 [1 1 0 0 1]]

In other words, permutation carries the final qubit mapping.

Note

This method is available as an application in Qaptiva Access.