Class implementing the adaptive gate decomposition algorithm of arXiv:2203.04426. More...

#include "N_Qubit_Decomposition_Tree_Search.h"
#include "N_Qubit_Decomposition_Cost_Function.h"
#include "n_aryGrayCodeCounter.h"
#include <algorithm>
#include <atomic>
#include <chrono>
#include <cmath>
#include <iostream>
#include <numeric>
#include <queue>
#include <random>
#include <stdlib.h>
#include <thread>
#include <time.h>
#include <unordered_map>

Include dependency graph for N_Qubit_Decomposition_Tree_Search.cpp:

Go to the source code of this file.

Classes
struct	ForbiddenSubseqSet

struct	LevelResult
	Structure containing the result of a BFS level enumeration. More...

Typedefs
using	Discovery = std::vector< std::pair< std::vector< int >, GrayCodeCNOT > >

Functions
std::vector< uint32_t >	build_pred_mask (const GrayCodeCNOT &ops, const std::vector< matrix_base< int >> &topology)

static int	canonical_prefix_ok (const GrayCodeCNOT &path, const std::vector< matrix_base< int >> &topology)

bool	contains_topological_subsequence (const GrayCodeCNOT &smallpath, const GrayCodeCNOT &bigpath, const std::vector< matrix_base< int >> &topology)

static LevelResult	enumerate_unordered_cnot_BFS_level_init (int n)
	Initialize the breadth-first search (BFS) enumeration at depth 0 (identity state only). More...

static LevelResult	enumerate_unordered_cnot_BFS_level_step (LevelInfo &L, const std::vector< matrix_base< int >> &topology, bool use_gl=true)
	Perform one expansion level of breadth-first search (BFS) enumeration over CNOT gate structures. More...

template<class Callback >
void	generate_insertions (const GrayCodeCNOT &curpath, const std::vector< matrix_base< int >> &topology, const std::vector< int > &topo_filt, int num_cnot, Callback &&callback)

template<class Callback >
void	generate_insertions_recursive (const GrayCodeCNOT &curpath, const std::vector< matrix_base< int >> &topology, const std::vector< int > &topo_filt, int num_cnot, std::vector< int > &places, std::vector< int > &pairs, int depth, int min_place, Callback &&callback, bool &early_stop)

static int	is_unique_structure (const GrayCodeCNOT &path, const std::vector< matrix_base< int >> &topology)

Detailed Description

Class implementing the adaptive gate decomposition algorithm of arXiv:2203.04426.

Definition in file N_Qubit_Decomposition_Tree_Search.cpp.

Typedef Documentation

◆ Discovery

using Discovery = std::vector<std::pair<std::vector<int>, GrayCodeCNOT> >

Definition at line 54 of file N_Qubit_Decomposition_Tree_Search.cpp.

Function Documentation

◆ build_pred_mask()

std::vector<uint32_t> build_pred_mask	(	const GrayCodeCNOT &	ops,
		const std::vector< matrix_base< int >> &	topology
	)

Definition at line 843 of file N_Qubit_Decomposition_Tree_Search.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ canonical_prefix_ok()

static int canonical_prefix_ok	(	const GrayCodeCNOT &	path,
		const std::vector< matrix_base< int >> &	topology
	)

static

Definition at line 96 of file N_Qubit_Decomposition_Tree_Search.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ contains_topological_subsequence()

bool contains_topological_subsequence	(	const GrayCodeCNOT &	smallpath,
		const GrayCodeCNOT &	bigpath,
		const std::vector< matrix_base< int >> &	topology
	)

Definition at line 870 of file N_Qubit_Decomposition_Tree_Search.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ enumerate_unordered_cnot_BFS_level_init()

static LevelResult enumerate_unordered_cnot_BFS_level_init ( int n )

inlinestatic

Initialize the breadth-first search (BFS) enumeration at depth 0 (identity state only).

This function sets up the initial state for BFS enumeration of CNOT gate structures. At depth 0, the state represents the identity operation (no CNOT gates applied), where each qubit is in its own computational basis state. The function creates the initial state vector I, where each element I[i] = 2^i represents the i-th qubit's basis state, marks it as visited, and initializes the sequence pairs mapping with an empty Gray code.

Parameters

n	The number of qubits in the system

Returns

Returns a LevelResult structure containing:

visited: Set containing the initial identity state I
seq_pairs_of: Map from the identity state to an empty Gray code sequence
out_res: Vector containing a single discovery pair (I, empty Gray code)

Note: This function is the starting point for BFS enumeration. The identity state I is represented as a vector where I[i] = 2^i, which corresponds to the i-th qubit being in state |1â© while all others are in state |0â©.

Definition at line 73 of file N_Qubit_Decomposition_Tree_Search.cpp.

Here is the caller graph for this function:

◆ enumerate_unordered_cnot_BFS_level_step()

static LevelResult enumerate_unordered_cnot_BFS_level_step	(	LevelInfo &	L,
		const std::vector< matrix_base< int >> &	topology,
		bool	use_gl = `true`
	)

inlinestatic

Perform one expansion level of breadth-first search (BFS) enumeration over CNOT gate structures.

This function processes all states in the current BFS level queue, applies all possible CNOT operations from the topology, and discovers new states at the next depth level. It maintains the BFS property that states are discovered at their minimal depth, ensuring optimal exploration of the gate structure space.

The function operates in two modes:

When use_gl=true (Gray-Lin mode): Applies CNOT operations directly to state vectors using XOR operations, tracking actual quantum states reached by the circuit.
When use_gl=false: Builds Gray code sequences representing gate orderings, with additional constraints to avoid repeated CNOTs (max 3 consecutive) and ensure canonical ordering.

Parameters

L	LevelInfo reference containing the current BFS state: visited: Set of states already discovered (modified to include new discoveries) seq_pairs_of: Map from states to their Gray code sequences (used for lookups) q: Queue of states to process at the current level (emptied during processing)
topology	Vector of CNOT pairs (target, control) representing allowed qubit connections. Each element is a matrix_base<int> with two elements [target, control].
use_gl	If true, uses Gray-Lin mode (applies CNOTs directly to states). If false, builds sequence-based representations with canonical ordering constraints.

Returns

Returns a LevelResult structure containing:

visited: Updated set of visited states (includes all newly discovered states)
seq_pairs_of: Map from newly discovered states to their extended Gray code sequences
out_res: Vector of discovery pairs (state, Gray code) for all newly found states

Note: The function modifies the input LevelInfo structure L by updating visited states and clearing the queue. New states are discovered by applying CNOT operations: B[target] ^= B[control] in Gray-Lin mode, or by extending Gray code sequences in sequence mode.

Definition at line 194 of file N_Qubit_Decomposition_Tree_Search.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ generate_insertions()

template<class Callback >

void generate_insertions	(	const GrayCodeCNOT &	curpath,
		const std::vector< matrix_base< int >> &	topology,
		const std::vector< int > &	topo_filt,
		int	num_cnot,
		Callback &&	callback
	)

Definition at line 327 of file N_Qubit_Decomposition_Tree_Search.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ generate_insertions_recursive()

template<class Callback >

void generate_insertions_recursive	(	const GrayCodeCNOT &	curpath,
		const std::vector< matrix_base< int >> &	topology,
		const std::vector< int > &	topo_filt,
		int	num_cnot,
		std::vector< int > &	places,
		std::vector< int > &	pairs,
		int	depth,
		int	min_place,
		Callback &&	callback,
		bool &	early_stop
	)