Union-find decoder for LDPC codes

Abstract

A quantum decoder receives a syndrome from a quantum measurement circuit and performs various decoding operations for processing-efficient fault detection. The decoding operations include generating a decoding graph from the syndrome and growing a cluster around each one of multiple check nodes in the graph that correspond to a non-trivial value in the syndrome. Each cluster includes the check node corresponding to the non-trivial value and a set of neighboring nodes positioned within a distance of d edge-lengths from the check node. Following cluster growth, the decoder determines if, for each cluster, there exists a solution set internal to the cluster that fully explains the non-trivial syndrome bit for the cluster. If so, the decoder identifies and returns at least one solution set that fully explains the set of non-trivial bits in the syndrome.

What is claimed is: 
     
       1. A method comprising:
 receiving a syndrome from a quantum measurement circuit, the syndrome including a plurality of syndrome bits providing information about one or more errors in a qubit register; and 
 generating a decoding graph from the syndrome, the graph having bit nodes that each correspond to one or more data qubits in the measurement circuit and check nodes that each correspond to one of the syndrome bits; 
 growing a cluster around each one of the check nodes corresponding to a non-trivial value in the syndrome, the cluster including the check node and a set of neighboring nodes positioned within a distance of d edge-lengths from the check node; 
 determining if each of the clusters is neutral, the cluster being neutral when there exists a solution set internal to the cluster that fully explains the non-trivial syndrome bit for the cluster; and 
 responsive to determining that all of the clusters are neutral, identifying and returning at least one solution set that fully explains the set of non-trivial bits in the syndrome. 
 
     
     
       2. The method of  claim 1 , further comprising:
 responsive to determining than one or more of the clusters is non-neutral, merging together clusters that contain neighboring nodes. 
 
     
     
       3. The method of  claim 1 , further comprising:
 responsive to determining that one or more of the clusters are non-neutral, growing each one of the clusters to include an additional set of nodes positioned within a maximum distance of d edge-lengths from a boundary of the cluster; 
 determining if each one of the clusters is neutral following the growing operation; 
 responsive to determining that all of the clusters are neutral, identifying and returning the at least one solution set that fully explains the set of non-trivial bits in the syndrome. 
 
     
     
       4. The method of  claim 1 , wherein the quantum measurement circuit implements a surface code and the distance of d edge-lengths consists of one edge. 
     
     
       5. The method of  claim 1 , wherein the quantum measurement circuit implements a folded code and the distance of d edge-lengths consists of two edges. 
     
     
       6. The method of  claim 5 , wherein the quantum measurement circuit implements a hexon architecture that includes a pair of data qubits at each of multiple physical sites. 
     
     
       7. The method of  claim 5 , wherein each of multiple physical sites include a pair of qubits connected by interaction channels. 
     
     
       8. The method of  claim 1 , wherein the qubit register includes logical qubits encoded in an LDPC code that is built from physical qubits. 
     
     
       9. A quantum system comprising:
 a quantum measurement circuit configured to measure a syndrome encoded on a grid of qubits; 
 a decoder stored in memory and executable to:
 generate a decoding graph based on the syndrome, the decoding graph having bit nodes that each correspond to one or more data qubits on the grid and check nodes that each correspond to one of a plurality of syndrome bits in the measured syndrome; 
 grow a cluster around each one of the check nodes that corresponds to a non-trivial value in the measured syndrome, the cluster including the check node and a set of neighboring nodes positioned within a distance of d edge-lengths from the check node; 
 determine if each of the clusters is neutral, the cluster being neutral when there exists a solution set internal to the cluster that fully explains the non-trivial syndrome bit for the cluster; and 
 responsive to determining that all of the clusters are neutral, identify and returning at least one solution set that fully explains the set of non-trivial bits in the syndrome. 
 
 
     
     
       10. The quantum system of  claim 9 , wherein the decoder is further executable to: merge together clusters that contain one or more neighboring nodes responsive to determining than one or more of the clusters is non-neutral. 
     
     
       11. The quantum system of  claim 9 , wherein the decoder is further executable to:
 grow each one of the clusters to include an additional set of nodes positioned within the distance of d edge-lengths from the cluster responsive to determining that one or more of the clusters are non-neutral; 
 determine if each one of the clusters is neutral following the growing operation; 
 responsive to determining that all of the clusters are neutral, identify and return the at least one solution set that fully explains the set of non-trivial bits in the syndrome. 
 
     
     
       12. The quantum system of  claim 9 , wherein the quantum measurement circuit implements a surface code and the distance of d edge-lengths consists of one edge. 
     
     
       13. The quantum system of  claim 9 , wherein the quantum measurement circuit implements a folded code and the distance of d edge-lengths consists of two edges. 
     
     
       14. The quantum system of  claim 13 , wherein the quantum measurement circuit implements a Majorana hexon architecture that includes a pair of data qubits at each of multiple physical qubit sites. 
     
     
       15. The quantum system of  claim 13 , wherein each of multiple physical sites includes a pair of qubits connected by interaction channels. 
     
     
       16. One or more memory devices encoding computer-executable instructions for executing a computer process, the computer process comprising:
 receiving a syndrome from a quantum measurement circuit, the syndrome including a plurality of syndrome bits providing information about one or more errors in a qubit register; and 
 generating a decoding graph from the syndrome, the graph having bit nodes that each correspond to one or more data qubits in the measurement circuit and check nodes that each correspond to one of the syndrome bits; 
 growing a cluster around each one of the check nodes corresponding to a non-trivial value in the syndrome, the cluster including the check node and a set of neighboring nodes positioned within a distance of d edge-lengths from the check node; 
 determining if each of the clusters is neutral, the cluster being neutral when there exists a solution set internal to the cluster that fully explains the non-trivial syndrome bit for the cluster; and 
 responsive to determining that all of the clusters are neutral, identifying and returning at least one solution set that fully explains the set of non-trivial bits in the syndrome. 
 
     
     
       17. The one or more memory devices of  claim 16 , wherein the computer process further comprises:
 responsive to determining than one or more of the clusters is non-neutral, merging together clusters that contain one or more neighboring nodes. 
 
     
     
       18. The one or more memory devices of  claim 16 , wherein the computer process further comprises:
 responsive to determining that one or more of the clusters are non-neutral, growing each one of the clusters to include an additional set of nodes positioned within the distance of d edge-lengths from the cluster; 
 determining if each one of the clusters is neutral following the growing operation; 
 responsive to determining that all of the clusters are neutral, identifying and returning the at least one solution set that fully explains the set of non-trivial bits in the syndrome. 
 
     
     
       19. The one or more memory devices of  claim 16 , wherein the quantum measurement circuit implements a surface code and the distance of d edge-lengths consists of one edge. 
     
     
       20. The one or more memory devices of  claim 16 , wherein the quantum measurement circuit implements a folded code and the distance of d edge-lengths consists of two edges.