Beam Search Decoder for Quantum Low-Density Parity-Check Codes

We propose a decoder for quantum low-density parity-check (LDPC) codes based on a beam search heuristic guided by belief propagation (BP). Our beam search decoder applies to all quantum LDPC codes and achieves different speed-accuracy tradeoffs by tuning its parameters such as the beam width. We perform numerical simulations under circuit level noise for the <a:math xmlns:a="http://www.w3.org/1998/Math/MathML" display="inline"> <a:mo stretchy="false">[</a:mo> <a:mo stretchy="false">[</a:mo> <a:mn>144</a:mn> <a:mo>,</a:mo> <a:mn>12</a:mn> <a:mo>,</a:mo> <a:mn>12</a:mn> <a:mo stretchy="false">]</a:mo> <a:mo stretchy="false">]</a:mo> </a:math> bivariate bicycle (BB) code at noise rate <g:math xmlns:g="http://www.w3.org/1998/Math/MathML" display="inline"> <g:mi>p</g:mi> <g:mo>=</g:mo> <g:msup> <g:mn>10</g:mn> <g:mrow> <g:mo>−</g:mo> <g:mn>3</g:mn> </g:mrow> </g:msup> </g:math> to estimate the logical error rate and the 99.9 percentile runtime and we compare with the BP-OSD decoder which has been the default quantum LDPC decoder for the past six years. A variant of our beam search decoder with a beam width of 64 achieves a <i:math xmlns:i="http://www.w3.org/1998/Math/MathML" display="inline"> <i:mn>17</i:mn> <i:mo>×</i:mo> </i:math> reduction in logical error rate. With a beam width of 8, we reach the same logical error rate as BP-OSD with a <k:math xmlns:k="http://www.w3.org/1998/Math/MathML" display="inline"> <k:mn>26.2</k:mn> <k:mo>×</k:mo> </k:math> reduction in the 99.9 percentile runtime. We identify the beam search decoder with beam width of 32 as a promising candidate for trapped ion architectures because it achieves a <m:math xmlns:m="http://www.w3.org/1998/Math/MathML" display="inline"> <m:mn>5.6</m:mn> <m:mo>×</m:mo> </m:math> reduction in logical error rate with a 99.9 percentile runtime per syndrome extraction round below 1 ms at <o:math xmlns:o="http://www.w3.org/1998/Math/MathML" display="inline"> <o:mi>p</o:mi> <o:mo>=</o:mo> <o:mn>5</o:mn> <o:mo>×</o:mo> <o:msup> <o:mn>10</o:mn> <o:mrow> <o:mo>−</o:mo> <o:mn>4</o:mn> </o:mrow> </o:msup> </o:math> . Remarkably, this is achieved in software on a single core, without any parallelization or specialized hardware (FPGA, ASIC), suggesting one might only need three 32-core CPUs to decode a trapped ion quantum computer with 1000 logical qubits.