\section*{Methods}

We here summarize our notation and then present construction of our fault-tolerant protocol, derivation of the existence of a threshold, and analysis of the space and time overheads.
See Supplemental Information for further detail.

\textit{Notation.}---
For a qubit $\mathbb{C}^2$,
the $Z$ basis is denoted by $\{\Ket{0},\Ket{1}\}$, and the $X$ basis by $\{\Ket{\pm}\coloneqq(\nicefrac{1}{\sqrt{2}})(\Ket{0}\pm\Ket{1})\}$.
Matrix elements are represented in terms of the $Z$ basis.
By convention of Ref.~\cite{N4}, we use the following notation:
\begin{align}
  X&=\left(\begin{matrix}
      0 & 1\\
      1 & 0
  \end{matrix}\right),\\
      Z&=\left(\begin{matrix}
          1 & 0\\
          0 & -1
      \end{matrix}\right),\\
      Y&=\left(\begin{matrix}
          0 & -\mathrm{i}\\
          \mathrm{i} & 0
      \end{matrix}\right)\propto XZ,\\
          H&=\frac{1}{\sqrt{2}}\left(\begin{matrix}
              1 & 1\\
              1 & -1
          \end{matrix}\right),\\
          S&=\left(\begin{matrix}
              1 & 0\\
              0 & \mathrm{i}
          \end{matrix}\right),\\
              \textsc{CNOT}&=\left(\begin{matrix}
                  1 & 0 & 0 & 0\\
                  0 & 1 & 0 & 0\\
                  0 & 0 & 0 & 1\\
                  0 & 0 & 1 & 0
          \end{matrix}\right),\\
              CZ&=\left(\begin{matrix}
                  1 & 0 & 0 & 0\\
                  0 & 1 & 0 & 0\\
                  0 & 0 & 1 & 0\\
                  0 & 0 & 0 & -1
          \end{matrix}\right),\\
                  R_y(\theta)&=\left(\begin{matrix}
                      \cos(\nicefrac{\theta}{2}) & -\sin(\nicefrac{\theta}{2})\\
                      \sin(\nicefrac{\theta}{2}) & \cos(\nicefrac{\theta}{2})
          \end{matrix}\right).
\end{align}
The identity operator is denoted by
\begin{equation}
\mathbbm{1}=\left(\begin{matrix}
                      1 & 0\\
                      0 & 1
          \end{matrix}\right).
\end{equation}

In the same way as referring to a running time $\exp(O(\log^c(M)))$ for fixed $c>0$ as a quasi-polynomial time in $M$,
we call
\begin{equation}
  \exp(O(\log^c(\log(M))))
\end{equation}
a quasi-polylogarithmic time.
A quasi-polylogarithmic time with $c>1$ may be larger than a polylogarithmic time $\exp(O(\log(\log(M))))=O(\polylog(M))$.
However, a quasi-polylogarithmic time for any $c>0$ is much smaller than a polynomial time, i.e., $\exp(O(\log(M)))=O(\poly(M))=O(M^\alpha)$, even for an arbitrarily small degree $\alpha>0$ of the polynomial.

\textit{Construction of fault-tolerant protocol.}---
In our fault-tolerant protocol, we use level-$l$ elementary operations to write a level-$l$ circuit for each $l\in\{L,L-1,\ldots,0\}$.
The set of level-$l$ elementary operations consist of a level-$l$ measurement operation, level-$l$ $H$-, \textsc{CNOT}-, $CZ$-, and Pauli-gate operations, level-$l$ initial-, Clifford-, and magic-state preparation operations, and a level-$l$ wait operation.
The measurement operation implements measurements in $Z$ basis of all qubits in a level-$l$ register.
The $H$-, $\textsc{CNOT}$-, $CZ$-, and Pauli-gate operations implement $H$, $\textsc{CNOT}$, and $CZ$ gates on all qubits in level-$l$ registers and tensor product of any combination of Pauli gates on the qubits in a level-$l$ register.
The initial-state preparation operation prepares a level-$l$ register in $\Ket{0}^{\otimes K^{(l)}}$.
To assist implementing any given two-register Clifford unitary $U_\mathrm{C}$ on the $2K^{(l)}$ qubits in two level-$l$ registers,
the Clifford-state preparation operation prepares four level-$l$ registers $B_1,B_2,B_3,B_4$ in
\begin{equation}
  \label{eq:Clifford_state}
  (\mathbbm{1}^{B_1B_2}\otimes U_\mathrm{C}^{B_3B_4})\ket{\Phi^{(l)}}^{B_1B_2B_3B_4},
