Namespace dd¶

namespace dd¶

Typedefs

template<typename T> using isVector = std::enable_if_t<std::is_same_v<T, vNode>, bool>¶

template<typename T> using isMatrix = std::enable_if_t<std::is_same_v<T, mNode>, bool>¶

template<typename T> using isMatrixVariant = std::enable_if_t<std::is_same_v<T, mNode> || std::is_same_v<T, dNode>, bool>¶

using Qubit = std::uint16_t¶

Integer type used for indexing qubits.

std::uint16_t can address up to 65536 qubits as [0, …, 65535].

Note

If you need even more qubits, this can be increased to std::uint32_t. Beware of the increased memory footprint of matrix nodes.

using fp = double¶: Floating point type to use for computations.

Note

Adjusting the precision might lead to unexpected results.

using CVec = std::vector<std::complex<fp>>¶

using SparseCVec = std::unordered_map<std::size_t, std::complex<fp>>¶

using SparsePVec = std::unordered_map<std::size_t, fp>¶

using SparsePVecStrKeys = std::unordered_map<std::string, fp>¶

using CMat = std::vector<CVec>¶

using SparseCMat = std::unordered_map<std::pair<std::size_t, std::size_t>, std::complex<fp>, PairHash>¶

using GateMatrix = std::array<std::complex<fp>, NEDGE>¶

using TwoQubitGateMatrix = std::array<std::array<std::complex<fp>, NEDGE>, NEDGE>¶

template<typename T> using isDensityMatrix = std::enable_if_t<std::is_same_v<T, dNode>, bool>¶

using AmplitudeFunc = std::function<void(std::size_t, const std::complex<fp>&)>¶

using ProbabilityFunc = std::function<void(std::size_t, const fp&)>¶

using MatrixEntryFunc = std::function<void(std::size_t, std::size_t, const std::complex<fp>&)>¶

using vEdge = Edge<vNode>¶

using vCachedEdge = CachedEdge<vNode>¶

typedef vEdge VectorDD¶

using mEdge = Edge<mNode>¶

using mCachedEdge = CachedEdge<mNode>¶

typedef mEdge MatrixDD¶

using dEdge = Edge<dNode>¶

using dCachedEdge = CachedEdge<dNode>¶

typedef dEdge DensityMatrixDD¶

using NrEdges = std::tuple_size<decltype(dNode::e)>¶

using ArrayOfEdges = std::array<dCachedEdge, NrEdges::value>¶

Enums

enum class BasisStates : std::uint8_t¶

Values:

enumerator zero¶

enumerator one¶

enumerator plus¶

enumerator minus¶

enumerator right¶

enumerator left¶

enum NoiseOperations¶

Values:

enumerator AmplitudeDamping¶

enumerator PhaseFlip¶

enumerator Depolarization¶

enumerator Identity¶

enum class GenerationWireStrategy : std::uint8_t¶

The strategy to wire two layers.

Values:

enumerator ROUNDROBIN¶

enumerator RANDOM¶

Functions

ApproximationMetadata approximate(VectorDD &state, double fidelity, Package &dd)¶

Approximate the state based on fidelity. The fidelity of the approximated state will be at least fidelity.

Traverses the decision diagram layer by layer in a breadth-first manner (iterative deepening algorithm) and eliminates edges greedily until the budget (1 - fidelity) is exhausted.

Parameters:

state – The DD to approximate.
fidelity – The desired minimum fidelity after approximation.
dd – The DD package to use for the approximation.

Returns:

Metadata about the approximation.

template<class Node> CachedEdge(Node*, const ComplexValue&) -> CachedEdge<Node>¶

template<class Node> CachedEdge(Node*, const Complex&) -> CachedEdge<Node>¶

std::ostream &operator<<(std::ostream &os, const Complex &c)¶

Print a complex number to a stream.

Parameters:

os – The output stream to write to.
c – The complex number to print.

Returns:

The output stream.

ComplexValue operator*(const Complex &c1, const ComplexValue &c2)¶

ComplexValue operator*(const ComplexValue &c1, const Complex &c2)¶

ComplexValue operator*(const Complex &c1, const Complex &c2)¶

ComplexValue operator*(const Complex &c1, fp real)¶

ComplexValue operator*(fp real, const Complex &c1)¶

ComplexValue operator/(const Complex &c1, const ComplexValue &c2)¶

ComplexValue operator/(const ComplexValue &c1, const Complex &c2)¶

ComplexValue operator/(const Complex &c1, const Complex &c2)¶

ComplexValue operator/(const Complex &c1, fp real)¶

ComplexValue operator+(const ComplexValue &c1, const ComplexValue &c2)¶

ComplexValue operator*(const ComplexValue &c1, fp r)¶

ComplexValue operator*(fp r, const ComplexValue &c1)¶

ComplexValue operator*(const ComplexValue &c1, const ComplexValue &c2)¶

ComplexValue operator/(const ComplexValue &c1, fp r)¶

ComplexValue operator/(const ComplexValue &c1, const ComplexValue &c2)¶

std::ostream &operator<<(std::ostream &os, const ComplexValue &c)¶

Print a complex value to the given output stream.

Parameters:

os – The output stream to write to.
c – The complex value to print.

Returns:

The output stream.

static std::string intToBinaryString(const std::size_t value, const std::size_t nbits)¶

Converts a decimal number to a binary string (big endian)

Parameters:

value – The decimal number to convert
nbits – The number of bits to use for the binary representation

Returns:

The binary representation of the decimal number

static std::size_t ulpDistance(fp a, fp b)¶

constexpr std::size_t murmur64(std::size_t k) noexcept¶

64bit mixing hash (from MurmurHash3)

Hash function for 64bit integers adapted from MurmurHash3

Parameters:: k – the number to hash
Returns:: the hash value

std::string colorFromPhase(const Complex &a)¶

fp thicknessFromMagnitude(const Complex &a)¶

void printPhaseFormatted(std::ostream &os, fp r)¶

std::string conditionalFormat(const Complex &a, bool formatAsPolar = true)¶

template<class Node> static std::ostream &header(const Edge<Node> &e, std::ostream &os, bool edgeLabels, bool formatAsPolar = true)¶

template<class Node> static std::ostream &coloredHeader(const Edge<Node> &e, std::ostream &os, bool edgeLabels, bool formatAsPolar = true)¶

template<class Node> static std::ostream &memoryHeader(const Edge<Node> &e, std::ostream &os, bool edgeLabels)¶

std::ostream &modernNode(const mEdge &e, std::ostream &os, bool formatAsPolar = true)¶

std::ostream &modernNode(const vEdge &e, std::ostream &os, bool formatAsPolar = true)¶

std::ostream &classicNode(const mEdge &e, std::ostream &os, bool formatAsPolar = true)¶

std::ostream &classicNode(const vEdge &e, std::ostream &os, bool formatAsPolar = true)¶

template<class Node> static std::ostream &memoryNode(const Edge<Node> &e, std::ostream &os)¶

std::ostream &bwEdge(const mEdge &from, const mEdge &to, std::uint16_t idx, std::ostream &os, bool edgeLabels = false, bool classic = false, bool formatAsPolar = true)¶

std::ostream &bwEdge(const vEdge &from, const vEdge &to, std::uint16_t idx, std::ostream &os, bool edgeLabels = false, bool classic = false, bool formatAsPolar = true)¶

std::ostream &coloredEdge(const mEdge &from, const mEdge &to, std::uint16_t idx, std::ostream &os, bool edgeLabels = false, bool classic = false, bool formatAsPolar = true)¶

std::ostream &coloredEdge(const vEdge &from, const vEdge &to, std::uint16_t idx, std::ostream &os, bool edgeLabels = false, bool classic = false, bool formatAsPolar = true)¶

template<class Node> static std::ostream &memoryEdge(const Edge<Node> &from, const Edge<Node> &to, std::uint16_t idx, std::ostream &os, bool edgeLabels = false)¶

template<class Node> static void toDot(const Edge<Node> &e, std::ostream &os, bool colored = true, bool edgeLabels = false, bool classic = false, bool memory = false, bool formatAsPolar = true)¶

template<class Node> static void export2Dot(Edge<Node> basic, const std::string &outputFilename, bool colored = true, bool edgeLabels = false, bool classic = false, bool memory = false, bool show = true, bool formatAsPolar = true)¶

void serialize(const vEdge &basic, std::ostream &os, bool writeBinary = false)¶: Serialization Note: do not rely on the binary format being portable across different architectures/platforms

void serializeMatrix(const mEdge &basic, std::int64_t &idx, std::unordered_map<mNode*, std::int64_t> &nodeIndex, std::unordered_set<mNode*> &visited, std::ostream &os, bool writeBinary = false)¶

void serialize(const mEdge &basic, std::ostream &os, bool writeBinary = false)¶

template<class Node> static void serialize(const Edge<Node> &basic, const std::string &outputFilename, bool writeBinary = false)¶

template<typename Node> static void exportEdgeWeights(const Edge<Node> &edge, std::ostream &stream)¶

MatrixDD buildFunctionality(const qc::QuantumComputation &qc, Package &dd)¶

Sequentially build a decision diagram representation for the functionality of a purely-quantum qc::QuantumComputation.

For a circuit \(G\) with \(|G|\) gates \(g_0, g_1, \ldots, g_{|G|-1}\), the functionality of \(G\) is defined as the unitary matrix \(U\) such that

\[ U = U_{|G|-1}) \cdot U_{|G|-2} \cdot \ldots \cdot U_1 \cdot U_0, \]

where \(U_i\) is the unitary matrix corresponding to gate \(g_i\). For an \(n\)-qubit quantum computation, \(U\) is a \(2^n \times 2^n\) matrix.

By representing every single operation in the circuit as a decision diagram instead of a unitary matrix and performing the matrix multiplication directly using decision diagrams, a representation of the functionality of a quantum computation can oftentimes be computed more efficiently in terms of memory and runtime.

This function effectively computes

\[ DD(U) = DD(g_{|G|-1}) \otimes DD(g_{|G|-2}) \otimes \ldots \otimes DD(g_0) \]

by sequentially applying the decision diagrams of the gates in the circuit to the current decision diagram representing the functionality of the quantum computation.

Parameters:

qc – The quantum computation to construct the functionality for
dd – The DD package to use for the construction

Returns:

The matrix diagram representing the functionality of the quantum computation

MatrixDD buildFunctionalityRecursive(const qc::QuantumComputation &qc, Package &dd)¶

Recursively build a decision diagram representation for the functionality of a purely-quantum qc::QuantumComputation.

Instead of sequentially applying the decision diagrams of the gates in the circuit, this function builds a binary computation tree out of the decision diagrams of the gates in the circuit. This results in a recursive pairwise grouping that can be more memory and runtime efficient compared to the sequential approach.

See also

buildFunctionality

See also

https://arxiv.org/abs/2103.08281

Parameters:

qc – The quantum computation to construct the functionality for
dd – The DD package to use for the construction

Returns:

The matrix diagram representing the functionality of the quantum computation

GateMatrix opToSingleQubitGateMatrix(qc::OpType t, const std::vector<fp> &params = {})¶

Converts a given quantum operation to a single-qubit gate matrix.

Parameters:

t – The quantum operation to convert
params – The parameters of the quantum operation

Returns:

The single-qubit gate matrix representation of the quantum operation

TwoQubitGateMatrix opToTwoQubitGateMatrix(qc::OpType t, const std::vector<fp> &params = {})¶

Converts a given quantum operation to a two-qubit gate matrix.

Parameters:

t – The quantum operation to convert
params – The parameters of the quantum operation

Returns:

The two-qubit gate matrix representation of the quantum operation

static inline dEdge densityFromMatrixEdge(const mEdge &e)¶

void sanityCheckOfNoiseProbabilities(double noiseProbability, double amplitudeDampingProb, double multiQubitGateFactor)¶

MatrixDD getStandardOperationDD(Package &dd, qc::OpType type, const std::vector<fp> &params, const qc::Controls &controls, const std::vector<qc::Qubit> &targets)¶

Get the decision diagram representation of an operation based on its constituent parts.

Note

This function is only intended for internal use and should not be called directly.

Parameters:

dd – The DD package to use
type – The operation type
params – The operation parameters
controls – The operation controls
targets – The operation targets

Returns:

The decision diagram representation of the operation

