Flag Gadgets Based on Classical Codes

Fault-tolerant syndrome extraction is a key ingredient in implementing fault-tolerant quantum computation. While conventional methods use a number of extra qubits that are linear in the weight of the syndrome, several improvements have been introduced using flag gadgets. In this work, we develop a framework to design flag gadgets using classical codes. Using this framework, we show how to perform fault-tolerant syndrome extraction for any stabilizer code with arbitrary distance using exponentially fewer qubits than conventional methods when qubit measurement and reset are relatively slow compared to a round of error correction. In particular, our method requires only <a:math xmlns:a="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"><a:mo stretchy="false">(</a:mo><a:mn>2</a:mn><a:mi>t</a:mi><a:mo>+</a:mo><a:mn>1</a:mn><a:mo stretchy="false">)</a:mo><a:mi>t</a:mi><a:mrow><a:mo>⌈</a:mo><a:mrow><a:msub><a:mi>log</a:mi><a:mn>2</a:mn></a:msub><a:mo></a:mo><a:mo stretchy="false">(</a:mo><a:mi>w</a:mi><a:mo stretchy="false">)</a:mo></a:mrow><a:mo>⌉</a:mo></a:mrow></a:math> flag qubits to fault-tolerantly measure a weight-<h:math xmlns:h="http://www.w3.org/1998/Math/MathML" display="inline" overflow="scroll"><h:mi>w</h:mi></h:math> stabilizer. We further take advantage of the saving provided by our construction to fault-tolerantly measure multiple stabilizers using a single gadget and show that it maintains the same exponential advantage when it is used to fault-tolerantly extract the syndromes of quantum low-density parity-check codes. Using the developed framework, we perform computer-assisted search to find several small examples where our constructions reduce the number of qubits required. These small examples may be relevant to near-term experiments on small-scale quantum computers. Published by the American Physical Society 2024