Information¶

The most popular decoder for surface codes is the Minimum-Weight Perfect Matching (MWPM) decoder. It performs near-optimal for a pauli noise model [dennis2002] on a standard toric code with a threshold of \(p_{\text{th}} = 10.3\%\), and for a phenomenological noise model (including faulty measurements) [wang2003], which includes faulty measurements, with \(p_{\text{th}} = 2.9\%\). The main idea is to approximate the error with the minimum-weight error configuration compatible with the syndrome. The minimum-weight configuration is found by constructing a fully connected graph between the nodes of the syndrome, which leads to a cubic worst-case time complexity [kolmogorov2009].

The decoder defaults to using a Python implementation of MWPM by networkx.algorithms.matching.max_weight_matching. This implementation is however quite slow. Optionally, Blossom V [kolmogorov2009], a C++ algorithm, can be used to increase the speed of the decoder. Since this software has its own license, it is not bundeled with qsurface. A script is provided to download and compile the latest release of BlossomV in get_blossomv. The interface of the C++ code and Python is taken from Fault Tolerant Simulations.

qsurface.decoders.mwpm.get_blossomv(accept=False)¶

Downloads and compiles the BlossomV algorithm, which is distributed under the following license:

License:

Copyright 2008-2009 UCL Business PLC, Author Vladimir Kolmogorov (vnk@ist.ac.at)

This software can be used for evaluation and non-commercial research purposes only. Commercial use is prohibited.
Public redistribution of the code or its derivatives is prohibited.
If you use this software for research purposes, you should cite the following paper in any resulting publication:

    Vladimir Kolmogorov. "Blossom V: A new implementation of a minimum cost perfect matching algorithm."
    In Mathematical Programming Computation (MPC), July 2009, 1(1):43-67.

For commercial use of the software not covered by this agreement, you may obtain a licence from
the copyright holders UCL Business via their licensing site: www.e-lucid.com/i/software/optimisation_software/BlossomV.html.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Simulation¶

class qsurface.decoders.mwpm.sim.Toric(code, check_compatibility=False, **kwargs)¶

Minimum-Weight Perfect Matching decoder for the toric lattice.

Parameters

args – Positional and keyword arguments are passed on to decoders._template.Sim.
kwargs – Positional and keyword arguments are passed on to decoders._template.Sim.

decode(**kwargs)¶: Decodes the surface loaded at self.code after all ancilla-qubits have been measured.

match_syndromes(syndromes, use_blossomv=False, **kwargs)¶

Decodes a list of syndromes of the same type.

A graph is constructed with the syndromes in syndromes as nodes and the distances between each of the syndromes as the edges. The distances are dependent on the boundary conditions of the code and is calculated by get_qubit_distances. A minimum-weight matching is then found by either match_networkx or match_blossomv.

Parameters

syndromes (List[AncillaQubit]) – Syndromes of the code.
use_blossomv (bool) – Use external C++ Blossom V library for minimum-weight matching. Needs to be downloaded and compiled by calling get_blossomv.

Returns

Minimum-weight matched ancilla-qubits.

Return type

list of AncillaQubit

correct_matching(syndromes, matching, **kwargs)¶: Applies the matchings as a correction to the code.

static match_networkx(edges, maxcardinality, **kwargs)¶

Finds the minimum-weight matching of a list of edges using networkx.algorithms.matching.max_weight_matching.

Parameters

edges ([[nodeA, nodeB, distance(nodeA,nodeB)],..]) – A graph defined by a list of edges.
maxcardinality (float) – See networkx.algorithms.matching.max_weight_matching.

Returns

Minimum weight matching in the form of [[nodeA, nodeB],..].

Return type

list

static match_blossomv(edges, num_nodes=0, **kwargs)¶

Finds the minimum-weight matching of a list of edges using Blossom V.

Parameters: edges ([[nodeA, nodeB, distance(nodeA,nodeB)],..]) – A graph defined by a list of edges.
Returns: Minimum weight matching in the form of [[nodeA, nodeB],..].
Return type: list

static get_qubit_distances(qubits, size)¶

Computes the distance between a list of qubits.

On a toric lattice, the shortest distance between two qubits may be one in four directions due to the periodic boundary conditions. The size parameters indicates the length in both x and y directions to find the shortest distance in all directions.

check_compatibility()¶: Checks compatibility of the decoder with the code class and loaded errors.

correct_edge(ancilla_qubit, key, **kwargs)¶

Applies a correction.

The correction is applied to the data-qubit located at ancilla_qubit.parity_qubits[key]. More specifically, the correction is applied to the Edge object corresponding to the state_type of ancilla_qubit.

Return type: AncillaQubit

static get_neighbor(ancilla_qubit, key)¶

Returns the neighboring ancilla-qubit of ancilla_qubit in the direction of key.

Return type: Tuple[AncillaQubit, Edge]

get_neighbors(ancilla_qubit, loop=False, **kwargs)¶

Returns all neighboring ancillas, including other time instances.

Parameters: loop (bool) – Include neighbors in time that are not chronologically next to each other during decoding within the same instance.

get_syndrome(find_pseudo=False)¶

Finds the syndrome of the code.

Parameters

find_pseudo (bool, optional) – If enabled, the lists of syndromes returned are not only AncillaQubit objects, but tuples of (ancilla, pseudo), where pseudo is the closest PseudoQubit in the boundary of the code.

Return type

