Namespace busclique#

namespace busclique

Typedefs

typedef size_t size_y

typedef size_t size_x

typedef size_t size_w

typedef size_t size_z

template<typename value_t> using biclique_result_cache = std::unordered_map<pair<size_t, size_t>, value_t, craphash>

using chimera_spec = topo_spec_cellmask<chimera_spec_base>#

using pegasus_spec = topo_spec_cellmask<pegasus_spec_base>#

using zephyr_spec = topo_spec_cellmask<zephyr_spec_base>#

Enums

enum corner#

Values:

enumerator NW#

enumerator NE#

enumerator SW#

enumerator SE#

enumerator NWskip#

enumerator NEskip#

enumerator SWskip#

enumerator SEskip#

enumerator skipmask#

enumerator shift#

enumerator mask#

enumerator none#

Functions

inline size_t binom(size_t)#

inline const size_t &coordinate_index(const size_t &c)

inline const size_t &vert(const size_t &c)

inline const size_t &horz(const size_t &c)

constexpr size_y operator""_y(unsigned long long int v): user-defined literal for size_y

constexpr size_x operator""_x(unsigned long long int v): user-defined literal for size_x

constexpr size_w operator""_w(unsigned long long int v): user-defined literal for size_w

constexpr size_z operator""_z(unsigned long long int v): user-defined literal for size_z

constexpr uint64_t operator""_u64(unsigned long long int v): user-defined literal for uint64_t

constexpr uint32_t operator""_u32(unsigned long long int v): user-defined literal for uint32_t

constexpr uint16_t operator""_u16(unsigned long long int v): user-defined literal for uint16_t

constexpr uint8_t operator""_u8(unsigned long long int v): user-defined literal for uint8_t

template<typename topo_spec> void best_bicliques(const topo_spec &topo, const vector<size_t> &nodes, const vector<pair<size_t, size_t>> &edges, vector<pair<pair<size_t, size_t>, vector<vector<size_t>>>> &embs)

template<typename topo_spec> void best_bicliques(topo_cache<topo_spec> &topology, vector<pair<pair<size_t, size_t>, vector<vector<size_t>>>> &embs)

template<typename T> size_t get_maxlen(vector<T> &emb, size_t size)

template<typename clique_cache_t> size_t get_sol(const clique_cache_t &rects, vector<vector<size_t>> &emb, size_t size)

template<typename cells_t> bool find_clique_short(const cells_t &cells, const size_t size, vector<vector<size_t>> &emb, size_t &max_length)

template<typename topo_spec> bool find_clique_nice(const cell_cache<topo_spec>&, size_t size, vector<vector<size_t>> &emb, size_t &min_width, size_t &max_width, size_t &max_length)

template<> bool find_clique_nice(const cell_cache<chimera_spec> &cells, size_t size, vector<vector<size_t>> &emb, size_t&, size_t&, size_t &max_length)

template<> bool find_clique_nice(const cell_cache<zephyr_spec> &cells, size_t size, vector<vector<size_t>> &emb, size_t&, size_t&, size_t &max_length)

template<> bool find_clique_nice(const cell_cache<pegasus_spec> &cells, size_t size, vector<vector<size_t>> &emb, size_t&, size_t&, size_t &max_length)

template<typename topo_spec> bool find_clique(const topo_spec &topo, const vector<size_t> &nodes, const vector<pair<size_t, size_t>> &edges, size_t size, vector<vector<size_t>> &emb)

template<typename topo_spec> bool find_clique(topo_cache<topo_spec> &topology, size_t size, vector<vector<size_t>> &emb)

template<typename topo_spec> void short_clique(const topo_spec&, const vector<size_t> &nodes, const vector<pair<size_t, size_t>> &edges, vector<vector<size_t>> &emb)

template<typename topo_spec> void best_cliques(topo_cache<topo_spec> &topology, vector<vector<vector<size_t>>> &embs, vector<vector<size_t>> &emb_1)

bool find_generic_1(const vector<size_t> &nodes, vector<vector<size_t>> &emb)

bool find_generic_2(const vector<pair<size_t, size_t>> &edges, vector<vector<size_t>> &emb)

bool find_generic_3(const vector<pair<size_t, size_t>> &edges, vector<vector<size_t>> &emb)