MatrixDD getStandardOperationDD(const qc::StandardOperation &op, Package &dd, const qc::Controls &controls, const std::vector<qc::Qubit> &targets, bool inverse)¶

Get the decision diagram representation of a qc::StandardOperation.

Note

This function is only intended for internal use and should not be called directly.

Parameters:

op – The operation to get the DD for
dd – The DD package to use
controls – The operation controls
targets – The operation targets
inverse – Whether to get the inverse of the operation

Returns:

The decision diagram representation of the operation

MatrixDD getDD(const qc::Operation &op, Package &dd, const qc::Permutation &permutation = {}, bool inverse = false)¶

Get the decision diagram representation of an operation.

Parameters:

op – The operation to get the DD for
dd – The DD package to use
permutation – The permutation to apply to the operation’s qubits. An empty permutation marks the identity permutation.
inverse – Whether to get the inverse of the operation

Returns:

The decision diagram representation of the operation

MatrixDD getInverseDD(const qc::Operation &op, Package &dd, const qc::Permutation &permutation = {})¶

Get the decision diagram representation of the inverse of an operation.

See also

getDD

Parameters:

op – The operation to get the inverse DD for
dd – The DD package to use
permutation – The permutation to apply to the operation’s qubits. An empty permutation marks the identity permutation.

Returns:

The decision diagram representation of the inverse of the operation

VectorDD applyUnitaryOperation(const qc::Operation &op, const VectorDD &in, Package &dd, const qc::Permutation &permutation = {})¶

Apply a unitary operation to a given vector DD.

This is a convenience function that realizes op times in and correctly accounts for the permutation of the operation’s qubits as well as automatically handles reference counting.

Parameters:

op – The operation to apply
in – The input DD
dd – The DD package to use
permutation – The permutation to apply to the operation’s qubits. An empty permutation marks the identity permutation.

Returns:

The output DD

MatrixDD applyUnitaryOperation(const qc::Operation &op, const MatrixDD &in, Package &dd, const qc::Permutation &permutation = {}, bool applyFromLeft = true)¶

Apply a unitary operation to a given matrix DD.

This is a convenience function that realizes op times in and correctly accounts for the permutation of the operation’s qubits as well as automatically handles reference counting.

Parameters:

op – The operation to apply
in – The input DD
dd – The DD package to use
permutation – The permutation to apply to the operation’s qubits. An empty permutation marks the identity permutation.
applyFromLeft – Whether to apply the operation from the left (true) or from the right (false).

Returns:

The output DD

VectorDD applyMeasurement(const qc::NonUnitaryOperation &op, VectorDD in, Package &dd, std::mt19937_64 &rng, std::vector<bool> &measurements, const qc::Permutation &permutation = {})¶

Apply a measurement operation to a given DD.

This is a convenience function that realizes the measurement op on in and stores the measurement results in measurements. The result is determined based on the RNG rng. The function correctly accounts for the permutation of the operation’s qubits as well as automatically handles reference counting.

Parameters:

op – The measurement operation to apply
in – The input DD
dd – The DD package to use
rng – The random number generator to use
measurements – The vector to store the measurement results in
permutation – The permutation to apply to the operation’s qubits. An empty permutation marks the identity permutation.

Returns:

The output DD

VectorDD applyReset(const qc::NonUnitaryOperation &op, VectorDD in, Package &dd, std::mt19937_64 &rng, const qc::Permutation &permutation = {})¶

Apply a reset operation to a given DD.

This is a convenience function that realizes the reset op on in. To this end, it measures the qubit and applies an X operation if the measurement result is one. The result is determined based on the RNG rng. The function correctly accounts for the permutation of the operation’s qubits as well as automatically handles reference counting.

Parameters:

op – The reset operation to apply
in – The input DD
dd – The DD package to use
rng – The random number generator to use
permutation – The permutation to apply to the operation’s qubits. An empty permutation marks the identity permutation.

Returns:

The output DD

VectorDD applyIfElseOperation(const qc::IfElseOperation &op, const VectorDD &in, Package &dd, const std::vector<bool> &measurements, const qc::Permutation &permutation = {})¶

Apply an if-else operation to a given DD.

This is a convenience function that realizes the if-else operation op on in. It applies the underlying operation if the actual value stored in the measurement results matches the expected value according to the comparison kind. The function correctly accounts for the permutation of the operation’s qubits as well as automatically handles reference counting.

Parameters:

op – The if-else operation to apply
in – The input DD
dd – The DD package to use
measurements – The vector of measurement results
permutation – The permutation to apply to the operation’s qubits. An empty permutation marks the identity permutation.

Returns:

The output DD

bool isExecutableVirtually(const qc::Operation &op) noexcept¶

Check whether op is virtually executable.

Parameters:: op – The operation in question.
Returns:: Whether op is virtually executable.

void applyVirtualOperation(const qc::Operation &op, qc::Permutation &permutation) noexcept¶

Apply virtual operation op.

Parameters:

op – The virtual operation to apply.
permutation – If suitable, the to be updated permutation.

VectorDD applyGlobalPhase(VectorDD &in, const fp &phase, Package &dd)¶

Apply global phase to a given DD.

Parameters:

in – The input DD
phase – The phase to apply
dd – The DD package to use

Returns:

The output DD

template<class DDType> void changePermutation(DDType &on, qc::Permutation &from, const qc::Permutation &to, Package &dd, const bool regular = true)¶

Change the permutation of a given DD.

This function changes the permutation of the given DD on from from to to by applying SWAP gates. The from permutation must be at least as large as the to permutation.

Template Parameters:

DDType – The type of the DD

Parameters:

on – The DD to change the permutation of
from – The current permutation
to – The target permutation
dd – The DD package to use
regular – Whether to apply the permutation from the left (true) or from the right (false)

VectorDD simulate(const qc::QuantumComputation &qc, const VectorDD &in, Package &dd)¶

Simulate a purely-quantum qc::QuantumComputation on a given input state using decision diagrams.

This method classically simulates the quantum computation qc on the input state in by sequentially applying the operations in the circuit to the initial state via decision diagram multiplication.

This simple simulation method can only handle circuits that do not contain any classical control operations or measurements. Its main purpose is to construct a representation of the statevector after simulating the quantum computation for the given input state. For more elaborate simulation methods that can handle classical control and mid-circuit measurements, see sample(const QuantumComputation&,

std::size_t, std::size_t).

Parameters:

qc – The quantum computation to simulate
in – The input state to simulate. Represented as a vector DD.
dd – The DD package to use for the simulation

Returns:

A vector DD representing the output state of the simulation

std::map<std::string, std::size_t> sample(const qc::QuantumComputation &qc, std::size_t shots = 1024U, std::size_t seed = 0U)¶

Sample from the output distribution of a quantum computation.

This method classically simulates the quantum computation qc starting from the all-zero state and samples shots times from the output distribution. The seed for the random number generator can be set using seed.

For a circuit without mid-circuit measurements, this function will construct a representation of the final statevector similar to simulate and then repeatedly sample from the resulting decision diagram, without actually collapsing the state. For a fixed number of qubits, each sample can be drawn in constant time, which is a significant of the decision diagram structure.

For a circuit with mid-circuit measurements, this function will separately execute the circuit for each sample, probabilistically collapsing the state after each measurement.

Parameters:

qc – The quantum computation to simulate
shots – The number of shots to sample
seed – The seed for the random number generator

Returns:

A histogram of the measurement results

std::map<std::string, std::size_t> sample(const qc::QuantumComputation &qc, const VectorDD &in, Package &dd, std::size_t shots, std::size_t seed = 0U)¶

Sample from the output distribution of a quantum computation.

This is a more general version of sample that allows for choosing the input state to simulate as well as the DD package to use for the simulation.

Parameters:

qc – The quantum computation to simulate
in – The input state to simulate. Represented as a vector DD.
dd – The DD package to use for the simulation
shots – The number of shots to sample
seed – The seed for the random number generator

Returns:

A histogram of the measurement results

VectorDD makeZeroState(std::size_t n, Package &dd, std::size_t start = 0)¶

Construct the all-zero state \(|0...0\rangle\).

Parameters:

n – The number of qubits.
dd – The DD package to use for making the vector DD.
start – The starting qubit index. Default is 0.

Throws:

`std::invalid_argument` – dd.qubits() < n.

Returns:

A vector DD for the all-zero state.

VectorDD makeBasisState(std::size_t n, const std::vector<bool> &state, Package &dd, std::size_t start = 0)¶

Construct a computational basis state \(|b_{n-1}...b_0\rangle\).

Parameters:

n – The number of qubits.
state – The state to construct.
dd – The DD package to use for making the vector DD.
start – The starting qubit index. Default is 0.

Throws:

`std::invalid_argument` – dd.qubits() < n or size(state) < n.

Returns:

A vector DD for the computational basis state.

VectorDD makeBasisState(std::size_t n, const std::vector<BasisStates> &state, Package &dd, std::size_t start = 0)¶

Construct a product state out of \(\{0, 1, +, -, R, L\}^{\otimes n}\).

Parameters:

n – The number of qubits
state – The state to construct.
dd – The DD package to use for making the vector DD.
start – The starting qubit index. Default is 0.

Throws:

`std::invalid_argument` – dd.qubits() < n or size(state) < n.

Returns:

A vector DD for the product state.

VectorDD makeGHZState(std::size_t n, Package &dd)¶

Construct a GHZ state \(|0...0\rangle + |1...1\rangle\).

Parameters:

n – The number of qubits.
dd – The DD package to use for making the vector DD.

Throws:

`std::invalid_argument` – dd.qubits() < n.

Returns:

A vector DD for the GHZ state.

VectorDD makeWState(std::size_t n, Package &dd)¶

Construct a W state.

The W state is defined as

\[ |0...01\rangle + |0...10\rangle + |10...0\rangle \]

Parameters:

n – The number of qubits.
dd – The DD package to use for making the vector DD.

Throws:

`std::invalid_argument` – dd.qubits() < n or the number of qubits and currently set tolerance would lead to an underflow.

Returns:

A vector DD for the W state.

VectorDD makeStateFromVector(const CVec &vec, Package &dd)¶

Construct a decision diagram from an arbitrary state vector.

Parameters:

vec – The state vector to convert to a DD.
dd – The DD package to use for making the vector DD.

Throws:

`std::invalid_argument` – vec.size() is not a power of two or dd.qubits() < log2(vec.size()) - 1.

Returns:

A vector DD representing the state.

VectorDD generateExponentialState(std::size_t levels, Package &dd)¶

Generate exponentially large vector DD.

Parameters:

levels – The number of levels in the vector DD.
dd – The DD package to use for generating the vector DD.

Throws:

`std::invalid_argument` – dd.qubits() < levels.

Returns:

The exponentially large vector DD.

VectorDD generateExponentialState(std::size_t levels, Package &dd, std::size_t seed)¶

Generate exponentially large vector DD. Use seed for randomization.

Parameters:

levels – The number of levels in the vector DD.
dd – The DD package to use for generating the vector DD.
seed – The seed used for randomization.

Throws:

`std::invalid_argument` – dd.qubits() < levels.

Returns:

The exponentially large vector DD.

VectorDD generateRandomState(std::size_t levels, const std::vector<std::size_t> &nodesPerLevel, GenerationWireStrategy strategy, Package &dd)¶

Generate random vector DD.

Parameters:

levels – The number of levels in the vector DD.
nodesPerLevel – The number of nodes per level.
strategy – The strategy to wire two layers.
dd – The DD package to use for generating the vector DD.

Throws:

`std::invalid_argument` – dd.qubits() < levels.

Returns:

The random vector DD.

VectorDD generateRandomState(std::size_t levels, const std::vector<std::size_t> &nodesPerLevel, GenerationWireStrategy strategy, Package &dd, std::size_t seed)¶

Generate random vector DD. Use seed for randomization.

Parameters:

levels – The number of levels in the vector DD.
nodesPerLevel – The number of nodes per level.
strategy – The strategy to wire two layers.
dd – The DD package to use for generating the vector DD.
seed – The seed used for randomization.

Throws:

`std::invalid_argument` – dd.qubits() < levels, levels <= 0, or nodesPerLevel.size() != levels.

Returns:

The random vector DD.

double computeActiveMemoryMiB(Package &package)¶

Computes an estimate for the memory usage of active DDs.

The estimate is based on the number of active entries which are computed by temporarily marking all nodes reachable from the current root set and subsequently counting them in the unique tables. It accounts for the memory used by DD nodes, DD edges, and real numbers.