\end{equation}
where $\ket{\Phi^{(l)}}^{B_1B_2B_3B_4}=\ket{\Phi}^{B_1B_3}\otimes\ket{\Phi}^{B_2B_4}$, and $\ket{\Phi}^{B_j B_{j^\prime}}\propto\sum_{m=0}^{2^{K^{(l)}}-1}\Ket{m}^{B_j}\otimes\Ket{m}^{B_{j^\prime}}$ for $(j,j^\prime)\in\{(1,3),(2,4)\}$ is a maximally entangled state between $B_j$ and $B_{j^\prime}$.
To assist implementing any given unitary $U_{R_y(\pm\nicefrac{\pi}{4})}$ in the form of a tensor product of $R_y(\nicefrac{\pi}{4})$, $R_y(-\nicefrac{\pi}{4})$, and $\mathbbm{1}$ on the $K^{(l)}$ qubits in a level-$l$ register,
the magic-state preparation operation prepares two level-$l$ registers in
\begin{equation}
  {(R_y(\nicefrac{\pi}{4})\Ket{0})}^{\otimes K^{(l)}}\otimes{(R_y(\nicefrac{\pi}{4})\Ket{0})}^{\otimes K^{(l)}}.
\end{equation}
A wait operation is a Pauli-gate operation of $\mathbbm{1}^{\otimes K^{(l)}}$.

Using these operations in combination, we implement $U_\mathrm{C}$ and $U_{R_y(\pm\nicefrac{\pi}{4})}$ by gate teleportation.
In particular, a level-$l$ two-register Clifford gate $U_\mathrm{C}$ in our protocol is implemented by means of gate teleportation~\cite{gottesmanchuang1999,K5,K6}, assisted by the auxiliary state $(\mathbbm{1}^{B_1B_2}\otimes U_\mathrm{C}^{B_3B_4})\ket{\Phi^{(l)}}^{B_1B_2B_3B_4}$ prepared by the level-$l$ Clifford-state preparation operation, along with other level-$l$ gate and measurement operations.
The correction of byproducts in the gate teleportation is performed by level-$l$ Pauli-gate operations.
Regarding level-$l$ $U_{R_y(\pm\nicefrac{\pi}{4})}$,
the gate teleportation for $U_{R_y(\pm\nicefrac{\pi}{4})}$ is assisted by an auxiliary magic state ${(R_y(\nicefrac{\pi}{4})\Ket{0})}^{\otimes K^{(l)}}$ prepared by the level-$l$ magic-state preparation operation, and also an auxiliary state ${\Ket{0}}^{\otimes K^{(l)}}$ prepared by the level-$l$ initial-state preparation operation, along with other level-$l$ gate and measurement operations.
To apply $R_y(\pm\nicefrac{\pi}{4})$ in $U_{R_y(\pm\nicefrac{\pi}{4})}$ to a desired subset of qubits in a register, we prepare the required auxiliary state in the tensor product of $R_y(\nicefrac{\pi}{4})\Ket{0}$ and ${\Ket{0}}$ by applying single-qubit \textsc{SWAP} gates between ${(R_y(\nicefrac{\pi}{4})\Ket{0})}^{\otimes K^{(l)}}$ and ${\Ket{0}}^{\otimes K^{(l)}}$ using the level-$l$ two-register Clifford gate.
Then, assisted by this auxiliary state, we perform the gate teleportation.
The correction of byproducts is single-qubit Clifford gates on a level-$l$ register, performed by the level-$l$ two-register Clifford gate acting trivially on another auxiliary level-$l$ register.

To simulate a level-$l$ circuit at each level $l\in\{L,\ldots,1\}$, we construct a level-$l$ gadget corresponding to each level-$l$ elementary operation, i.e., a level-$(l-1)$ circuit for simulating the elementary operation on encoded level-$l$ registers.
Apart from these level-$l$ gadgets, we use a level-$l$ error-correction gadget, a level-$(l-1)$ circuit for correcting errors on one of the $N_{r_l}$ level-$(l-1)$ registers for an encoded level-$l$ register.
For the existence of a threshold, each level-$l$ gadget must be \textit{fault-tolerant}; that is, roughly speaking, even if one of the level-$(l-1)$ locations in the gadget has a fault, the resulting error should be correctable using the decoder of $\Q^{(l)}$ at the end of the gadget (See Supplemental Information for precise definition).
This definition of fault-tolerant gadgets in our protocol is a suitable modification of conventional definition for the concatenated codes~\cite{G}, so that we can prove the existence of a threshold by applying the conventional argument in Ref.~\cite{G} to our protocol.
Using the fault-tolerant level-$l$ gadgets, we convert a level-$l$ circuit into the corresponding level-$(l-1)$ circuit by replacing each level-$l$ elementary operation with the corresponding level-$l$ gadget, followed by inserting the level-$l$ error-correction gadgets between all pairs of adjacent level-$l$ elementary operations.
Repeating this conversion recursively for $l\in\{L,\ldots,1\}$ yields a level-$0$ circuit,
which leads to a fault-tolerant circuit on physical qubits to simulate the original circuit.