bool find_generic_4(const vector<pair<size_t, size_t>> &edges, vector<vector<size_t>> &emb)

template<typename T> inline size_t _serial_helper(serialize_size_tag, uint8_t*, const fat_pointer<T> &value)#

_serial_helper both computes the size of a field of an object being serialized, and also writes it into an output buffer, advancing its buffer.

The construction provides a single source of truth for the serialization of an object field or data pointer.

template<typename T> inline size_t _serial_helper(serialize_size_tag, uint8_t*, const T &value)#

template<typename T> const T *_serial_addr(const fat_pointer<T> &value)#

template<typename T> const T *_serial_addr(const T &value)#

template<typename serialize_tag, typename T> inline size_t _serial_helper(serialize_tag, uint8_t *output, const T &value)#

template<typename serialize_tag, typename...> inline size_t _serialize(serialize_tag, uint8_t*)#

_serialize computes the size of a sequence of fields associated with an object being serialized, and also writes those fields into an output buffer advancing the buffer by the corresponding amount.

This provides a single source of truth for the serialization of a class.

template<typename serialize_tag, typename T, typename ...Args> inline size_t _serialize(serialize_tag, uint8_t *output, const T &value, const Args&... args)#

Variables

const vector<vector<size_t>> empty_emb

const uint8_t popcount[256] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8}#

const uint8_t first_bit[256] = {0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0}#

const uint8_t mask_bit[8] = {1, 2, 4, 8, 16, 32, 64, 128}#

const uint16_t mask_subsets[8] = {1, 2, 4, 8, 16, 32, 64, 128}#

const std::set<size_t> _emptyset#

class yieldcache: #include <biclique_cache.hpp>

template<typename topo_spec> class biclique_cache: #include <biclique_cache.hpp>

template<typename topo_spec> class biclique_yield_cache

#include <biclique_cache.hpp>

class iterator: #include <biclique_cache.hpp>

template<typename topo_spec> class bundle_cache: #include <bundle_cache.hpp>

template<typename topo_spec> class cell_cache: #include <cell_cache.hpp>

class maxcache: #include <clique_cache.hpp>

class zerocache: #include <clique_cache.hpp>

template<typename topo_spec> class clique_iterator: #include <clique_cache.hpp>

template<typename topo_spec> class clique_cache: #include <clique_cache.hpp>

template<typename topo_spec> class clique_yield_cache: #include <clique_cache.hpp>

class coordinate_converter

#include <coordinate_types.hpp>

An arena to perform arithmetic that does not respect the unit system defined in coordinate_base<T>.

This class is not a friend of coordinate_base<T> so so that we can do all of our bounds-checking here, with full type-safety. The generic pattern is that bounds-checking is done inside a public method, respecting the unit systems, and then we explicitly convert coordinates and dimensions to size_t, to be combined in a private method with the _impl suffix.

Public Static Functions

static inline size_t cell_index(size_y y, size_x x, bool u, size_y dim_y, size_x dim_x): This computes compute the index of A[u][y][x] in an array A of dimension [2][dim_y][dim_x]

static inline size_t cell_index(bool u, size_w w, size_z z, size_y dim_y, size_x dim_x): This computes compute the index of A[u][y][x] in an array A of dimension [2][dim_y][dim_x]; where y and x are determined from w and z, depending on the orientation u.

template<typename shore_t> static inline size_t chimera_linear(size_y y, size_x x, bool u, shore_t k, size_y dim_y, size_x dim_x, shore_t shore): given a chimera coordinate (y, x, u, k) with chimera dimensions (m, n, t) = (dim_y, dim_x, shore), compute the linear index.

template<typename shore_t> static inline void linear_chimera(size_t q0, size_y &y, size_x &x, bool &u, shore_t &k, size_y dim_y, size_x dim_x, shore_t shore): given a linear index q0 in a chimera graph with dimensions (m, n, t) = (dim_y, dim_x, shore), compute the coordinate (y, x, u, k)

template<typename shore_t> static inline size_t linemajor_linear(bool u, size_w w, shore_t k, size_z z, size_w dim_w, shore_t shore, size_z dim_z)

Pegasus and Zephyr coordinates exist in relative coordinate systems.