Parameters:: package – The package instance
Returns:: The estimated memory usage in MiB

double computePeakMemoryMiB(const Package &package)¶

Computes an estimate for the peak memory usage of DDs.

The estimate is based on the peak number of used entries in the respective memory managers. It accounts for the memory used by DD nodes, DD edges, and real numbers.

Parameters:: package – The package instance
Returns:: The estimated memory usage in MiB

nlohmann::json getStatistics(Package &package, bool includeIndividualTables = false)¶

nlohmann::json getDataStructureStatistics()¶

Get some key statistics about data structures used by the DD package.

Returns:: A JSON representation of the statistics

std::string getStatisticsString(Package &package)¶

void printStatistics(Package &package, std::ostream &os = std::cout)¶

Variables

static constexpr std::uint8_t RADIX = 2¶

static constexpr std::uint8_t NEDGE = RADIX * RADIX ¶

static constexpr auto SQRT2_2 = static_cast<fp>(0.707106781186547524400844362104849039284835937688474036588L)¶

static constexpr fp PI = std::numbers::pi¶

static constexpr auto PI_2 = PI / 2¶

static constexpr fp PI_4 = PI / 4¶

static constexpr std::uint64_t SERIALIZATION_VERSION = 1¶

constexpr auto STOCHASTIC_NOISE_SIMULATOR_DD_PACKAGE_CONFIG = []() { DDPackageConfigconfig{};config.stochasticCacheOps = qc::OpType::OpTypeEnd;config.ctVecAddMagNumBucket = 1U;config.ctMatAddMagNumBucket = 1U;config.ctVecConjNumBucket = 1U;return config;}()¶

constexpr auto DENSITY_MATRIX_SIMULATOR_DD_PACKAGE_CONFIG = []() { DDPackageConfigconfig{};config.utDmNumBucket = 65536U;config.utDmInitialAllocationSize = 4096U;config.ctDmDmMultNumBucket = 16384U;config.ctDmAddNumBucket = 16384U;config.ctDmNoiseNumBucket = 4096U;config.utMatNumBucket = 16384U;config.ctMatAddNumBucket = 4096U;config.ctVecAddNumBucket = 4096U;config.ctMatConjTransNumBucket = 4096U;config.ctMatMatMultNumBucket = 1U;config.ctMatVecMultNumBucket = 1U;config.utVecNumBucket = 1U;config.utVecInitialAllocationSize = 1U;config.utMatInitialAllocationSize = 1U;config.ctVecKronNumBucket = 1U;config.ctMatKronNumBucket = 1U;config.ctDmTraceNumBucket = 4096U;config.ctMatTraceNumBucket = 1U;config.ctVecInnerProdNumBucket = 1U;config.stochasticCacheOps = 1U;config.ctVecAddMagNumBucket = 1U;config.ctMatAddMagNumBucket = 1U;config.ctVecConjNumBucket = 1U;return config;}()¶

constexpr auto UNITARY_SIMULATOR_DD_PACKAGE_CONFIG = []() { DDPackageConfigconfig{};config.utMatNumBucket = 65'536U;config.ctMatAddNumBucket = 65'536U;config.ctMatMatMultNumBucket = 65'536U;config.utVecNumBucket = 1U;config.utVecInitialAllocationSize = 1U;config.ctVecAddNumBucket = 1U;config.ctVecAddMagNumBucket = 1U;config.ctMatAddMagNumBucket = 1U;config.ctVecConjNumBucket = 1U;config.ctMatConjTransNumBucket = 1U;config.ctMatVecMultNumBucket = 1U;config.ctVecKronNumBucket = 1U;config.ctMatKronNumBucket = 1U;config.ctMatTraceNumBucket = 1U;config.ctVecInnerProdNumBucket = 1U;return config;}()¶

constexpr GateMatrix MEAS_ZERO_MAT = {1, 0, 0, 0}¶: Single-qubit gate matrix for collapsing a qubit to the |0> state.

constexpr GateMatrix MEAS_ONE_MAT = {0, 0, 0, 1}¶: Single-qubit gate matrix for collapsing a qubit to the |1> state.

struct ApproximationMetadata¶

#include <Approximation.hpp>

Useful metadata of an approximation run.

Public Members

double fidelity¶: The fidelity between the source and the approximated state.

std::size_t nodesVisited¶: The number of nodes visited during the mark stage.

Qubit min¶: The lowest qubit number that requires rebuilding.

template<typename Node> struct CachedEdge¶

#include <CachedEdge.hpp>

A DD node with a cached edge weight.

Some DD operations create intermediate results that are not part of the final result. To avoid storing these intermediate results in the unique table, they are represented via cached numbers.

Template Parameters:: Node – Type of the DD node

Public Functions

inline bool operator==(const CachedEdge &other) const¶: Comparing two DD edges with another involves comparing the respective pointers and checking whether the corresponding weights are “close enough” according to a given tolerance this notion of equivalence is chosen to counter floating point inaccuracies

inline constexpr bool isTerminal() const¶

Check whether this is a terminal.

Returns:: whether this is a terminal

template<typename T = Node, isMatrixVariant<T> = true> inline bool isIdentity(const bool upToGlobalPhase = true) const¶

Check whether the matrix represented by the DD is the identity.

Template Parameters:: T – template parameter to enable this function only for matrix nodes
Returns:: whether the matrix is the identity

Public Static Functions

static inline constexpr CachedEdge terminal(const ComplexValue &w)¶

Create a terminal edge with the given weight.

Parameters:: w – The weight of the terminal edge.
Returns:: A terminal edge with the given weight.

static inline constexpr CachedEdge terminal(const std::complex<fp> &w)¶

Create a terminal edge with the given weight.

Parameters:: w – The weight of the terminal edge.
Returns:: A terminal edge with the given weight.

static inline constexpr CachedEdge terminal(const Complex &w)¶

Create a terminal edge with the given weight.

Parameters:: w – The weight of the terminal edge.
Returns:: A terminal edge with the given weight.

static inline constexpr CachedEdge zero()¶

Create a zero terminal edge.

Returns:: A zero terminal edge.

static inline constexpr CachedEdge one()¶

Create a one terminal edge.

Returns:: A one terminal edge.

template<typename T = Node, isVector<T> = true> static auto normalize(Node *p, const std::array<CachedEdge, RADIX> &e, MemoryManager &mm, ComplexNumbers &cn) -> CachedEdge ¶

Get a normalized vector DD from a fresh node and a list of edges.

Template Parameters:

T – template parameter to enable this method only for vNode

Parameters:

p – the fresh node
e – the list of edges that form the successor nodes
mm – a reference to the memory manager (for returning unused nodes)
cn – a reference to the complex number manager (for adding new complex numbers)

Returns:

the normalized vector DD

template<typename T = Node, isMatrixVariant<T> = true> static auto normalize(Node *p, const std::array<CachedEdge, NEDGE> &e, MemoryManager &mm, ComplexNumbers &cn) -> CachedEdge ¶

Get a normalized (density) matrix) DD from a fresh node and a list of edges.

Template Parameters:

T – template parameter to enable this method only for matrix nodes

Parameters:

p – the fresh node
e – the list of edges that form the successor nodes
mm – a reference to the memory manager (for returning unused nodes)
cn – a reference to the complex number manager (for adding new complex numbers)

Returns:

the normalized (density) matrix DD

struct Complex¶

#include <Complex.hpp>

A complex number represented by two pointers to compute table entries.

Public Functions

inline constexpr bool exactlyZero() const noexcept¶

Check whether the complex number is exactly equal to zero.

See also

RealNumber::exactlyZero

Returns:: True if the complex number is exactly equal to zero, false otherwise.

inline constexpr bool exactlyOne() const noexcept¶

Check whether the complex number is exactly equal to one.

See also

RealNumber::exactlyOne

See also

RealNumber::exactlyZero

Returns:: True if the complex number is exactly equal to one, false otherwise.

bool approximatelyEquals(const Complex &c) const noexcept¶

Check whether the complex number is approximately equal to the given complex number.

See also

RealNumber::approximatelyEquals

Parameters:: c – The complex number to compare to.
Returns:: True if the complex number is approximately equal to the given complex number, false otherwise.

bool approximatelyZero() const noexcept¶

Check whether the complex number is approximately equal to zero.

See also

RealNumber::approximatelyZero

Returns:: True if the complex number is approximately equal to zero, false otherwise.

void mark() const noexcept¶: Mark the complex number as used.

void unmark() const noexcept¶: Unmark the complex number.

std::string toString(bool formatted = true, int precision = -1) const¶

Convert the complex number to a string.

See also

ComplexValue::toString

Parameters:

formatted – Whether to apply special formatting to the numbers.
precision – The precision to use for the numbers.

Returns:

The string representation of the complex number.

void writeBinary(std::ostream &os) const¶

Write the complex number to a binary stream.

See also

RealNumber::writeBinary

Parameters:: os – The output stream to write to.

explicit operator ComplexValue() const noexcept¶

Convert the Complex number to a ComplexValue.

Returns:: The ComplexValue representation of the Complex number.

Public Members

RealNumber *r¶: Compute table entry for the real part.

RealNumber *i¶: Compute table entry for the imaginary part.

Public Static Functions

static inline constexpr Complex zero() noexcept¶

The static constant for the complex number zero.

Returns:: A complex number with real and imaginary part equal to zero.

static inline constexpr Complex one() noexcept¶

The static constant for the complex number one.

Returns:: A complex number with real part equal to one and imaginary part equal to zero.

class ComplexNumbers¶

#include <ComplexNumbers.hpp>

A class for managing complex numbers in the DD package.

Public Functions

inline explicit ComplexNumbers(RealNumberUniqueTable &table)¶: Default constructor.

~ComplexNumbers() = default¶: Default destructor.

Complex lookup(const Complex &c)¶

Lookup a complex value in the complex table; if not found add it.

Parameters:: c – The complex number.
Returns:: The found or added complex number.

Complex lookup(const std::complex<fp> &c)¶

See also

lookup(fp r, fp i)

Complex lookup(const ComplexValue &c)¶

See also

lookup(fp r, fp i)

Complex lookup(fp r)¶

Lookup a real value in the complex table; if not found add it.

Parameters:: r – The real number.
Returns:: The found or added complex number with real part r and imaginary part zero.

Complex lookup(fp r, fp i)¶

Lookup a complex value in the complex table; if not found add it.

See also

ComplexTable::lookup

Parameters:

r – The real part.
i – The imaginary part.

Returns:

The found or added complex number.

template<class Node> inline Edge<Node> lookup(const CachedEdge<Node> &ce)¶

Turn CachedEdge into Edge via lookup.

Template Parameters:: Node – The type of the node.
Parameters:: ce – The cached edge.
Returns:: The edge with looked-up weight. The zero terminal if the new weight is exactly zero.

std::size_t realCount() const noexcept¶

Get the number of stored real numbers.

Returns:: The number of stored real numbers.

Public Static Functions

static void setTolerance(fp tol) noexcept¶

Set the numerical tolerance for comparisons of floats.

Parameters:: tol – The new tolerance.

static fp mag2(const Complex &a) noexcept¶

Compute the squared magnitude of a complex number.

Parameters:: a – The complex number.
Returns:: The squared magnitude.

static fp mag(const Complex &a) noexcept¶

Compute the magnitude of a complex number.

Parameters:: a – The complex number.
Returns:: The magnitude.

static fp arg(const Complex &a) noexcept¶

Compute the argument of a complex number.

Parameters:: a – The complex number.
Returns:: The argument.

static Complex conj(const Complex &a) noexcept¶

Compute the complex conjugate of a complex number.

Note

Conjugation is efficiently handled by just flipping the sign of the imaginary pointer.

Parameters:: a – The complex number.
Returns:: The complex conjugate.

static Complex neg(const Complex &a) noexcept¶

Compute the negation of a complex number.

Note

Negation is efficiently handled by just flipping the sign of both pointers.

Parameters:: a – The complex number.
Returns:: The negation.

static inline constexpr bool isStaticComplex(const Complex &c)¶

Check whether a complex number is one of the static ones.

Parameters:: c – The complex number.
Returns:: Whether the complex number is one of the static ones.

struct ComplexValue¶

#include <ComplexValue.hpp>

A complex number represented by two floating point values.

Public Functions

bool operator==(const ComplexValue &other) const noexcept¶

