Gate maps

Representing gates with matrices is a great way to ensure plugin compatibility; unlike using for example names for gates, the matrix unambiguously represents the mathematical operation that is to be performed. However, there are cases where you may want to distinguish whether a gate is for instance one of the Pauli gates or something else. You could do this with dqcs_mat_approx_eq(), but if you have a lot of gates your code will explode, be error-prone (especially if you want to do the reverse operation as well), and may not be very efficient. More generally, a plugin may want to use its own higher-level internal gate representation, and convert between that and DQCsim's matrix-based representation.

Gate maps intend to solve this problem. You can define any data structure to represent your gates as long as it can map to/from the following:

any kind of key (a void*) defining the type of gate.
a number of qubit arguments.
optionally, an ArbData representing parameters if your definition of a gate type is parameterized.

You can then use a gate map to convert between that representation and DQCsim's representation, typically in both directions. Going from DQCsim's matrix representation to your plugin's representation is called detection, while the opposite direction is called construction. Once you have a gate map, you can use the following functions to do this.

dqcs_gm_detect()

Uses a gate map object to convert an incoming DQCsim gate to the plugin's representation.

dqcs_bool_return_t dqcs_gm_detect(
    dqcs_handle_t gm,
    dqcs_handle_t gate,
    const void **key_data,
    dqcs_handle_t *qubits,
    dqcs_handle_t *param_data
)

gm must be a handle to a gate map object (dqcs_mm_new()). gate must be a handle to a gate. The handle is borrowed; it is not mutated or deleted. key_data serves as an optional return value; if non-NULL and a match is found, the key_data specified when the respective detector was added is returned here as a const void *. If no match is found, *key_data is not assigned. qubits serves as an optional return value; if non-NULL and a match is found, it is set to a handle to a new QubitSet object representing the gate's qubits. Ownership of this handle is passed to the user, so it is up to the user to eventually delete it. If no match is found, *qubits is set to 0. param_data serves as an optional return value; if non-NULL and a match is found, it is set to a handle to a new ArbData object representing the gate's parameters. Ownership of this handle is passed to the user, so it is up to the user to eventually delete it. If no match is found, *param_data is set to 0.

This function returns DQCS_TRUE if a match was found, DQCS_FALSE if no match was found, or DQCS_BOOL_FAILURE if an error occurs.

dqcs_gm_construct_one()

Uses a gate map object to construct a one-qubit DQCsim gate from the plugin's representation.

dqcs_handle_t dqcs_gm_construct_one(
    dqcs_handle_t gm,
    const void *key_data,
    dqcs_qubit_t qa,
    dqcs_handle_t param_data
)

This function is simply a shorthand for dqcs_gm_construct() with one qubit in the qubits set, to make constructing one-qubit gates more ergonomic. Refer to its documentation for more information.

dqcs_gm_construct_two()

Uses a gate map object to construct a two-qubit DQCsim gate from the plugin's representation.

dqcs_handle_t dqcs_gm_construct_two(
    dqcs_handle_t gm,
    const void *key_data,
    dqcs_qubit_t qa,
    dqcs_qubit_t qb,
    dqcs_handle_t param_data
)

This function is simply a shorthand for dqcs_gm_construct() with two qubits in the qubits set, to make constructing two-qubit gates more ergonomic. Refer to its documentation for more information.

dqcs_gm_construct_three()

Uses a gate map object to construct a three-qubit DQCsim gate from the plugin's representation.

dqcs_handle_t dqcs_gm_construct_three(
    dqcs_handle_t gm,
    const void *key_data,
    dqcs_qubit_t qa,
    dqcs_qubit_t qb,
    dqcs_qubit_t qc,
    dqcs_handle_t param_data
)

This function is simply a shorthand for dqcs_gm_construct() with three qubits in the qubits set, to make constructing three-qubit gates more ergonomic. Refer to its documentation for more information.

dqcs_gm_construct()

Uses a gate map object to construct a multi-qubit DQCsim gate from the plugin's representation.

dqcs_handle_t dqcs_gm_construct(
    dqcs_handle_t gm,
    const void *key_data,
    dqcs_handle_t qubits,
    dqcs_handle_t param_data
)