We note that our implementation of Zephyr coordinates differs from the one used other places — we’ve merged the k and j indices into one. The name ‘linemajor’ indicates that the (u, w, k) parameters specify a line of colinear qubits. This function is used to pack a Zephyr or Pegasus coordinate address (u, w, k, z) into a linear index. The interpretation of dim_w, shore, and dim_z is determined by the relevant topology, and we expect callers to know what they’re doing. Specifically, for pegasus_graph(m), dim_w = 6*m, shore = 2, dim_z = m-1 and for zephyr_graph(m), dim_w = 2*m+1, shore=2*t, dim_z = m

template<typename shore_t> static inline void linear_linemajor(size_t q0, bool &u, size_w &w, shore_t &k, size_z &z, size_w dim_w, shore_t shore, size_z dim_z)

Pegasus and Zephyr coordinates exist in relative coordinate systems.

We note that our implementation of Zephyr coordinates differs from the one used other places — we’ve merged the k and j indices into one. The name ‘linemajor’ indicates that the (u, w, k) parameters specify a line of colinear qubits. This function is used to unpack a Zephyr or Pegasus linear index to a coordinate address (u, w, k, z). The interpretation of dim_w, shore, and dim_z is determined by the relevant topology, and we expect callers to know what they’re doing. Specifically, for pegasus_graph(m), dim_w = 6*m, shore = 2, dim_z = m-1 and for zephyr_graph(m), dim_w = 2*m+1, shore=2*t, dim_z = m

template<typename T, typename ...Args> static inline size_t product(T t, Args... args): explicitly convert all arguments into a size_t and return the product of them all.

template<typename T, typename ...Args> static inline size_t sum(T t, Args... args): explicitly convert all arguments into a size_t and return the product of them all.

template<typename S, typename T> static inline size_t min(S s, T t): explicitly convert both arguments into a size_t and return the minimum

template<typename S, typename T> static inline size_t max(S s, T t): explicitly convert both arguments into a size_t and return the maximum

static inline size_t grid_index(size_y y, size_x x, size_y dim_y, size_x dim_x): Implements addressing into a 2-dimensional array T[dim_y][dim_x].

static inline size_t bundle_cache_index(bool u, size_w w, size_z z0, size_z z1, size_t stride_u, size_t stride_w)

This addressing scheme is wikkid complicated.

The majority of the logic is contained in bundle_cache.hpp. We store line masks (that is, sets of k-indices) corresponding to the line segment (u, w, z0, z1). That is, if the bit i is set in line_mask[bundle_cache_index(u, w, z0, z1)], then line of qubits [(u, w, i, z) for z in range(z0, z1+1)] and the necessary external couplers are present in the linemajor representation of the topology. We assume that the caller knows what it’s doing with stride_u and stride_w. We do belts-and-suspenders assertion testing in bundle_cache::compute_line_masks for added confidence that the caller actually knows what it’s doing.

class craphash: #include <find_biclique.hpp>

template<typename topo_spec> class topo_cache: #include <topo_cache.hpp>

class serialize_size_tag: #include <util.hpp>

class serialize_write_tag: #include <util.hpp>

template<typename T> class fat_pointer: #include <util.hpp>

class ignore_badmask: #include <util.hpp>

class populate_badmask: #include <util.hpp>

class topo_spec_base

#include <util.hpp>

Subclassed by busclique::chimera_spec_base, busclique::pegasus_spec_base, busclique::zephyr_spec_base

Public Functions

inline size_t cell_index(size_y y, size_x x, bool u) const

cell_index is used for indexing into the nodemask and edgemask fields of cell_cache and topo_cache objects.

These are used to store bitmasks indicating the presence of nodes in the corresponding cell, or external edges between the corresponding cell and its greater parallel neighbor (that is, between the cells [y,x,0] and [y+1,x,0] or between the cells [y,x,1] and [y,x+1,1]).

inline size_t cell_index(bool u, size_w w, size_z z) const

cell_index is used for indexing into the nodemask and edgemask fields of cell_cache and topo_cache objects.

class pegasus_spec_base : public busclique::topo_spec_base: #include <util.hpp>

class chimera_spec_base : public busclique::topo_spec_base: #include <util.hpp>

class zephyr_spec_base : public busclique::topo_spec_base: #include <util.hpp>

template<typename topo_spec> class topo_spec_cellmask : public topo_spec: #include <util.hpp>