Check for exact equality.

Parameters:: other – The other complex number to compare to.
Returns:: True if the complex numbers are exactly equal, false otherwise.

bool operator!=(const ComplexValue &other) const noexcept¶

See also

operator==

inline bool exactlyZero() const noexcept¶

Check whether the complex number is exactly equal to zero.

Returns:: True if the complex number is exactly equal to zero, false otherwise.

inline bool exactlyOne() const noexcept¶

Check whether the complex number is exactly equal to one.

Returns:: True if the complex number is exactly equal to one, false otherwise.

bool approximatelyEquals(const ComplexValue &c) const noexcept¶

Check whether the complex number is approximately equal to the given complex number.

See also

RealNumber::approximatelyEquals

Parameters:: c – The complex number to compare to.
Returns:: True if the complex number is approximately equal to the given complex number, false otherwise.

bool approximatelyZero() const noexcept¶

Check whether the complex number is approximately equal to zero.

See also

RealNumber::approximatelyZero

Returns:: True if the complex number is approximately equal to zero, false otherwise.

void writeBinary(std::ostream &os) const¶

Write a binary representation of the complex number to the given output stream.

Parameters:: os – The output stream to write to.

void readBinary(std::istream &is)¶

Read a binary representation of the complex number from the given input stream.

Parameters:: is – The input stream to read from.

void fromString(const std::string &realStr, std::string imagStr)¶

Construct a complex number from a string.

Parameters:

realStr – The string representation of the real part.
imagStr – The string representation of the imaginary part.

inline explicit operator auto() const noexcept¶: Automatically convert to std::complex<fp>

inline fp mag2() const noexcept¶

Compute the squared magnitude of the complex number.

Returns:: The squared magnitude of the complex number.

inline fp mag() const noexcept¶

Compute the magnitude of the complex number.

Returns:: The magnitude of the complex number.

ComplexValue &operator+=(const ComplexValue &rhs) noexcept¶: In-place addition of two complex numbers.

Public Members

fp r = {}¶: real part

fp i = {}¶: imaginary part

Public Static Functions

static std::pair<std::uint64_t, std::uint64_t> getLowestFraction(fp x, std::uint64_t maxDenominator = 1U << 10)¶

Get the closest fraction to the given number.

Parameters:

x – The number to approximate.
maxDenominator – The maximum denominator to use.

Returns:

The closest fraction to the given number as a pair of numerator and denominator.

static void printFormatted(std::ostream &os, fp num, bool imaginary = false)¶

Pretty print the given real number to the given output stream.

Parameters:

os – The output stream to write to.
num – The number to print.
imaginary – Whether the number is imaginary.

static std::string toString(const fp &real, const fp &imag, bool formatted = true, int precision = -1)¶

Print the given complex number to the given output stream.

Parameters:

real – The real part of the complex number.
imag – The imaginary part of the complex number.
formatted – Whether to pretty print the number.
precision – The precision to use for printing numbers..

Returns:

The string representation of the complex number.

template<class LeftOperandType, class RightOperandType, class ResultType> class ComputeTable¶

#include <ComputeTable.hpp>

Data structure for caching computed results of binary operations.

Template Parameters:

LeftOperandType – type of the operation’s left operand
RightOperandType – type of the operation’s right operand
ResultType – type of the operation’s result

Public Functions

inline explicit ComputeTable(const size_t numBuckets = DEFAULT_NUM_BUCKETS)¶

Default constructor

Parameters:: numBuckets – Number of hash table buckets. Must be a power of two.

inline std::size_t hash(const LeftOperandType &leftOperand, const RightOperandType &rightOperand) const¶

Compute the hash value for a given pair of operands.

Parameters:

leftOperand – The left operand
rightOperand – The right operand

Returns:

The hash value

inline const auto &getTable() const¶: Get a reference to the underlying table.

inline const auto &getStats() const noexcept¶: Get a reference to the statistics.

inline void insert(const LeftOperandType &leftOperand, const RightOperandType &rightOperand, const ResultType &result)¶

Insert a new entry into the compute table.

Any existing entry for the resulting hash value will be replaced.

Parameters:

leftOperand – The left operand
rightOperand – The right operand
result – The result of the operation

inline ResultType *lookup(const LeftOperandType &leftOperand, const RightOperandType &rightOperand, const bool useDensityMatrix = false)¶

Look up a result in the compute table.

Parameters:

leftOperand – The left operand
rightOperand – The right operand
useDensityMatrix – Whether a density matrix is expected

Returns:

A pointer to the result if it is found, otherwise nullptr.

inline void clear()¶

Clear the compute table.

Sets all entries to invalid.

inline std::ostream &printStatistics(std::ostream &os = std::cout) const¶

Print the statistics of the compute table.

Parameters:: os – The output stream to print to
Returns:: The output stream

Public Static Attributes

static constexpr std::size_t DEFAULT_NUM_BUCKETS = 16384U¶: Default number of buckets for the compute table.

struct Entry¶

#include <ComputeTable.hpp>

An entry in the compute table.

A triple consisting of the left operand, the right operand, and the result of a binary operation.

struct DDPackageConfig¶

template<class OperandType, class ResultType> class DensityNoiseTable¶

#include <DensityNoiseTable.hpp>

Data structure for caching computed results of noise operations.

Template Parameters:

OperandType – type of the operation’s operand
ResultType – type of the operation’s result

Public Functions

inline explicit DensityNoiseTable(const size_t numBuckets = 32768U)¶

Default constructor

Parameters:: numBuckets – Number of hash table buckets. Must be a power of two.

inline const auto &getTable() const¶: Get a reference to the table.

inline const auto &getStats() const noexcept¶: Get a reference to the statistics.

struct Entry¶

class DeterministicNoiseFunctionality¶

struct dNode : public dd::NodeBase ¶

#include <Node.hpp>

A density matrix DD node.

Data Layout (8)|(2|2|4)|(24|24|24|24) = 112B

Public Functions

inline dNode *next() const noexcept¶: Getter for the next object.

Public Static Functions

static inline constexpr dNode *getTerminal() noexcept¶: Getter for the terminal object.

template<class Node> struct Edge¶

#include <Edge.hpp>

A weighted edge pointing to a DD node.

This struct is used to represent the core data structure of the DD package. It is a wrapper around a pointer to a DD node and a complex edge weight.

Template Parameters:: Node – Type of the DD node

Public Functions

inline constexpr bool operator==(const Edge &other) const¶: Comparing two DD edges with another involves comparing the respective pointers and checking whether the corresponding weights are “close enough” according to a given tolerance this notion of equivalence is chosen to counter floating point inaccuracies

inline constexpr bool isTerminal() const¶

Check whether this is a terminal.

Returns:: whether this is a terminal

inline constexpr bool isZeroTerminal() const¶

Check whether this is a zero terminal.

Returns:: whether this is a zero terminal

inline constexpr bool isOneTerminal() const¶

Check whether this is a one terminal.

Returns:: whether this is a one terminal

std::complex<fp> getValueByPath(std::size_t numQubits, const std::string &decisions) const¶

Get a single element of the vector or matrix represented by the DD.

Parameters:

numQubits – number of qubits in the considered DD
decisions – string {0, 1, 2, 3}^n describing which outgoing edge should be followed (for vectors entries are limited to 0 and 1) If string is longer than required, the additional characters are ignored.

Returns:

the complex amplitude of the specified element

std::size_t size() const¶

Get the size of the DD.

The size of a DD is defined as the number of nodes (including the terminal node) in the DD.

Returns:: the size of the DD

void mark() const noexcept¶: Mark the edge as used.

void unmark() const noexcept¶: Unmark the edge.

template<typename T = Node, isVector<T> = true> std::complex<fp> getValueByIndex(std::size_t i) const¶

Get a single element of the vector represented by the DD.

Template Parameters:: T – template parameter to enable this function only for vNode
Parameters:: i – index of the element
Returns:: the complex value of the amplitude

template<typename T = Node, isVector<T> = true> CVec getVector(fp threshold = 0.) const¶

Get the vector represented by the DD.

Template Parameters:: T – template parameter to enable this function only for vNode
Parameters:: threshold – amplitudes with a magnitude below this threshold will be ignored
Returns:: the vector

template<typename T = Node, isVector<T> = true> SparseCVec getSparseVector(fp threshold = 0.) const¶

Get the sparse vector represented by the DD.

Template Parameters:: T – template parameter to enable this function only for vNode
Parameters:: threshold – amplitudes with a magnitude below this threshold will be ignored
Returns:: the sparse vector

template<typename T = Node, isVector<T> = true> void printVector() const¶

Print the vector represented by the DD.

Note

This function scales exponentially with the number of qubits.

Template Parameters:: T – template parameter to enable this function only for vNode

template<typename T = Node, isVector<T> = true> void addToVector(CVec &amplitudes) const¶

Add the amplitudes of a vector DD to a vector.

Template Parameters:: T – template parameter to enable this function only for vNode
Parameters:: amplitudes – the vector to add to

template<typename T = Node, isMatrixVariant<T> = true> inline bool isIdentity(const bool upToGlobalPhase = true) const¶

Check whether the matrix represented by the DD is the identity.

Template Parameters:: T – template parameter to enable this function only for matrix nodes
Returns:: whether the matrix is the identity

template<typename T = Node, isMatrixVariant<T> = true> std::complex<fp> getValueByIndex(std::size_t numQubits, std::size_t i, std::size_t j) const¶

Get a single element of the matrix represented by the DD.

Template Parameters:

T – template parameter to enable this function only for matrix nodes

Parameters:

numQubits – number of qubits in the considered DD
i – row index of the element
j – column index of the element

Returns:

the complex value of the entry

template<typename T = Node, isMatrixVariant<T> = true> CMat getMatrix(std::size_t numQubits, fp threshold = 0.) const¶

Get the matrix represented by the DD.

Template Parameters:

T – template parameter to enable this function only for matrix nodes

Parameters:

numQubits – number of qubits in the considered DD
threshold – entries with a magnitude below this threshold will be ignored

Returns:

the matrix

template<typename T = Node, isMatrixVariant<T> = true> SparseCMat getSparseMatrix(std::size_t numQubits, fp threshold = 0.) const¶

Get the sparse matrix represented by the DD.

Template Parameters:

T – template parameter to enable this function only for matrix nodes

Parameters:

numQubits – number of qubits in the considered DD
threshold – entries with a magnitude below this threshold will be ignored

Returns:

the sparse matrix

template<typename T = Node, isMatrixVariant<T> = true> void printMatrix(std::size_t numQubits) const¶

Print the matrix represented by the DD.

Note

This function scales exponentially with the number of qubits.

Template Parameters:: T – template parameter to enable this function only for matrix nodes
Parameters:: numQubits – number of qubits in the considered DD

template<typename T = Node, isMatrixVariant<T> = true> void traverseMatrix(const std::complex<fp> &amp, std::size_t i, std::size_t j, MatrixEntryFunc f, std::size_t level, fp threshold = 0.) const¶

Recursively traverse the DD and call a function for each non-zero matrix entry.

Template Parameters:

T – template parameter to enable this function only for matrix nodes

Parameters:

amp – the accumulated amplitude from previous traversals
i – the current row index in the matrix
j – the current column index in the matrix
f – This function is called for each non-zero matrix entry with the row index, the column index and the amplitude as arguments.
level – the current level in the DD (ranges from 1 to n for regular nodes and is 0 for the terminal node)
threshold – entries with a magnitude below this threshold will be ignored

template<typename T = Node, isDensityMatrix<T> = true> SparsePVec getSparseProbabilityVector(std::size_t numQubits, fp threshold = 0.) const¶

Get the sparse probability vector for the underlying density matrix.

Template Parameters:

T – template parameter to enable this function only for dNode

Parameters:

numQubits – number of qubits in the considered DD
threshold – probabilities below this threshold will be ignored

Returns:

the sparse probability vector

template<typename T = Node, isDensityMatrix<T> = true> SparsePVecStrKeys getSparseProbabilityVectorStrKeys(std::size_t numQubits, fp threshold = 0.) const¶

Get the sparse probability vector for the underlying density matrix.

Template Parameters:

T – template parameter to enable this function only for dNode

Parameters:

numQubits – number of qubits in the considered DD
threshold – probabilities below this threshold will be ignored

Returns:

the sparse probability vector (using strings as keys)

Public Static Functions

static inline constexpr Edge zero()¶