In the following, we sketch our construction of level-$l$ gadgets used for the fault-tolerant protocol.
See Supplemental Information for further detail.
Note that gate implementations for some classes of CSS codes with multiple logical qubits have also been discussed in Refs.~\cite{gottesman2014faulttolerant,PhysRevA.72.052335}, but the main contribution of our work is to present the gadgets explicitly for our code $\mathcal{Q}^{(l)}$ so that we can prove the existence of a threshold and bound the space and time overheads rigorously for our fault-tolerant protocol.

We implement the level-$l$ measurement gadget by performing level-$(l-1)$ measurement operations for all the level-$(l-1)$ registers and then calculating bit values of the outcome by a decoder, using the logical $Z$ operator for each logical qubit in the encoded level-$l$ register.
The fault tolerance follows from transversality.

We implement the $H$-, $\textsc{CNOT}$-, and $CZ$-gate gadgets by applying level-$(l-1)$ $H$-, $\textsc{CNOT}$-, and $CZ$-gate operations, respectively, to all level-$(l-1)$ registers transversally.
We implement the Pauli-gate gadget by level-$(l-1)$ Pauli-gate operations to apply the tensor product of Pauli gates representing the logical Pauli operators to the level-$(l-1)$ registers transversally.
The wait gadget is a special case of the Pauli-gate gadget to apply the identity gate.
The fault tolerance follows from transversality.

The level-$l$ initial-state preparation gadget is implemented by transforming states $\Ket{0}^{\otimes K^{(l-1)}}$ prepared by the level-$(l-1)$ initial-state preparation operations into logical $\Ket{0}^{\otimes K^{(l)}}$ by a level-$(l-1)$ stabilizer circuit in a non-fault-tolerant way~\cite{PhysRevA.56.76}, followed by verification with post-selection.
For the verification, we prepare another logical $\Ket{0}^{\otimes K^{(l)}}$, and using this auxiliary $\Ket{0}^{\otimes K^{(l)}}$, we measure the logical $Z$ operators and the $Z$ stabilizer generators of $\Q_{r_l}$.
The post-selection discards the states that may have logical $X$ errors on logical $\Ket{0}^{\otimes K^{(l)}}$, which makes the gadget fault-tolerant~\cite{G}.

Assisted by the registers in logical states ${\Ket{0}}^{\otimes K^{(l)}}$ prepared by the level-$l$ initial-state preparation gadgets,
the level-$l$ error-correction gadget is implemented here in a fault-tolerant way by Knill's error correction~\cite{K5,K6} based on quantum teleportation~\cite{PhysRevLett.70.1895}.
Note that we could also use Steane's error correction here~\cite{G}, but Knill's error correction may have merits in our protocol since Knill's error correction can be implemented in the same way as gate teleportation used for implementing the level-$l$ two-register Clifford gates.
The fault tolerance follows from transversality.

The level-$l$ Clifford-state preparation gadget is implemented as follows.
First, we transform logical states ${\Ket{0}}^{\otimes K^{(l)}}$ prepared by the level-$l$ initial-state preparation gadgets into logical $(\mathbbm{1}\otimes U_\mathrm{C})\ket{\Phi^{(l)}}$ by a level-$(l-1)$ stabilizer circuit in a non-fault-tolerant way~\cite{PhysRevA.56.76}.
Then, we perform verification with post-selection.
In the verification, we let the state be in the code space of $\Q_{r_l}$ using the level-$l$ error-correction gadgets, and then measure the logical stabilizer operators for $(\mathbbm{1}\otimes U_\mathrm{C})\ket{\Phi^{(l)}}$ with technique of flag qubits~\cite{PhysRevLett.121.050502}, to make the gadget fault-tolerant.