gm must be a handle to a gate map object (dqcs_mm_new()). gate must be a handle to a gate. The handle is borrowed; it is not mutated or deleted. key_data specifies the gate mapping key for the constructor to use. Note that the pointer must match exactly to what was specified when the mapping(s) was/were added. qubits specifies the qubits arguments for the constructed gate. It is up to the constructor function to determine how to interpret these. The parameter is optional; passing 0 is equivalent to passing an empty qubit set. The handle is deleted if the function succeeds. param_data specifies the ArbData object used to parameterize the gate. It is optional; if 0, an empty ArbData is automatically constructed by DQCsim. The handle is deleted if the function succeeds.

This function returns the handle to the gate, or 0 to indicate failure. The qubit set and parameterization data (if specified) are consumed/deleted by this function if and only if it succeeds.

Converters

Conceptually, a gate map consists of a number of converter objects, each typically consisting of a detector function and a constructor function. In the most generic case, the detector takes a DQCsim gate as its input, and converts it to a qubit set and an ArbData if it recognizes the gate, while the constructor performs the inverse operation. Detection is usually fuzzy to account for floating-point inaccuracies, while construction is as exact as possible.

These converter objects are stored in the gate map as the values of an ordered map, for which the key is the user-defined void* key defining the type of gate. Thus, each converter represents a single gate type. When a gate is to be detected, DQCsim will call each converter's detector function in insertion order until one of the detectors returns a match. When a gate is to be constructed, it simply maps the gate type key to the appropriate converter and calls only its constructor.

The most generic converter described above can be added to a map with the following function, but it is also the most complicated to implement.

dqcs_gm_add_custom()

Adds a fully customizable gate mapping to the given gate map.

dqcs_return_t dqcs_gm_add_custom(
    dqcs_handle_t gm,
    void (*key_free)(void *key_data),
    void *key_data,
    dqcs_bool_return_t (*detector)(
        const void *user_data,
        dqcs_handle_t gate,
        dqcs_handle_t *qubits,
        dqcs_handle_t *param_data
    ),
    void (*detector_user_free)(void *user_data),
    void *detector_user_data,
    dqcs_handle_t (*constructor)(
        const void *user_data,
        dqcs_handle_t qubits,
        dqcs_handle_t param_data
    ),
    void (*constructor_user_free)(void *user_data),
    void *constructor_user_data
)

Note that this is the only type of mapping that can handle custom/named gates.

detector is the detector function pointer. It is optional; if null, this mapping only supports construction. detector_user_free is an optional callback function used to free detector_user_data when the gate map is destroyed, when this function fails, or when detector was null. detector_user_data is a user-specified value that is passed to the detector callback function. It is not used by DQCsim. constructor is the constructor function pointer. It is optional; if null, this mapping only supports detection. constructor_user_free is an optional callback function used to free constructor_user_data when the gate map is destroyed, when this function fails, or when constructor was null. constructor_user_data is a user-specified value that is passed to the constructor callback function. It is not used by DQCsim.