Get the static zero terminal.

Returns:: the zero terminal

static inline constexpr Edge one()¶

Get the static one terminal.

Returns:: the one terminal

static inline constexpr Edge terminal(const Complex &w)¶

Get a terminal DD with a given edge weight.

Parameters:: w – the edge weight
Returns:: the terminal DD representing (w)

static inline constexpr bool trackingRequired(const Edge &e)¶

Check whether an edge requires tracking.

Parameters:: e – The edge to check.
Returns:: Whether the edge requires tracking.

template<typename T = Node, isVector<T> = true> static auto normalize(Node *p, const std::array<Edge, RADIX> &e, MemoryManager &mm, ComplexNumbers &cn) -> Edge ¶

Get a normalized vector DD from a fresh node and a list of edges.

Template Parameters:

T – template parameter to enable this function only for vNode

Parameters:

p – the fresh node
e – the list of edges that form the successor nodes
mm – a reference to the memory manager (for returning unused nodes)
cn – a reference to the complex number manager (for adding new complex numbers)

Returns:

the normalized vector DD

template<typename T = Node, isMatrixVariant<T> = true> static auto normalize(Node *p, const std::array<Edge, NEDGE> &e, MemoryManager &mm, ComplexNumbers &cn) -> Edge ¶

Get a normalized (density) matrix DD from a fresh node and a list of edges.

Template Parameters:

T – template parameter to enable this function only for matrix nodes

Parameters:

p – the fresh node
e – the list of edges that form the successor nodes
mm – a reference to the memory manager (for returning unused nodes)
cn – a reference to the complex number manager (for adding new complex numbers)

Returns:

the normalized (density) matrix DD

struct LLBase¶

#include <LinkedListBase.hpp>

A class to provide a base for linked list objects.

Subclassed by dd::NodeBase, dd::RealNumber

Public Functions

inline LLBase *next() const noexcept¶

Default getter for the next object.

Classes that inherit from LLBase should implement their own next() method to return the next object in the list with a specialized return type.

Returns:: LLBase*

inline void setNext(LLBase *n) noexcept¶: Setter for the next object.

Public Members

LLBase *next_ = nullptr¶

The pointer to the next object.

The next pointer is used to form linked lists of objects. Classes used in a linked list must solely inherit from this class. Other code in mqt-core relies on the assumption that all objects in a linked list are of the same type.

class MemoryManager¶

#include <MemoryManager.hpp>

A memory manager for objects of the same type that inherit from LLBase.

The class manages a collection of objects. The objects are stored in contiguous chunks of memory. The manager supports reclaiming objects that are no longer in use. This is done by maintaining a linked list of available objects. When an object is no longer in use, it is added to the list. When a new object is requested, the first object from the list is returned. If the list is empty, an object from the current chunk is returned. If the current chunk is full, a new chunk is allocated. The size of chunks grows exponentially according to a growth factor.

Note

The main purpose of this class is to reduce the number of memory allocations and deallocations. This is achieved by allocating a large number of objects at once and reusing them. This is especially useful for objects that are frequently created and destroyed, such as decision diagram nodes, edge weights, etc.

Public Functions

~MemoryManager() = default¶: default destructor

template<class T> inline T *get()¶

Get an entry from the manager.

If an entry is available for reuse, it is returned. Otherwise, an entry from the pre-allocated chunks is returned. If no entry is available, a new chunk is allocated.

Template Parameters:: T – The type of the entry.
Returns:: A pointer to an entry.

void returnEntry(LLBase &entry) noexcept¶

Return an entry to the manager.

The entry is added to the list of available entries. The entry must not be used after it has been returned to the manager.

Parameters:: entry – A reference to an entry that is no longer in use.

void reset(bool resizeToTotal = false) noexcept¶

Reset the manager.

Drops all but the first chunk. If resizeToTotal is set to true, the first chunk is resized to the total number of entries. This increases memory locality and reduces the number of allocations when the manager is used again. However, it might also require a huge contiguous block of memory to be allocated.

Parameters:: resizeToTotal – If set to true, the first chunk is resized to the total number of entries.

inline const auto &getStats() const noexcept¶: Get a reference to the statistics.

Public Static Functions

template<class T> static inline MemoryManager create(const std::size_t initialAllocationSize = INITIAL_ALLOCATION_SIZE)¶

Construct a new MemoryManager object for objects of type T.

Parameters:: initialAllocationSize – The initial number of entries to allocate
Template Parameters:: T – The type of the entries

Public Static Attributes

static constexpr std::size_t INITIAL_ALLOCATION_SIZE = 2048U¶

The number of initially allocated entries.

The number of initially allocated entries is the number of entries that are allocated as a chunk when the manager is created. Increasing this number reduces the number of allocations, but increases the memory usage.

static constexpr double GROWTH_FACTOR = 2U¶

The growth factor for table entry allocation.

The growth factor is used to determine the number of entries that are allocated when the manager runs out of entries. Per default, the number of entries is doubled. Increasing this number reduces the number of memory allocations, but increases the memory usage.

struct MemoryManagerStatistics : public dd::Statistics ¶

#include <MemoryManagerStatistics.hpp>

A utility class for storing statistics of a memory manager.

Public Functions

inline explicit MemoryManagerStatistics(const std::size_t entrySize)¶

Construct a new Memory Manager Statistics object.

Parameters:: entrySize – The size of a single entry

std::size_t getNumAvailableFromChunks() const noexcept¶: Get the number of available entries from memory chunks.

std::size_t getTotalNumAvailable() const noexcept¶: Get the total number of available entries.

double getUsageRatio() const noexcept¶: Get an estimate for ratio of used memory.

double getAllocatedMemoryMiB() const noexcept¶: Get an estimate of the total allocated memory in MiB.

double getUsedMemoryMiB() const noexcept¶: Get an estimate of the total used memory in MiB.

double getPeakUsedMemoryMiB() const noexcept¶: Get an estimate for the peak used memory in MiB.

void trackUsedEntries(std::size_t numEntries = 1U) noexcept¶: Track newly used entries (from chunks)

void trackReusedEntries(std::size_t numEntries = 1U) noexcept¶: Track reused entries (from available list)

void trackReturnedEntry() noexcept¶: Track a new available entry for reuse.

virtual void reset() noexcept override¶: Reset all statistics (except for the peak values)

virtual nlohmann::json json() const override¶: Get a JSON representation of the statistics.

Public Members

std::size_t entrySize_¶: The size of a single entry.

std::size_t numAllocations = 0U¶: The number of allocations performed.

std::size_t numAllocated = 0U¶: The number of allocated entries.

std::size_t numUsed = 0U¶: The number of entries currently in use.

std::size_t numAvailableForReuse = 0U¶: The number of entries currently available for reuse.

std::size_t peakNumUsed = 0U¶: The peak number of entries in use.

std::size_t peakNumAvailableForReuse = 0U¶: The peak number of entries available for reuse.

struct mNode : public dd::NodeBase ¶

#include <Node.hpp>

A matrix DD node.

Data Layout (8)|(2|2|4)|(24|24|24|24) = 112B

Public Functions

inline mNode *next() const noexcept¶: Getter for the next object.

Public Static Functions

static inline constexpr mNode *getTerminal() noexcept¶: Getter for the terminal object.

struct NodeBase : public dd::LLBase ¶

#include <Node.hpp>

Base class for all DD nodes.

This class is used to store common information for all DD nodes. The flags makes the implicit padding explicit and can be used for storing node properties. Data Layout (8)|(2|2|4) = 16B.

Subclassed by dd::dNode, dd::mNode, dd::vNode

Public Functions

inline bool isMarked() const noexcept¶: Whether a node is marked as used.

inline void mark() noexcept¶: Mark the node as used.

inline void unmark() noexcept¶: Unmark the node.

inline NodeBase *next() const noexcept¶: Getter for the next object.

Public Members

Qubit v = {}¶: Variable index.

std::uint16_t flags = 0¶

Flags for node properties.

Not required for all node types, but padding is required either way.

0b10000 = mark flag used for mark-and-sweep garbage collection, 0b1000 = marks a reduced dm node, 0b100 = marks a dm (tmp flag), 0b10 = mark first path edge (tmp flag), 0b1 = mark path is conjugated (tmp flag)

Public Static Functions

static inline bool isTerminal(const NodeBase *p) noexcept¶

Check if a node is terminal.

Generally, a node is terminal if it is nullptr. Some nodes (dNode) encode additional information in the least significant bits of the pointer. These bits are masked out before checking for terminal nodes.

Parameters:: p – The node to check
Returns:: true if the node is terminal, false otherwise.

Public Static Attributes

static constexpr std::uint16_t MARK_FLAG = 0b10000U¶: Mark flag used for mark-and-sweep garbage collection.

class Package¶

#include <Package.hpp>

The DD package class.

This is the main class of the decision diagram module in MQT Core. It contains the core functionality for working with quantum decision diagrams. Specifically, it provides the means to

represent quantum states as decision diagrams,
represent quantum operations as decision diagrams,
multiply decision diagrams (MxV, MxM, etc.),
perform collapsing measurements on decision diagrams,
sample from decision diagrams.

To this end, it maintains several internal data structures, such as unique tables, compute tables, and memory managers, which are used to manage the nodes of the decision diagrams.

Public Functions

explicit Package(std::size_t nq = DEFAULT_QUBITS, const DDPackageConfig &config = DDPackageConfig{})¶

Construct a new DD Package instance.

Parameters:

nq – The maximum number of qubits to allocate memory for. This can always be extended later using resize.
config – The configuration of the package

void resize(std::size_t nq)¶

Resize the package to a new number of qubits.

This method will resize all the unique tables appropriately so that they can handle the new number of qubits.

Parameters:: nq – The new number of qubits

void reset()¶: Reset package state.

inline auto qubits() const¶: Get the number of qubits.

template<class T> inline auto &getMemoryManager()¶

Get the memory manager for a given type.

Template Parameters:: T – The type to get the manager for
Returns:: A reference to the manager

void resetMemoryManagers(bool resizeToTotal = false)¶

Reset all memory managers.

resizeToTotal If set to true, each manager allocates one chunk of memory as large as all chunks combined before the reset.

See also

MemoryManager::reset

template<class T> inline auto &getUniqueTable()¶

Get the unique table for a given type.

Template Parameters:: T – The type to get the unique table for
Returns:: A reference to the unique table

void clearUniqueTables()¶

Clear all unique tables.

See also

UniqueTable::clear

See also

RealNumberUniqueTable::clear

template<class Node> inline void incRef(const Edge<Node> &e) noexcept¶

Add the DD to a tracking hashset and update its reference count.

Template Parameters:: Node – The node type of the edge.
Parameters:: e – The edge to increase the reference count of.

template<class Node> inline void decRef(const Edge<Node> &e)¶

Decrease the DD’s reference count and remove it from the tracking hashset if the count hits zero.

Template Parameters:: Node – The node type of the edge.
Parameters:: e – The edge to decrease the reference count of.
Throws:: std::invalid_argument – If the edge is not part of the tracking hashset.

bool garbageCollect(bool force = false)¶

Trigger garbage collection on all unique tables.

Mark-and-sweep algorithm: First, mark all nodes and complex numbers tracked in roots. Second, remove any unmarked nodes and numbers from the respective unique tables. Lastly, unmark all nodes and complex numbers again.

Note

By default, garbage collection is only triggered if the unique tables report that a collection might be necessary.

Parameters:: force – Force garbage collect, regardless of whether any table reports that it may need collecting.
Returns:: Whether at least one vector, matrix, density-matrix node, or any complex number was reclaimed.

ActiveCounts computeActiveCounts()¶: Compute the active number of nodes and numbers.

Note

This traverses every currently tracked DD twice.

dEdge makeZeroDensityOperator(std::size_t n)¶

Construct the all-zero density operator \(|0...0\rangle\langle0...0|\).

Vector nodes, edges and quantum states

Parameters:: n – The number of qubits
Returns:: A decision diagram for the all-zero density operator

mEdge makeGateDD(const GateMatrix &mat, qc::Qubit target)¶

Construct the DD for a single-qubit gate.

Matrix nodes, edges and quantum gates

Parameters:

mat – The matrix representation of the gate
target – The target qubit

Returns:

A decision diagram for the gate

mEdge makeGateDD(const GateMatrix &mat, const qc::Control &control, qc::Qubit target)¶

Construct the DD for a single-qubit controlled gate.