The level-$l$ magic-state preparation gadget is implemented as follows.
First, we transform states ${(R_y(\nicefrac{\pi}{4})\Ket{0})}^{\otimes 2K^{(l)}}$ and ${\Ket{0}}^{\otimes 2(N^{(l)}-K^{(l)})}$ prepared by the level-$(l-1)$ magic- and initial-state preparation operations, respectively, into logical ${(R_y(\nicefrac{\pi}{4})\Ket{0})}^{\otimes K^{(l)}}\otimes{(R_y(\nicefrac{\pi}{4})\Ket{0})}^{\otimes K^{(l)}}$ by a level-$(l-1)$ stabilizer circuit for encoding, i.e., for transforming the magic states into the same logical states in a non-fault-tolerant way~\cite{PhysRevA.56.76}.
Then, we perform the verification via ensuring the state in the code space of $\Q_{r_l}$ and measuring the logical stabilizer operators for ${(R_y(\nicefrac{\pi}{4})\Ket{0})}^{\otimes K^{(l)}}\otimes{(R_y(\nicefrac{\pi}{4})\Ket{0})}^{\otimes K^{(l)}}$ with the flag qubits~\cite{PhysRevLett.121.050502}, to make the gadget fault-tolerant.
This magic state preparation does not use magic state distillation~\cite{PhysRevA.71.022316,https://doi.org/10.48550/arxiv.quant-ph/0402171},
but based on $H{(R_y(\nicefrac{\pi}{4})\Ket{0})}={R_y(\nicefrac{\pi}{4})\Ket{0}}$,
we implement controlled $H$ gates for measuring the logical stabilizer operators, using techniques similar to state-of-the-art low-overhead magic-state-preparation protocols in Refs.~\cite{yamasaki2020polylogoverhead,G6,Chamberland2019faulttolerantmagic}.

With synthesis of stabilizer circuits~\cite{PhysRevA.70.052328,10.5555/2011763.2011767}, we show that all the level-$l$ gadgets here have at most $O(\poly(N_{r_l}))$ depths including the wait operations to wait for classical computation.
Thus, each level-$l$ gadget has at most $O(\poly(N_{r_l}))$ locations, even if we take into account wait operations to wait for nonzero-time classical computation such as ones in the decoder and the gate teleportation.

\textit{Analysis of threshold existence and improvement.}---
We sketch the proof of the existence of a threshold in our fault-tolerant protocol and discuss how to achieve a practical threshold with minor protocol modifications.
See Supplemental Information for further detail.

As in the conventional proof for the concatenated code,
the proof of the existence of a threshold in our protocol is given by bounding a logical error rate at a higher concatenation level by that at a lower level, based on counting the number of locations in extended rectangles (ExRecs)~\cite{G}.
Given a level-$l$ circuit for $l\in\{1,\ldots,L\}$, a level-$l$ ExRec refers to a part of the corresponding level-$(l-1)$ circuit that includes a level-$l$ gadget at each level-$l$ location and its adjacent level-$l$ error-correcting gadgets~\cite{G}.
Let $A(l)$ be the maximum number of pairs of level-$(l-1)$ locations in a level-$l$ ExRec, where we take the maximum over all the possible level-$l$ ExRecs.
Since all the level-$l$ gadgets used in our protocol has $O(\poly(N_{r_l}))$ level-$(l-1)$ locations, we have $A(l)=O(\poly(N_{r_l}))=\exp({O(l)})$.
For simplicity of presentation, let $\alpha>0$ denote a constant factor such that
\begin{equation}
  \label{eq:A_l}
  A(l)\leqq 2^{\alpha l}
\end{equation}
for all $l\geqq 1$.
Crucially, our definition of a gadget being fault-tolerant is made analogous to the conventional definition in Ref.~\cite{G}, so that the same argument as Ref.~\cite{G} is applicable to our protocol.
When a level-$(l-1)$ circuit simulates a level-$l$ circuit, this argument leads to the fact that if the level-$(l-1)$ circuit undergoes the local statistic error model, the level-$l$ circuit also does.
Then, let $p_0$ be the physical error rate of level-$0$ locations, and $p_l$ denote the logical error rate of level-$l$ locations at each level $l$.
The conventional argument for the threshold theorem proves that the logical error rates are bounded by $p_l\leqq A(l)p_{l-1}^2$ for each $l$~\cite{G}, which leads to $p_l\leqq 2^{\alpha l}p_{l-1}^2$.
Using this bound recursively, we can prove that the logical error rate $p_L$ is bounded by $p_L\leqq{(2^{2\alpha}p_0)}^{2^L}$, as shown in Supplemental Information.
This shows the existence of a threshold $p_\mathrm{th}\geqq 2^{-2\alpha}$ such that the logical error rate $p_L\leqq{(\nicefrac{p_0}{p_\mathrm{th}})}^{2^L}p_\mathrm{th}$ can be suppressed doubly exponentially in $L$ if the physical error rate satisfies $p_0<p_\mathrm{th}$.
Note that the same argument as ours for the threshold existence holds even in cases where the exponent $\alpha l$ of $2^{\alpha l}$ in~\eqref{eq:A_l} is replaced with $\poly(l)$; e.g., even if the gadgets had $O(\poly(N^{(l)}))$ depths due to architectural overhead or insufficient parallelization, a threshold would still exist.

Remarkably, a practical threshold is also achievable with minor modifications of our protocol.
Any quantum code with one logical qubit can be concatenated with $\Q^{(L)}$ by using the logical qubit of the code in place of each level-$0$ qubit of $\Q^{(L)}$, as long as the code can implement required operations for our fault-tolerant protocol at level $0$, namely, preparation of a qubit in $\Ket{0}$, a single-qubit measurement in the $Z$ basis, and the $H$, $S$, $\textsc{CNOT}$, $CZ$, Pauli, and $R_y(\pm\nicefrac{\pi}{4})$ gates.
For example, we can concatenate the surface code and $\Q^{(L)}$ and replace physical operations for our fault-tolerant protocol at concatenation level $0$ with the corresponding logical operations on the surface code.
Indeed, the surface code has well-established procedures for implementing logical operations for universal quantum computation~\cite{Horsman_2012,Litinski2019gameofsurfacecodes}; thus, we can use the logical qubit of a constant-size surface code in place of each physical qubit of $\Q^{(L)}$ in our protocol.
With this modification, we can achieve the same threshold as that of the surface code, and at the same time attain the constant overhead asymptotically.
See also Supplemental Information regarding further options of protocol modifications for a better threshold.

\textit{Analysis of space and time overhead.}---
We sketch the analysis of space and time overheads of our fault-tolerant protocol.
See Supplemental Information for further detail.

To achieve the constant space overhead, our protocol uses the code $\Q^{(L)}$ with a non-vanishing rate of logical qubits per physical qubit.
However, it is still nontrivial to achieve the constant space overhead since the protocol may additionally use auxiliary level-$(l-1)$ registers in level-$l$ gadgets for implementability.
Crucially, we design each level-$l$ gadget to use only a constant number of auxiliary level-$(l-1)$ registers per encoded level-$l$ register, so as to keep the overall space overhead constant
\begin{equation}
  O(1)\quad\text{as $M\to\infty$},
\end{equation}
including physical qubits used for the auxiliary registers.

To save the time overhead, it is essential to realize gates acting on all the level-$L$ registers in parallel.
At the same time, it is also crucial to keep the code size for the sufficient error suppression as small as possible; after all, a smaller code size leads to a faster preparation of auxiliary states for gate teleportation and thus a smaller time overhead in implementing each gate acting on the level-$L$ registers.
As our threshold analysis shows, the suppression of the logical error rate $p_L=\exp(-O(2^L))$ in our protocol is exponentially faster than the growth of the code size $N^{(L)}=\exp(O(L^2))$ of $\mathcal{Q}^{(L)}$.
By choosing $L\approx\log\log(\nicefrac{M}{\epsilon})$, we can reduce the overall error in simulating the original circuit to $\epsilon$.
With this choice, the size of each code block $\mathcal{Q}^{(L)}$ becomes only quasi-polylogarithmic $N^{(L)}=\exp(O(L^2))=\exp(O(\polylog(\log(\nicefrac{M}{\epsilon}))))$.
On the other hand, each gadget in our protocol is designed to be implementable within at most polynomial time in the code size.
Therefore, this code size leads to the quasi-polylogarithmically small time overhead
\begin{equation}
  \exp(O(\polylog(\log(\nicefrac{M}{\epsilon}))))
\end{equation}
in implementing the gates and thus in simulating the original circuit.
Significantly, this time overhead includes that for preparing auxiliary states for gate teleportation and error correction, and also that for waiting for the nonzero-time classical computation during the protocol, such as ones required for the decoder and the gate teleportation.

\begin{acknowledgments}
  H.Y.\ acknowledges Keisuke Fujii and Yasunari Suzuki for comments in the meeting of JST PRESTO\@.
  This work was supported by JSPS Overseas Research Fellowships, JST PRESTO Grant Number JPMJPR201A, and JST [Moonshot R\&D][Grant Number JPMJMS2061].
\end{acknowledgments}

\newpage