If both constructor and detector are null for some reason, the function is no-op (besides possibly calling the *_free() callbacks.

The detector callback receives the complete gate passed to the gate map for it to match as it pleases. If the gate matches, the detector function must return DQCS_TRUE. It may assign qubits to a qbset object representing the qubit arguments (substituted with an empty set if it doesn't), and may assign param_data to an arb handle with the parameterization data (if it doesn't, the data from the gate is used; if this was modified by the callback, the modified data is used). If the gate doesn't match, it must return DQCS_FALSE. If an error occurs, it must call dqcs_error_set() with the error message and return DQCS_BOOL_FAILURE.

The constructor callback performs the reverse operation. It receives an ArbData handle containing the parameterization data and a qubit set, and must construct a gate based on this information. If construction succeeds, the constructor function must return the gate handle. If an error occurs, it must call dqcs_error_set() with the error message and return 0.

It is up to the user how to do the matching and constructing, but the converter functions must always return the same value for the same input. In other words, they must be pure functions. Otherwise, the caching behavior of the GateMap will make the results inconsistent.

There is also a specialized version that detects unitary gate matrices instead of complete gates. This version deals with distinguishing between unitary, measurement, and custom gates for you. It also converts between DQCsim's seperate target/control qubit set and the single gate-type-sensitive qubit set in the plugin representation for you.

dqcs_gm_add_custom_unitary()

Adds a custom unitary gate mapping to the given gate map.

dqcs_return_t dqcs_gm_add_custom_unitary(
    dqcs_handle_t gm,
    void (*key_free)(void *key_data),
    void *key_data,
    dqcs_bool_return_t (*detector)(
        const void *user_data,
        dqcs_handle_t matrix,
        size_t num_controls,
        dqcs_handle_t *param_data
    ),
    void (*detector_user_free)(void *user_data),
    void *detector_user_data,
    dqcs_handle_t (*constructor)(
        const void *user_data,
        dqcs_handle_t *param_data,
        intptr_t *num_controls
    ),
    void (*constructor_user_free)(void *user_data),
    void *constructor_user_data
)

gm must be a handle to a gate map object (dqcs_gm_new()). key_free is an optional callback function used to free key_data when the gate map is destroyed, or when this function fails. key_data is the user-specified value used to identify this mapping. detector is the detector function pointer. It is optional; if null, this mapping only supports construction. detector_user_free is an optional callback function used to free detector_user_data when the gate map is destroyed, when this function fails, or when detector was null. detector_user_data is a user-specified value that is passed to the detector callback function. It is not used by DQCsim. constructor is the constructor function pointer. It is optional; if null, this mapping only supports detection. constructor_user_free is an optional callback function used to free constructor_user_data when the gate map is destroyed, when this function fails, or when constructor was null. constructor_user_data is a user-specified value that is passed to the constructor callback function. It is not used by DQCsim.

If both constructor and detector are null for some reason, the function is no-op (besides possibly calling the *_free() callbacks.

The detector callback receives a matrix and control qubit information for the user to match. The matrix is passed through the matrix handle. num_controls is passed the number of explicit control qubits that exist besides the matrix (that is, if nonzero, the matrix is actually only the non-controlled submatrix of the controlled gate). param_data is given an ArbData handle initialized with the ArbData attached to the gate. If the gate matches, the detector function must return DQCS_TRUE. In this case, it can mutate the param_data to add the detected gate parameters. If it doesn't match, it must return DQCS_FALSE. If an error occurs, it must call dqcs_error_set() with the error message and return DQCS_BOOL_FAILURE.

The constructor callback performs the reverse operation. It receives an ArbData handle containing the parameterization data, and must construct the matrix, return the bound on the number of control qubits, and must return the ArbData associated with the gate by mutating the param_data handle. num_controls will point to a variable initialized to -1 representing a constraint on the number of control qubits. This works as follows: if negative, any number of qubits is allowed; if zero or positive, only that number is allowed. If construction succeeds, the constructor function must return a handle to the constructed matrix. If it fails, it must call dqcs_error_set() with an error message and return 0.

More likely, though, you just want to detect the usual gates, like X, H, swap, and so on. To help you do this, DQCsim includes built-in converters for every dqcs_predefined_gate_t, which you can add to the map with the following, much simpler function.

dqcs_gm_add_predef_unitary()

Adds a unitary gate mapping for the given DQCsim-defined gate to the given gate map.

dqcs_return_t dqcs_gm_add_predef_unitary(
    dqcs_handle_t gm,
    void (*key_free)(void *user_data),
    void *key_data,
    dqcs_predefined_gate_t gate,
    intptr_t num_controls,
    double epsilon,
    bool ignore_gphase
)

gm must be a handle to a gate map object (dqcs_gm_new()). key_free is an optional callback function used to free key_data when the gate map is destroyed, or when this function fails. key_data is the user-specified value used to identify this mapping. gate defines which predefined gate to use. Some of the predefined gates are parameterized. num_controls specifies the number of control qubits associated with this gate type. If negative, the gate can have any number of control qubits. If zero or positive, the number of control qubits must be as specified. epsilon specifies the maximum element-wise root-mean-square error between the incoming matrix and the to be detected matrix that results in a positive match. ignore_phase specifies whether the aforementioned check should ignore global phase or not when there are no explicit control qubits.

For most gate types, the parameterization ArbData object returned by detection and consumed by construction is mapped one-to-one to the user data of the gate in the DQCsim-protocol. Some of the detectors however detect parameterized gate matrices. These detectors prefix a fixed number of binary string arguments to the ArbData upon detection, and pop these when constructing. The specs for this can be found in the docs for dqcs_predefined_gate_t.

You can also easily detect gates with a special, fixed matrix.

dqcs_gm_add_fixed_unitary()

Adds a unitary gate mapping for the given gate matrix to the given gate map.

dqcs_return_t dqcs_gm_add_fixed_unitary(
    dqcs_handle_t gm,
    void (*key_free)(void *key_data),
    void *key_data,
    dqcs_handle_t matrix,
    intptr_t num_controls,
    double epsilon,
    bool ignore_gphase
)

gm must be a handle to a gate map object (dqcs_gm_new()). key_free is an optional callback function used to free key_data when the gate map is destroyed, or when this function fails. key_data is the user-specified value used to identify this mapping. matrix must be passed a handle to the matrix to detect. It is consumed by this function. num_controls specifies the number of control qubits associated with this gate type. If negative, the gate can have any number of control qubits. If zero or positive, the number of control qubits must be as specified. epsilon specifies the maximum element-wise root-mean-square error between the incoming matrix and the to be detected matrix that results in a positive match. ignore_phase specifies whether the aforementioned check should ignore global phase or not when there are no explicit control qubits.

The parameterization ArbData object returned by detection and consumed by construction is mapped one-to-one to the user data of the gate in the DQCsim-protocol.

Finally, you can detect measurement and prep gates with the following built-in detectors.

dqcs_gm_add_measure()

Adds a measurement gate mapping to the given gate map.

dqcs_return_t dqcs_gm_add_measure(
    dqcs_handle_t gm,
    void (*key_free)(void *user_data),
    void *key_data,
    intptr_t num_measures,
    dqcs_handle_t basis,
    double epsilon
)

gm must be a handle to a gate map object (dqcs_gm_new()). key_free is an optional callback function used to free key_data when the gate map is destroyed, or when this function fails. key_data is the user-specified value used to identify this mapping. num_measures specifies the number of measured qubits for this gate type. If negative, the gate can have any number of measured qubits. If zero or positive, the number of measured qubits must be as specified. basis optionally specifies a handle to a 2x2 matrix specifying the measurement basis to be detected. If not specified, the Z basis is used. The matrix is deleted by the call iff the function succeeds. epsilon specifies the maximum RMS deviation between the specified basis (if any) and the incoming basis.

The parameterization ArbData object returned by detection and consumed by construction is mapped one-to-one to the user data of the gate in the DQCsim-protocol.

dqcs_gm_add_prep()

Adds a prep gate mapping to the given gate map.

dqcs_return_t dqcs_gm_add_prep(
    dqcs_handle_t gm,
    void (*key_free)(void *user_data),
    void *key_data,
    intptr_t num_targets,
    dqcs_handle_t basis,
    double epsilon
)

The parameterization ArbData object returned by detection and consumed by construction is mapped one-to-one to the user data of the gate in the DQCsim-protocol.

Caching

The detection logic in a gate map includes a cache to improve performance when the same gate is received a number of times. This is quite typical, as algorithms typically use only a small subset of gates frequently. There are four different caching strategies:

The cache key is an exact copy of the incoming gate, so the cache only hits when the exact gate is received twice. In this case, the cache maps directly to the result of the previous detection, so no detector function needs to be run. This is the safest option.
The cache ignores differing ArbData attachments to the incoming gates. This is valid only if whether a detector function matches or not is not sensitive to this ArbData. However, the cache only maps to the matching detection function, and calls it again for every cache hit. Thus, the ArbData returned by the detector can still depend on the gate's ArbData.
The cache key is a copy of the incoming gate, but without the qubit references. That is, for example an X gate applied to q1 is considered equal to an X gate applied to q2. This is valid only if whether a detector function matches or not is not sensitive to the qubit references. It can, however, be sensitive to the amount of qubits, and as with the ArbData insensitivity described above, the detector is still called for each cache hit and can thus still return a different qubit set.
A combination of the latter two, i.e., the cache is not sensitive to either the gate's ArbData or to the qubit references.

Preprocessing

To be as compatible with other plugins as possible, you may want to preprocess the incoming gates with either dqcs_gate_reduce_control() or dqcs_gate_expand_control(). We already went over these in the previous section, but their description is repeated here for convenience.

When you apply dqcs_gate_reduce_control() to each incoming gate before passing it to dqcs_gm_detect(), you ensure that if the upstream plugin is sending for instance a CNOT using a complete two-qubit gate matrix and two target qubits, it will still be detected as a controlled X gate with one control qubit, instead of some different gate.

You can also choose to do the opposite, converting from for instance DQCsim's controlled X representation to a full CNOT matrix using dqcs_gate_expand_control. However, in this case you'll have to detect controlled matrices with dqcs_gm_add_fixed_unitary() or a fully custom implementation, as DQCsim only provided predefined matrices for the non-controlled (sub)matrices.

Constructing a gate map

Having read all of the above, you should be ready to construct a new gate map. The construction function takes the caching strategy as its parameters, as well as two optional callback functions used to compare and hash your plugin's key type, needed for the internal hashmap mapping from key to converter object.

dqcs_gm_new()

Constructs a new gate map.

dqcs_handle_t dqcs_gm_new(
    bool strip_qubit_refs,
    bool strip_data,
    bool (*key_cmp)(
        const void,
        const void
    ),
    uint64_t (*key_hash)(const void)
)

Returns a handle to a gate map with no mappings attached to it yet. Use dqcs_gm_add_*() to do that. The mappings are queried in the order in which they are added, so be sure to add more specific gates first. Once added, use dqcs_gm_detect() to detect incoming DQCsim gates, and dqcs_gm_construct*() to (re)construct gates for transmission.

Gate maps objects retain a cache to speed up detection of similar DQCsim gates: if a gate is received for the second time, the cache will hit, avoiding recomputation of the detector functions. What constitutes "similar gates" is defined by the two booleans passed to this function. If strip_qubit_refs is set, all qubit references associated with the gate will be invalidated (i.e., set to 0), such that for instance an X gate applied to qubit 1 will be considered equal to an X gate applied to qubit 2. If strip_data is set, the ArbData associated with the incoming gate is removed.

Gates are identified through user-defined void* keys. To do the above, however, DQCsim needs to know the following things:

how to delete an owned copy of a key if your semantics are that DQCsim owns it,
how to compare two keys (equality);
how to hash a key.

The deletion function is passed when the key is passed. If the keys are objects of different classes, this allows different constructors to be passed here. There can only be a single comparison and hash function for each gate map, though. They are passed here.

key_cmp represents this comparison function. It takes two void* to keys and must returns whether they are equal or not. If not specified, the default is to compare the pointers themselves, instead of the values they refer to. key_cmp must be a pure function, i.e., depend only on its input values.

key_hash represents the hashing function. It takes a void* key and returns a 64-bit hash representative of the key. For any pair of keys for which key_cmp returns true, the hashes must be equal. The default behavior depends on whether key_cmp is defined: if it is, all keys will have the same hash; if it isn't, the pointer is itself hashed. key_hash must be a pure function, i.e., depend only on its input values.

It is recommended to first preprocess incoming gates with dqcs_gate_reduce_control(). In this case, controlled unitary gate matrices will be reduced to their non-controlled submatrix, such that the unitary gate detectors will operate on said submatrix. The predefined unitary gate detectors are more-or-less based on this assumption (as there are no predefined controlled matrices).

Alternatively, you can preprocess with dqcs_gate_expand_control(). In this case, you can use dqcs_gm_add_fixed_unitary() to detect the full matrix in all cases, by specifying the CNOT matrix instead of an X matrix with one control qubit.

If you don't preprocess, the upstream plugin determines the representation. That is, it may send a CNOT as a two-qubit gate with a CNOT matrix or as a controlled X gate with a single target and single control qubit. The gate map will then detect these as two different kinds of gates.