Parameters:

mat – The matrix representation of the gate
control – The control qubit
target – The target qubit

Returns:

A decision diagram for the gate

mEdge makeGateDD(const GateMatrix &mat, const qc::Controls &controls, qc::Qubit target)¶

Construct the DD for a multi-controlled single-qubit gate.

Parameters:

mat – The matrix representation of the gate
controls – The control qubits
target – The target qubit

Returns:

A decision diagram for the gate

mEdge makeTwoQubitGateDD(const TwoQubitGateMatrix &mat, qc::Qubit target0, qc::Qubit target1)¶

Creates the DD for a two-qubit gate.

Parameters:

mat – Matrix representation of the gate
target0 – First target qubit
target1 – Second target qubit

Throws:

std::runtime_error – if the number of qubits is larger than the package configuration

Returns:

DD representing the gate

mEdge makeTwoQubitGateDD(const TwoQubitGateMatrix &mat, const qc::Control &control, qc::Qubit target0, qc::Qubit target1)¶

Creates the DD for a two-qubit gate.

Parameters:

mat – Matrix representation of the gate
control – Control qubit of the two-qubit gate
target0 – First target qubit
target1 – Second target qubit

Throws:

std::runtime_error – if the number of qubits is larger than the package configuration

Returns:

DD representing the gate

mEdge makeTwoQubitGateDD(const TwoQubitGateMatrix &mat, const qc::Controls &controls, qc::Qubit target0, qc::Qubit target1)¶

Creates the DD for a two-qubit gate.

Parameters:

mat – Matrix representation of the gate
controls – Control qubits of the two-qubit gate
target0 – First target qubit
target1 – Second target qubit

Throws:

std::runtime_error – if the number of qubits is larger than the package configuration

Returns:

DD representing the gate

mEdge makeDDFromMatrix(const CMat &matrix)¶

Converts a given matrix to a decision diagram.

Parameters:: matrix – A complex matrix to convert to a DD.
Throws:: std::invalid_argument – If the given matrix is not square or its length is not a power of two.
Returns:: A decision diagram representing the matrix.

template<class Node, template<class> class EdgeType> inline EdgeType<Node> makeDDNode(const Qubit var, const std::array<EdgeType<Node>, std::tuple_size_v<decltype(Node::e)>> &edges, const bool generateDensityMatrix = false)¶

Create a normalized DD node and return an edge pointing to it.

The node is not recreated if it already exists. This function retrieves a node from the memory manager, sets its variable, and normalizes the edges. If the node resembles the identity, it is skipped. The function then looks up the node in the unique table and returns an edge pointing to it.

Template Parameters:

Node – The type of the node.
EdgeType – The type of the edge.

Parameters:

var – The variable associated with the node.
edges – The edges of the node.
generateDensityMatrix – Flag to indicate if a density matrix node should be generated.

Returns:

An edge pointing to the normalized DD node.

template<class Node> inline Edge<Node> deleteEdge(const Edge<Node> &e, const Qubit v, const std::size_t edgeIdx)¶

Delete an edge from the decision diagram.

Template Parameters:

Node – The type of the node.

Parameters:

e – The edge to delete.
v – The variable associated with the edge.
edgeIdx – The index of the edge to delete.

Returns:

The modified edge after deletion.

template<class Node> inline Edge<Node> deleteEdge(const Edge<Node> &e, const Qubit v, const std::size_t edgeIdx, std::unordered_map<Node*, Edge<Node>> &nodes)¶

Helper function to delete an edge from the decision diagram.

Template Parameters:

Node – The type of the node.

Parameters:

e – The edge to delete.
v – The variable associated with the edge.
edgeIdx – The index of the edge to delete.
nodes – A map to keep track of processed nodes.

Returns:

The modified edge after deletion.

void clearComputeTables()¶

Clear all compute tables.

Compute table definitions

This method clears all entries in the compute tables used for various operations. It resets the state of the compute tables, making them ready for new computations.

std::string measureAll(vEdge &rootEdge, bool collapse, std::mt19937_64 &mt, fp epsilon = 0.001)¶

Measure all qubits in the given decision diagram.

Measurements from state decision diagrams

This function measures all qubits in the decision diagram represented by rootEdge. It checks for numerical instabilities and collapses the state if requested.

Parameters:

rootEdge – The decision diagram to measure.
collapse – If true, the state is collapsed after measurement.
mt – A random number generator.
epsilon – The tolerance for numerical instabilities.

Throws:

std::runtime_error – If numerical instabilities are detected or if probabilities do not sum to 1.

Returns:

A string representing the measurement result.

char measureOneCollapsing(vEdge &rootEdge, Qubit index, std::mt19937_64 &mt, fp epsilon = 0.001)¶

Measures the qubit with the given index in the given state vector decision diagram. Collapses the state according to the measurement result.

Parameters:

rootEdge – the root edge of the state vector decision diagram
index – the index of the qubit to be measured
mt – the random number generator
epsilon – the numerical precision used for checking the normalization of the state vector decision diagram

Throws:

std::runtime_error – if a numerical instability is detected during the measurement.

Returns:

the measurement result (‘0’ or ‘1’)

void performCollapsingMeasurement(vEdge &rootEdge, Qubit index, fp probability, bool measureZero)¶

Performs a specific measurement on the given state vector decision diagram. Collapses the state according to the measurement result.

Parameters:

rootEdge – the root edge of the state vector decision diagram
index – the index of the qubit to be measured
probability – the probability of the measurement result (required for normalization)
measureZero – whether or not to measure ‘0’ (otherwise ‘1’ is measured)

template<class Node> inline auto &getAddComputeTable()¶

Get the compute table for addition operations.

Template Parameters:: Node – The type of the node.
Returns:: A reference to the appropriate compute table for the given node type.

template<class Node> inline auto &getAddMagnitudesComputeTable()¶

Get the compute table for addition operations with magnitudes.

Template Parameters:: Node – The type of the node.
Returns:: A reference to the appropriate compute table for the given node type.

template<class Node> inline Edge<Node> add(const Edge<Node> &x, const Edge<Node> &y)¶

Add two decision diagrams.

This function performs the addition of two decision diagrams (DDs). It uses a compute table to cache intermediate results and avoid redundant computations. The addition is conducted recursively, where the function traverses the nodes of the DDs, adds corresponding edges, and normalizes the resulting edges. If the nodes are terminal, their weights are directly added. The function ensures that the resulting DD is properly normalized and stored in the unique table to maintain the canonical form.

Template Parameters:

Node – The type of the node.

Parameters:

x – The first DD.
y – The second DD.

Returns:

The resulting DD after addition.

template<class Node> inline CachedEdge<Node> add2(const CachedEdge<Node> &x, const CachedEdge<Node> &y, const Qubit var)¶

Internal function to add two decision diagrams.

This function is used internally to add two decision diagrams (DDs) of type Node. It is not intended to be called directly.

Template Parameters:

Node – The type of the node.

Parameters:

x – The first DD.
y – The second DD.
var – The variable associated with the current level of recursion.

Returns:

The resulting DD after addition.

template<class Node> inline CachedEdge<Node> addMagnitudes(const CachedEdge<Node> &x, const CachedEdge<Node> &y, const Qubit var)¶

Compute the element-wise magnitude sum of two vectors or matrices.

For two vectors (or matrices) x and y, this function returns a result r such that for each index i: \( r[i] = \sqrt{|x[i]|^2 + |y[i]|^2} \)

Parameters:

x – DD representation of the first operand.
y – DD representation of the second operand.
var – Number of qubits in the DD.

Returns:

DD representing the result.

vEdge conjugate(const vEdge &a)¶

Conjugates a given decision diagram edge.

Parameters:: a – The decision diagram edge to conjugate.
Returns:: The conjugated decision diagram edge.

vCachedEdge conjugateRec(const vEdge &a)¶

Recursively conjugates a given decision diagram edge.

Parameters:: a – The decision diagram edge to conjugate.
Returns:: The conjugated decision diagram edge.

mEdge conjugateTranspose(const mEdge &a)¶

Computes the conjugate transpose of a given matrix edge.

Parameters:: a – The matrix edge to conjugate transpose.
Returns:: The conjugated transposed matrix edge.

mCachedEdge conjugateTransposeRec(const mEdge &a)¶

Recursively computes the conjugate transpose of a given matrix edge.

Parameters:: a – The matrix edge to conjugate transpose.
Returns:: The conjugated transposed matrix edge.

template<class RightOperandNode> inline auto &getMultiplicationComputeTable()¶

Get the compute table for multiplication operations.

Template Parameters:: RightOperandNode – The type of the right operand node.
Returns:: A reference to the appropriate compute table for the given node type.

VectorDD applyOperation(const MatrixDD &operation, const VectorDD &e)¶

Applies a matrix operation to a vector.

The reference count of the input vector is decreased, while the reference count of the result is increased. After the operation, garbage collection is triggered.

Parameters:

operation – Matrix operation to apply
e – Vector to apply the operation to

Returns:

The appropriately reference-counted result.

MatrixDD applyOperation(const MatrixDD &operation, const MatrixDD &e, bool applyFromLeft = true)¶

Applies a matrix operation to a matrix.

The reference count of the input matrix is decreased, while the reference count of the result is increased. After the operation, garbage collection is triggered.

Parameters:

operation – Matrix operation to apply
e – Matrix to apply the operation to
applyFromLeft – Flag to indicate if the operation should be applied from the left (default) or right.

Returns:

The appropriately reference-counted result.

template<class LeftOperandNode, class RightOperandNode> inline Edge<RightOperandNode> multiply(const Edge<LeftOperandNode> &x, const Edge<RightOperandNode> &y, const bool generateDensityMatrix = false)¶

Multiplies two decision diagrams.

This function performs the multiplication of two decision diagrams (DDs). It uses a compute table to cache intermediate results and avoid redundant computations. The multiplication is conducted recursively, where the function traverses the nodes of the DDs, multiplies corresponding edges, and normalizes the resulting edges. If the nodes are terminal, their weights are directly multiplied. The function ensures that the resulting DD is properly normalized and stored in the unique table to maintain the canonical form.

Template Parameters:

LeftOperandNode – The type of the left operand node.
RightOperandNode – The type of the right operand node.

Parameters:

x – The left operand decision diagram.
y – The right operand decision diagram.
generateDensityMatrix – Flag to indicate if a density matrix node should be generated.

Returns:

The resulting decision diagram after multiplication.

ComplexValue innerProduct(const vEdge &x, const vEdge &y)¶

Calculates the inner product of two vector decision diagrams.

Parameters:

x – A vector DD representing a quantum state.
y – A vector DD representing a quantum state.

Returns:

A complex number representing the scalar product of the DDs.

fp fidelity(const vEdge &x, const vEdge &y)¶

Calculates the fidelity between two vector decision diagrams.

Parameters:

x – A vector DD representing a quantum state.
y – A vector DD representing a quantum state.

Returns:

The fidelity between the two quantum states.

fp expectationValue(const mEdge &x, const vEdge &y)¶

Calculates the expectation value of an operator with respect to a quantum state.

This function calls the multiply() function to apply the operator to the quantum state, then calls innerProduct() to calculate the overlap between the original state and the applied state (i.e., <Psi| Psi’> = <Psi| (Op|Psi>)). It also calls the garbageCollect() function to free up any unused memory.

Parameters:

x – A matrix decision diagram (DD) representing the operator.
y – A vector decision diagram (DD) representing the quantum state.

Throws:

std::runtime_error – if the edges are not on the same level or if the expectation value is non-real.

Returns:

A floating-point value representing the expectation value of the operator with respect to the quantum state.

template<class Node> inline auto &getKroneckerComputeTable()¶

Get the compute table for Kronecker product operations.

Template Parameters:: Node – The type of the node.
Returns:: A reference to the appropriate compute table for the given node type.

template<class Node> inline Edge<Node> kronecker(const Edge<Node> &x, const Edge<Node> &y, const std::size_t yNumQubits, const bool incIdx = true)¶

Computes the Kronecker product of two decision diagrams.

Template Parameters:

Node – The type of the node.

Parameters:

x – The first decision diagram.
y – The second decision diagram.
yNumQubits – The number of qubits in the second decision diagram.
incIdx – Whether to increment the index of the nodes in the second decision diagram.

Throws:

std::invalid_argument – if the node type is dNode (density matrices).

Returns:

The resulting decision diagram after computing the Kronecker product.

template<class Node> inline auto &getTraceComputeTable()¶

Get the compute table for trace operations.

Template Parameters:: Node – The type of the node.
Returns:: A reference to the appropriate compute table for the given node type.

mEdge partialTrace(const mEdge &a, const std::vector<bool> &eliminate)¶

Computes the partial trace of a matrix decision diagram.

Parameters:

a – The matrix decision diagram.
eliminate – A vector of booleans indicating which qubits to trace out.

Returns:

The resulting matrix decision diagram after the partial trace.

template<class Node> inline ComplexValue trace(const Edge<Node> &a, const std::size_t numQubits)¶

Computes the trace of a decision diagram.

Template Parameters:

Node – The type of the node.

Parameters:

a – The decision diagram.
numQubits – The number of qubits in the decision diagram.

Returns:

The trace of the decision diagram as a complex value.

bool isCloseToIdentity(const mEdge &m, fp tol = 1e-10, const std::vector<bool> &garbage = {}, bool checkCloseToOne = true) const¶

Checks if a given matrix is close to the identity matrix.

This function checks if a given matrix is close to the identity matrix, while ignoring any potential garbage qubits and ignoring the diagonal weights if checkCloseToOne is set to false.

Parameters:

m – An mEdge that represents the DD of the matrix.
tol – The accepted tolerance for the edge weights of the DD.
garbage – A vector of boolean values that defines which qubits are considered garbage qubits. If it’s empty, then no qubit is considered to be a garbage qubit.
checkCloseToOne – If false, the function only checks if the matrix is close to a diagonal matrix.

mEdge reduceAncillae(mEdge e, const std::vector<bool> &ancillary, bool regular = true)¶

Reduces the decision diagram by handling ancillary qubits.

Ancillary and garbage reduction

This function modifies the decision diagram to account for ancillary qubits by:

Early returning if there are no ancillary qubits or if the edge is zero
Special handling for identity matrices by creating appropriate zero nodes
Finding the lowest ancillary qubit as a starting point
Recursively reducing nodes starting from the lowest ancillary qubit
Adding zero nodes for any remaining higher ancillary qubits

The function maintains proper reference counting by incrementing the reference count of the result and decrementing the reference count of the input edge.

Parameters:

e – The matrix decision diagram edge to be reduced.
ancillary – A boolean vector indicating which qubits are ancillary (true) or not (false).
regular – Flag indicating whether to perform regular (true) or inverse (false) reduction.

Returns:

The reduced matrix decision diagram edge.

vEdge reduceGarbage(vEdge &e, const std::vector<bool> &garbage, bool normalizeWeights = false)¶

Reduces the given decision diagram by summing entries for garbage qubits.

For each garbage qubit q, this function sums all the entries for q = 0 and q = 1, setting the entry for q = 0 to the sum and the entry for q = 1 to zero. To ensure that the probabilities of the resulting state are the sum of the probabilities of the initial state, the function computes sqrt(|a|^2 + |b|^2) for two entries a and b.

Parameters:

e – DD representation of the matrix/vector.
garbage – Vector that describes which qubits are garbage and which ones are not. If garbage[i] = true, then qubit q_i is considered garbage.
normalizeWeights – By default set to false. If set to true, the function changes all weights in the DD to their magnitude, also for non-garbage qubits. This is used for checking partial equivalence of circuits. For partial equivalence, only the measurement probabilities are considered, so we need to consider only the magnitudes of each entry.

Returns:

DD representing the reduced matrix/vector.

mEdge reduceGarbage(const mEdge &e, const std::vector<bool> &garbage, bool regular = true, bool normalizeWeights = false)¶

Reduces garbage qubits in a matrix decision diagram.

For each garbage qubit q, this function sums all the entries for q=0 and q=1, setting the entry for q=0 to the sum and the entry for q=1 to zero. To maintain proper probabilities, the function computes sqrt(|a|^2 + |b|^2) for two entries a and b. The function handles special cases like zero terminals and identity matrices separately and maintains proper reference counting throughout the reduction process.

Parameters:

e – The matrix decision diagram edge to be reduced.
garbage – A boolean vector indicating which qubits are garbage (true) or not (false).
regular – Flag indicating whether to apply regular (true) or inverse (false) reduction. In regular mode, garbage entries are summed in the first two components, in inverse mode, they are summed in the first and third components.
normalizeWeights – Flag indicating whether to normalize weights to their magnitudes. When true, all weights in the DD are changed to their magnitude, also for non-garbage qubits. This is used for checking partial equivalence where only measurement probabilities matter.

Returns:

The reduced matrix decision diagram edge.

template<class Node> inline Edge<Node> transfer(Edge<Node> &original)¶

transfers a decision diagram from another package to this package

Vector and matrix extraction from DDs

template<class Node, class Edge = Edge<Node>, std::size_t N = std::tuple_size_v<decltype(Node::e)>> inline Edge deserialize(std::istream &is, const bool readBinary = false)¶: Deserialization Note: do not rely on the binary format being portable across different architectures/platforms

Public Members

MemoryManager vMemoryManager = {MemoryManager::create<vNode>(config_.utVecInitialAllocationSize)}¶: The memory manager for vector nodes.

MemoryManager mMemoryManager = {MemoryManager::create<mNode>(config_.utMatInitialAllocationSize)}¶: The memory manager for matrix nodes.

MemoryManager dMemoryManager = {MemoryManager::create<dNode>(config_.utDmInitialAllocationSize)}¶: The memory manager for density matrix nodes.

MemoryManager cMemoryManager = {MemoryManager::create<RealNumber>()}¶: The memory manager for complex numbers.

Note

The real and imaginary part of complex numbers are treated separately. Hence, it suffices for the manager to only manage real numbers.

UniqueTable vUniqueTable = {vMemoryManager, {0U, config_.utVecNumBucket}}¶: The unique table used for vector nodes.

UniqueTable mUniqueTable = {mMemoryManager, {0U, config_.utMatNumBucket}}¶: The unique table used for matrix nodes.

UniqueTable dUniqueTable = {dMemoryManager, {0U, config_.utDmNumBucket}}¶: The unique table used for density matrix nodes.

RealNumberUniqueTable cUniqueTable = {cMemoryManager}¶

The unique table used for complex numbers.

See also

RealNumberUniqueTable

Note

The table actually only stores real numbers in the interval [0, 1], but is used to manages all complex numbers throughout the package.

ComputeTable<vCachedEdge, vCachedEdge, vCachedEdge> vectorAdd{config_.ctVecAddNumBucket}¶: Addition

UnaryComputeTable<vNode*, vCachedEdge> conjugateVector{config_.ctVecConjNumBucket}¶: Vector conjugation

UnaryComputeTable<mNode*, mCachedEdge> conjugateMatrixTranspose{config_.ctMatConjTransNumBucket}¶: Matrix (conjugate) transpose

ComputeTable<mNode*, vNode*, vCachedEdge> matrixVectorMultiplication{config_.ctMatVecMultNumBucket}¶: Multiplication

ComputeTable<vNode*, vNode*, vCachedEdge> vectorInnerProduct{config_.ctVecInnerProdNumBucket}¶: Inner product, fidelity, expectation value

ComputeTable<vNode*, vNode*, vCachedEdge> vectorKronecker{config_.ctVecKronNumBucket}¶: Kronecker/tensor product

UnaryComputeTable<dNode*, dCachedEdge> densityTrace{config_.ctDmTraceNumBucket}¶: (Partial) trace

StochasticNoiseOperationTable<mEdge> stochasticNoiseOperationCache{nqubits, config_.stochasticCacheOps}¶: Noise Operations

Public Static Functions

static std::pair<fp, fp> determineMeasurementProbabilities(const vEdge &rootEdge, Qubit index)¶

Determine the measurement probabilities for a given qubit index.

This function calculates the probabilities of measuring 0 and 1 for a given qubit index in the decision diagram. It uses a breadth-first search to traverse the decision diagram and accumulate the measurement probabilities. The function maintains a map of measurement probabilities for each node and a set of visited nodes to avoid redundant calculations. It also uses a queue to process nodes level by level.

Parameters:

rootEdge – The root edge of the decision diagram.
index – The qubit index to determine the measurement probabilities for.

Returns:

A pair of floating-point values representing the probabilities of measuring 0 and 1, respectively.

static fp fidelityOfMeasurementOutcomes(const vEdge &e, const SparsePVec &probs, const qc::Permutation &permutation = {})¶

Calculates the fidelity between a vector decision diagram and a sparse probability vector.

This function computes the fidelity between a quantum state represented by a vector decision diagram and a sparse probability vector. The optional permutation of qubits can be provided to match the qubit ordering.

Parameters:

e – The root edge of the decision diagram.
probs – A map of probabilities for each measurement outcome.
permutation – An optional permutation of qubits.

Returns:

The fidelity of the measurement outcomes.

static mEdge makeIdent()¶

Create identity DD represented by the one-terminal.

Identity matrices

Public Static Attributes

static constexpr std::size_t MAX_POSSIBLE_QUBITS = static_cast<std::size_t>(std::numeric_limits<Qubit>::max()) + 1U¶: Construction, destruction, information, and reset

struct ActiveCounts¶

struct PairHash¶

struct RealNumber : public dd::LLBase ¶

#include <RealNumber.hpp>

A struct for representing real numbers as part of the DD package.

Consists of a floating point number (the value) and a next pointer (used for chaining entries). Numbers are marked for garbage collection via the second least significant bit of pointers referencing them.

Note

Due to the way the sign of the value is encoded, special care has to be taken when accessing the value. The static functions in this struct provide safe access to the value of a RealNumber* pointer.

Public Functions

RealNumber *next() const noexcept¶: Getter for the next object.

Public Members

fp value = {}¶

The value of the number.

The value of the number is a floating point number. The sign of the value is encoded in the least significant bit of the memory address of the number. As a consequence, values stored here are always non-negative. The sign of the value as well as the value itself can be accessed using the static functions of this struct.

Public Static Functions

static constexpr bool exactlyZero(const RealNumber *e) noexcept¶

Check whether the number points to the zero number.

Parameters:: e – The number to check.
Returns:: Whether the number points to zero.

static constexpr bool exactlyOne(const RealNumber *e) noexcept¶

Check whether the number points to the one number.

Parameters:: e – The number to check.
Returns:: Whether the number points to one.

static constexpr bool exactlySqrt2over2(const RealNumber *e) noexcept¶

Check whether the number points to the sqrt(2)/2 = 1/sqrt(2) number.

Parameters:: e – The number to check.
Returns:: Whether the number points to negative one.

static fp val(const RealNumber *e) noexcept¶

Get the value of the number.

Note

This function accounts for the sign of the number embedded in the memory address of the number.

Parameters:: e – The number to get the value for.
Returns:: The value of the number.

static bool approximatelyEquals(fp left, fp right) noexcept¶

Check whether two floating point numbers are approximately equal.

This function checks whether two floating point numbers are approximately equal. The two numbers are considered approximately equal if the absolute difference between them is smaller than a small value (TOLERANCE). This function is used to compare floating point numbers stored in the table.

Parameters:

left – The first floating point number.
right – The second floating point number.

Returns:

Whether the two floating point numbers are approximately equal.

static bool approximatelyEquals(const RealNumber *left, const RealNumber *right) noexcept¶

Check whether two numbers are approximately equal.

This function checks whether two numbers are approximately equal. Two numbers are considered approximately equal if they point to the same number or if the values of the numbers are approximately equal.

See also

approximatelyEquals(fp, fp)

Parameters:

left – The first number.
right – The second number.

Returns:

Whether the two numbers are approximately equal.

static bool approximatelyZero(fp e) noexcept¶

Check whether a floating point number is approximately zero.

Parameters:: e – The floating point number to check.
Returns:: Whether the floating point number is approximately zero.

static bool approximatelyZero(const RealNumber *e) noexcept¶

Check whether a number is approximately zero.

See also

approximatelyZero(fp)

Parameters:: e – The number to check.
Returns:: Whether the number is approximately zero.

static void writeBinary(const RealNumber *e, std::ostream &os)¶

Write a binary representation of the number to a stream.

Parameters:

e – The number to write.
os – The stream to write to.

static void writeBinary(fp num, std::ostream &os)¶

Write a binary representation of a floating point number to a.

Parameters:

num – The number to write.
os – The stream to write to.

