mimiqcircuits.decomposition.rules.solovay_kitaev

Solovay-Kitaev algorithm for approximating arbitrary unitaries with Clifford+T.

The Solovay-Kitaev algorithm recursively refines an initial approximation using group commutators, achieving ε-approximation with O(log^c(1/ε)) gates where c ≈ 3.97.

References

  • Dawson & Nielsen, “The Solovay-Kitaev algorithm” (2005)

  • Kitaev, Shen, Vyalyi, “Classical and Quantum Computation” (2002)

Functions

axis_angle_to_su2(axis, theta)

Construct an SU(2) matrix from rotation axis and angle.

extract_rotation_angle(U)

Extract the rotation angle θ from an SU(2) matrix U = exp(iθ n·σ/2).

extract_rotation_axis(U)

Extract the rotation axis n from an SU(2) matrix U = exp(iθ n·σ/2).

find_nearest_in_net(U, cache)

Find the gate sequence in the ε-net that best approximates U.

find_orthogonal_axes(n)

Find two orthonormal vectors v, w perpendicular to n.

gate_to_matrix(gate)

Convert a gate to a numpy matrix.

gc_decompose(delta)

Decompose an SU(2) matrix Δ (close to identity) into V and W.

generate_epsilon_net(basis_gates[, ...])

Generate an ε-net over SU(2) using Breadth-First Search.

get_basic_gates()

Get the basic Clifford+T gates for the epsilon-net.

get_sk_cache(basis_gates[, max_depth, ...])

Get or initialize the Solovay-Kitaev lookup tables.

invert_sequence(gates)

Return the inverse of a gate sequence: (g₁ g₂ .

matrix_to_point(U)

Map an SU(2) matrix to a point in R^4 (the 3-sphere S³).

operator_norm_distance(U, V)

Compute the Frobenius norm distance ||U - V||_F.

sequence_to_matrix(gates)

Compute the unitary matrix for a gate sequence.

simplify_sequence(gates)

Simplify a gate sequence by canceling adjacent gates.

sk_approximate(U, depth, basis_gates, cache)

Approximate an SU(2) matrix using the Solovay-Kitaev algorithm.

to_su2(U)

Project a 2x2 unitary matrix to SU(2) by removing the global phase.

Classes

SKCacheEntry(net_tree, net_sequences, ...)

Cache entry for Solovay-Kitaev lookup tables.

SolovayKitaevRewrite([depth, simplify, ...])

Rewrite rule that approximates single-qubit gates with Clifford+T by Solovay-Kitaev.

class SolovayKitaevRewrite(depth=3, simplify=True, net_max_depth=10, net_max_points=50000, net_min_dist=0.02)[source]

Bases: RewriteRule

Rewrite rule that approximates single-qubit gates with Clifford+T by Solovay-Kitaev.

The rule starts from the closest entry of a precomputed table (an epsilon-net) of short sequences of H, T, T†, S, S†, X, Y and Z, and refines it depth times with group commutators. Refinements lower the error on average, not at every step, and each multiplies the length of the sequence by about 5. The approximation holds up to a global phase. For Z-rotations, GridSynthRewrite gives much shorter sequences for the same error.

Parameters:
  • depth (int) – Number of refinements, at least 0 (default 3). With 0 the closest table entry is used as it is.

  • simplify (bool) – Cancel and merge adjacent gates of the result, such as T followed by T† or two S (default True).

  • net_max_depth (int) – Longest sequence in the table (default 10).

  • net_max_points (int) – Largest number of table entries (default 50000).

  • net_min_dist (float) – Smallest distance between two table entries (default 0.02).

Raises:

ValueError – If depth is negative.

Supported Operations

  • GateRZ(λ), GateRY(θ) and GateRX(θ)

  • GateU(θ, φ, λ, γ)

Only numeric parameters are matched; symbolic ones are not.

Examples

>>> from mimiqcircuits import *
>>> # one refinement of the closest table entry
>>> rule = SolovayKitaevRewrite(depth=1)
>>> circ = rule.decompose_step(GateRZ(0.123), [0], [], [])
>>> # the result only uses Clifford+T gates
>>> {type(inst.operation) for inst in circ} <= {GateH, GateT, GateTDG, GateS, GateSDG, GateX, GateY, GateZ}
True

Note

The table is built on first use, which takes a few seconds, and is then kept for later calls with the same net_* settings.

matches(op)[source]

Check whether an operation is a numeric single-qubit rotation.

Parameters:

op (Operation) – The operation to check.

Returns:

True for a GateRX, GateRY, GateRZ or GateU with numeric parameters.

Return type:

bool

decompose_step(op, qubits, bits, zvars)[source]

Approximate a single-qubit gate with Clifford+T gates.

Parameters:
  • op (Operation) – The rotation or GateU to approximate.

  • qubits (Sequence[int]) – Qubit index the gate acts on.

  • bits (Sequence[int]) – Classical bit indices (unused).

  • zvars (Sequence[int]) – Z-variable indices (unused).

Returns:

A new Circuit with the Clifford+T approximation. It can be empty when the gate is close to the identity.

Raises:

DecompositionError – If matches() rejects op.

Return type:

Circuit