Union[Tuple[List[AncillaQubit], List[AncillaQubit]], Tuple[List[Tuple[AncillaQubit, PseudoQubit]], List[Tuple[AncillaQubit, PseudoQubit]]]]

Returns

list – Plaquette operator syndromes.
list – Star operator syndromes.

class qsurface.decoders.mwpm.sim.Planar(code, check_compatibility=False, **kwargs)¶

Minimum-Weight Perfect Matching decoder for the planar lattice.

Additionally to all edges, virtual qubits are added to the boundary, which connect to their main qubits.Edges between all virtual qubits are added with weight zero.

decode(**kwargs)¶: Decodes the surface loaded at self.code after all ancilla-qubits have been measured.

correct_matching(syndromes, matching)¶: Applies the matchings as a correction to the code.

static get_qubit_distances(qubits, *args)¶

Computes the distance between a list of qubits.

On a planar lattice, any qubit can be paired with the boundary, which is inhabited by PseudoQubit objects. The graph of syndromes that supports minimum-weight matching algorithms must be fully connected, with each syndrome connecting additionally to its boundary pseudo-qubit, and a fully connected graph between all pseudo-qubits with weight 0.

check_compatibility()¶: Checks compatibility of the decoder with the code class and loaded errors.

correct_edge(ancilla_qubit, key, **kwargs)¶

Applies a correction.

The correction is applied to the data-qubit located at ancilla_qubit.parity_qubits[key]. More specifically, the correction is applied to the Edge object corresponding to the state_type of ancilla_qubit.

Return type: AncillaQubit

static get_neighbor(ancilla_qubit, key)¶

Returns the neighboring ancilla-qubit of ancilla_qubit in the direction of key.

Return type: Tuple[AncillaQubit, Edge]

get_neighbors(ancilla_qubit, loop=False, **kwargs)¶

Returns all neighboring ancillas, including other time instances.

Parameters: loop (bool) – Include neighbors in time that are not chronologically next to each other during decoding within the same instance.

get_syndrome(find_pseudo=False)¶

Finds the syndrome of the code.

Parameters

find_pseudo (bool, optional) – If enabled, the lists of syndromes returned are not only AncillaQubit objects, but tuples of (ancilla, pseudo), where pseudo is the closest PseudoQubit in the boundary of the code.

Return type

Union[Tuple[List[AncillaQubit], List[AncillaQubit]], Tuple[List[Tuple[AncillaQubit, PseudoQubit]], List[Tuple[AncillaQubit, PseudoQubit]]]]

Returns

list – Plaquette operator syndromes.
list – Star operator syndromes.

static match_blossomv(edges, num_nodes=0, **kwargs)¶

Finds the minimum-weight matching of a list of edges using Blossom V.

Parameters: edges ([[nodeA, nodeB, distance(nodeA,nodeB)],..]) – A graph defined by a list of edges.
Returns: Minimum weight matching in the form of [[nodeA, nodeB],..].
Return type: list

static match_networkx(edges, maxcardinality, **kwargs)¶

Finds the minimum-weight matching of a list of edges using networkx.algorithms.matching.max_weight_matching.

Parameters

edges ([[nodeA, nodeB, distance(nodeA,nodeB)],..]) – A graph defined by a list of edges.
maxcardinality (float) – See networkx.algorithms.matching.max_weight_matching.

Returns

Minimum weight matching in the form of [[nodeA, nodeB],..].

Return type

list

match_syndromes(syndromes, use_blossomv=False, **kwargs)¶

Decodes a list of syndromes of the same type.

A graph is constructed with the syndromes in syndromes as nodes and the distances between each of the syndromes as the edges. The distances are dependent on the boundary conditions of the code and is calculated by get_qubit_distances. A minimum-weight matching is then found by either match_networkx or match_blossomv.

Parameters

syndromes (List[AncillaQubit]) – Syndromes of the code.
use_blossomv (bool) – Use external C++ Blossom V library for minimum-weight matching. Needs to be downloaded and compiled by calling get_blossomv.

Returns

Minimum-weight matched ancilla-qubits.

Return type

list of AncillaQubit

Plotting¶

class qsurface.decoders.mwpm.plot.Toric(*args, **kwargs)¶

Plot MWPM decoder for the toric code.

Parameters

args – Positional and keyword arguments are passed on to decoders._template.Plot and decoders.mwpm.sim.Toric.
kwargs – Positional and keyword arguments are passed on to decoders._template.Plot and decoders.mwpm.sim.Toric.

class qsurface.decoders.mwpm.plot.Planar(*args, **kwargs)¶

Plot MWPM decoder for the planar code.

Parameters

args – Positional and keyword arguments are passed on to Toric and decoders.mwpm.sim.Planar.
kwargs – Positional and keyword arguments are passed on to Toric and decoders.mwpm.sim.Planar.

dennis2002: Dennis, Eric and Kitaev, Alexei and Landahl, Andrew and Preskill, John, Topological quantum memory, in Journal of Mathematical Physics, 2002, 43(9)4452-4505.
wang2003: Wang, Chenyang and Harrington, Jim and Preskill, John, Confinement-Higgs transition in a disordered gauge theory and the accuracy threshold for quantum memory, in Annals of Physics, 2003, 303(1)31-58.
kolmogorov2009(1,2): Kolmogorov, Vladimir, Blossom V: A new implementation of a minimum cost perfect matching algorithm in Mathematical Programming Computation (MPC), July 2009, 1(1):43-67.