static void readBinary(fp &num, std::istream &is)¶

Read a binary representation of a number from a stream.

Parameters:

num – The number to read into.
is – The stream to read from.

static RealNumber *getAlignedPointer(const RealNumber *e) noexcept¶

Get an aligned pointer to the number.

Since the least significant bit of the memory address of the number is used to encode the sign of the value, the pointer to the number might not be aligned. This function returns an aligned pointer to the number.

Parameters:: e – The number to get the aligned pointer for.
Returns:: An aligned pointer to the number.

static RealNumber *getNegativePointer(const RealNumber *e) noexcept¶

Get a pointer to the number with a negative sign.

Since the least significant bit of the memory address of the number is used to encode the sign of the value, this function just sets the least significant bit of the memory address of the number to 1.

Parameters:: e – The number to get the negative pointer for.
Returns:: A negative pointer to the number.

static RealNumber *flipPointerSign(const RealNumber *e) noexcept¶

Flip the sign of the number pointer.

Note

This function does not change the sign of the value of the number. It rather changes the sign of the pointer to the number.

Note

We do not consider negative zero here, since it is not used in the DD package. There only exists one zero number, which is positive.

Parameters:: e – The number to flip the sign of.
Returns:: The number with the sign flipped.

static void mark(RealNumber *e) noexcept¶

Mark e for garbage collection.

Sets the 2nd least significant bit of the next_ pointer.

Parameters:: e – The number to mark.

static void unmark(RealNumber *e) noexcept¶

Unmark e after garbage collection.

Unsets the 2nd least significant bit of the next_ pointer.

Parameters:: e – The number to unmark.

static void immortalize(RealNumber *e) noexcept¶

Immortalize e.

Sets the 3rd least significant bit of the next_ pointer.

Parameters:: e – The number to immortalize.

static bool isNegativePointer(const RealNumber *e) noexcept¶

Check whether the number is flagged as negative.

Parameters:: e – The number to check.
Returns:: Whether the number is negative.

static bool isMarked(const RealNumber *e) noexcept¶

Check whether the number is flagged as marked.

Parameters:: e – The number to check.
Returns:: Whether the number is marked.

static bool isImmortal(const RealNumber *e) noexcept¶

Check whether the number is flagged as immortal.

Parameters:: e – The number to check.
Returns:: Whether the number is immortal.

Public Static Attributes

static fp eps = std::numeric_limits<fp>::epsilon() * 1024¶: numerical tolerance to be used for floating point values

class RealNumberUniqueTable¶

#include <RealNumberUniqueTable.hpp>

A unique table for real numbers.

A hash table that stores real numbers. The hash table is implemented as an array of buckets, each of which is a linked list of entries. The hash table has a fixed number of buckets.

Note

: The implementation assumes that all values are non-negative and in the range [0, 1]. While numbers outside of this range can be stored, they will always be placed in the same bucket and will therefore cause collisions.

Public Functions

explicit RealNumberUniqueTable(MemoryManager &manager, std::size_t initialGCLim = INITIAL_GC_LIMIT)¶

The default constructor.

Parameters:

manager – The memory manager to use for allocating new numbers.
initialGCLim – The initial garbage collection limit.

inline const auto &getTable() const noexcept¶: Get a reference to the table.

inline const auto &getStats() const noexcept¶: Get a reference to the statistics.

RealNumber *lookup(fp val)¶

Lookup a number in the table.

This function is used to lookup and insert them into the table if they are not yet present. Since the table only ever stores non-negative numbers, the lookup is a three-step process. First the sign is stripped off the number and stored, then the non-negative value is looked up in the table and an aligned pointer to the respective entry is returned. Finally, If the sign of the original number was negative, the pointer is adjusted.

Parameters:: val – The floating point number to look up.
Returns:: A pointer to an entry corresponding to that number.

bool possiblyNeedsCollection() const noexcept¶

Check whether the table possibly needs garbage collection.

Returns:: Whether the number of entries in the table has reached the garbage collection limit.

std::size_t garbageCollect(bool force = false) noexcept¶

Perform garbage collection.

This function performs garbage collection. It first checks whether garbage collection is necessary. If not, it does nothing. Otherwise, it iterates over all entries in the table and removes all numbers whose pointers are unmarked. If the force flag is set, garbage collection is performed even if it is not strictly necessary. Based on how many entries are returned to the available list, the garbage collection limit is dynamically adjusted.

Parameters:: force – Whether to force garbage collection.
Returns:: The number of entries returned to the available list.

void clear() noexcept¶

Clear the table.

This function clears the table. It iterates over all entries in the table and sets them to nullptr. It also discards the available list and all but the first chunk of the allocated chunks. Also resets all counters.

void print() const¶: Print the table.

std::ostream &printBucketDistribution(std::ostream &os = std::cout)¶

Print the bucket distribution of the table.

Parameters:: os – The output stream to print to.
Returns:: The output stream.

std::size_t countMarkedEntries() const noexcept¶: Count the marked entries in the table.

Public Static Functions

static std::int64_t hash(fp val) noexcept¶

The hash function for the hash table.

The hash function for the table is a simple linear (clipped) hash function. The hash function is used to map floating point numbers to the buckets of the table.

Note

Typically, you would expect the hash to be an unsigned integer. Here, we use a signed integer because it turns out to result in fewer assembly instructions. See https://godbolt.org/z/9v4TEMfdz for a comparison.

Parameters:: val – The floating point number to hash. Must be non-negative.
Returns:: The hash value of the floating point number.

struct Statistics¶

Subclassed by dd::MemoryManagerStatistics, dd::TableStatistics

Public Functions

inline virtual void reset() noexcept¶: Reset all statistics (except for peak values)

virtual nlohmann::json json() const¶: Get a JSON representation of the statistics.

virtual std::string toString() const¶: Get a pretty-printed string representation of the statistics.

Friends

inline friend std::ostream &operator<<(std::ostream &os, const Statistics &stats)¶

Write a string representation to an output stream.

Parameters:

os – The output stream
stats – The statistics

Returns:

The output stream

class StochasticNoiseFunctionality¶

template<class Edge> class StochasticNoiseOperationTable¶

Public Functions

inline const auto &getTable() const¶: Get a reference to the table.

inline const auto &getStats() const noexcept¶: Get a reference to the statistics.

struct TableStatistics : public dd::Statistics ¶

#include <TableStatistics.hpp>

A utility class for storing statistics of a table.

Subclassed by dd::UniqueTableStatistics

Public Functions

void trackInsert() noexcept¶: Track a new insert.

virtual void reset() noexcept override¶: Reset all statistics (except for peak values)

double hitRatio() const noexcept¶

Get the hit ratio of the table.

The hit ratio is the ratio of lookups that were successful.

Returns:: The hit ratio of the table.

double colRatio() const noexcept¶

Get the collision ratio of the table.

A collision occurs when the hash function maps two different entries to the same bucket. The collision ratio is the ratio of lookups that resulted in a collision.

Returns:: The collision ratio of the table.

double loadFactor() const noexcept¶

Get the load factor of the table.

The load factor is the ratio of entries to buckets.

Returns:: The load factor of the table.

double getEntrySizeMiB() const noexcept¶: Convert the entry size to MiB.

double getMemoryMiB() const noexcept¶: Get the amount of memory required for the table in MiB.

virtual nlohmann::json json() const override¶: Get a JSON representation of the statistics.

Public Members

std::size_t entrySize = 0U¶: The size of a single entry.

std::size_t numBuckets = 0U¶: The number of buckets in the table.

std::size_t numEntries = 0U¶: The number of entries in the table.

std::size_t peakNumEntries = 0U¶: The peak number of entries in the table.

std::size_t collisions = 0U¶: The number of collisions.

std::size_t hits = 0U¶: The number of successful lookups.

std::size_t lookups = 0U¶: The number of lookups.

std::size_t inserts = 0U¶: The number of inserts.

template<class OperandType, class ResultType> class UnaryComputeTable¶

#include <UnaryComputeTable.hpp>

Data structure for caching computed results of unary operations.

Template Parameters:

OperandType – type of the operation’s operand
ResultType – type of the operation’s result

Public Functions

inline explicit UnaryComputeTable(const size_t numBuckets = DEFAULT_NUM_BUCKETS)¶: Default constructor.

inline const auto &getTable() const¶: Get a reference to the underlying table.

inline const auto &getStats() const noexcept¶: Get a reference to the statistics.

inline std::size_t hash(const OperandType &a) const¶: Compute the hash value for a given operand.

inline void insert(const OperandType &operand, const ResultType &result)¶

Insert a new entry into the compute table.

Any existing entry for the resulting hash value will be replaced.

Parameters:

operand – The operand
result – The result of the operation

inline ResultType *lookup(const OperandType &operand)¶

Look up a result in the compute table.

Parameters:: operand – The operand
Returns:: A pointer to the result if it is found, otherwise nullptr.

inline void clear()¶

Clear the compute table.

Sets all entries to invalid.

Public Static Attributes

static constexpr std::size_t DEFAULT_NUM_BUCKETS = 32768U¶: Default number of buckets for the compute table.

struct Entry¶: #include <UnaryComputeTable.hpp>

An entry in the compute table.

class UniqueTable¶

#include <UniqueTable.hpp>

Data structure for uniquely storing DD nodes.

Public Functions

UniqueTable(MemoryManager &manager, const UniqueTableConfig &config)¶

The default constructor.

The MemoryManager shall be constructed from the same type that the unique table is then used for in the lookup method.

Parameters:

manager – The memory manager to use
config – The configuration for the unique table

template<class Node> inline std::size_t hash(const Node &p) const¶

The hash function for the hash table.

The hash function just combines the hashes of the edges of the node. The hash value is masked to ensure that it is in the range [0, nBuckets - 1].

Parameters:: p – The node to hash.
Returns:: The hash value of the node.

inline const auto &getTables() const¶: Get a reference to the table.

inline const auto &getStats() const noexcept¶: Get a reference to the statistics.

const UniqueTableStatistics &getStats(std::size_t idx) const noexcept¶: Get a reference to individual statistics.

nlohmann::basic_json getStatsJson(bool includeIndividualTables = false) const¶: Get a JSON object with the statistics.

std::size_t getNumEntries() const noexcept¶: Get the total number of entries.

std::size_t countMarkedEntries() const noexcept¶: Count the number of marked entries.

bool possiblyNeedsCollection() const¶: Determine whether the table possibly requires garbage collection.

Public Static Attributes

static constexpr std::size_t INITIAL_GC_LIMIT = 131072U¶

The initial garbage collection limit.

The initial garbage collection limit is the number of entries that must be present in the table before garbage collection is triggered. Increasing this number reduces the number of garbage collections, but increases the memory usage.

struct UniqueTableConfig¶

Public Members

std::size_t nVars = 0U¶: The number of variables.

std::size_t nBuckets = 32768¶: The number of hash buckets to use (has to be a power of two)

std::size_t initialGCLimit = INITIAL_GC_LIMIT ¶: The initial garbage collection limit.

struct UniqueTableStatistics : public dd::TableStatistics ¶

#include <UniqueTableStatistics.hpp>

A class for storing statistics of a unique table.

Public Functions

virtual void reset() noexcept override¶: Reset all statistics (except for the peak values)

virtual nlohmann::json json() const override¶: Get a JSON representation of the statistics.

Public Members

std::size_t gcRuns = 0U¶: The number of garbage collection runs.

struct vNode : public dd::NodeBase ¶

#include <Node.hpp>

A vector DD node.

Data Layout (8)|(2|2|4)|(24|24) = 64B

Public Functions

inline vNode *next() const noexcept¶: Getter for the next object.

Public Static Functions

static inline constexpr vNode *getTerminal() noexcept¶: Getter for the terminal object.

namespace constants¶

Functions

constexpr bool isStaticNumber(const RealNumber *e) noexcept¶

Check whether a number is one of the static numbers.

Parameters:: e – The number to check.
Returns:: Whether the number is one of the static numbers.

Variables

MQT_CORE_DD_EXPORT RealNumber zero: The constant zero.

MQT_CORE_DD_EXPORT RealNumber one: The constant one.

MQT_CORE_DD_EXPORT RealNumber sqrt2over2: The constant sqrt(2)/2 = 1/sqrt(2).

namespace immortals¶

Immortal numbers that will never be garbage collected.

Functions

constexpr std::array<fp, 1> get()¶

constexpr std::size_t size()¶