QuLunch is a biweekly QuSoft seminar on topics in quantum computation.
🗓️ Starting from Feb 3rd, every second Tuesday
<aside>
Speaker: Boldizsár Poór (Oxford University)
Abtstract: We establish a new performance benchmark for the fault-tolerant syndrome extraction of $\llbracket7, 1, 3\rrbracket$ Steane code with a dynamic protocol. Our method is built on two highly optimized circuits derived using fault-equivalent ZX-rewrites: a primary fault-tolerant circuit with 14 CNOTs and an efficient non-fault-tolerant recovery circuit with 11 CNOTs. The protocol uses an adaptive response to internal faults, discarding flagged measurements and falling back to the recovery circuit to correct potentially detrimental errors. Monte Carlo simulations confirm the efficiency of our protocol, reducing the logical error rate per cycle by an average of ∼14.3% relative to the optimized Steane method [1] and ∼ 17.7% compared to the Reichardt’s three-qubit method [2], the leading prior techniques.
[1] Rodatz, B., Poór, B., & Kissinger, A. (2025). Fault Tolerance by Construction. arXiv preprint arXiv:2506.17181.
[2] Reichardt, B. W. (2020). Fault-tolerant quantum error correction for Steane’s seven-qubit color code with few or no extra qubits. Quantum Science and Technology, 6(1), 015007.
Joint-work with: Benjamin Rodatz and Aleks Kissinger </aside>
<aside>
<aside>
Speaker: Michael Walter (LMU Munich and UvA/QuSoft)
Abstract: Some representation-theoretic multiplicities, such as the Kostka and the Littlewood-Richardson coefficients, admit a combinatorial interpretation that places their computation in the complexity class $\textsf{\# P}$. Whether this holds more generally is considered an important open problem in mathematics and computer science, with relevance for geometric complexity theory and quantum information. Recent work has investigated the quantum complexity of particular multiplicities, such as the Kronecker coefficients and certain special cases of the plethysm coefficients.
Here, we show that a broad class of representation-theoretic multiplicities is in $\textsf{\# BQP}$. In particular, our result implies that the plethysm coefficients are in $\textsf{\# BQP}$, which was only known in special cases. It also implies all known results on the quantum complexity of previously studied coefficients as special cases, unifying, simplifying, and extending prior work. We obtain our result by multiple applications of the Schur transform. Recent work has improved its dependence on the local dimension, which is crucial for our work. We further describe a general approach for showing that representation-theoretic multiplicities are in $\textsf{\# BQP}$ that captures our approach as well as the approaches of prior work. We complement the above by showing that the same multiplicities are also naturally in $\textsf{GapP}$ and obtain polynomial-time classical algorithms when certain parameters are fixed.
Joint-work with: Matthias Christandl, Aram W. Harrow, Greta Panova, Pietro M. Posta </aside>
<aside>
<aside>
<aside>
<aside>
Abstract: We present a complete set of rewrite rules for multi-qudit Clifford circuits, where $\emph{qudit}$ denotes a d-level quantum system with d an odd prime. Completeness means that any two Clifford circuits representing the same linear map can be transformed into each other using these rules. In total, there are 19 $\emph{Clifford relations}$, each involving at most three qudits and admitting an intuitive interpretation.
Our approach leverages the isomorphism between the symplectic group $\mathrm{Sp}(2n, \mathbb{Z}_d)$ and the quotient of the Clifford group by the Pauli group. We first derive a complete set of $\emph{symplectic relations}$ for $\mathrm{Sp}(2n, \mathbb{Z}_d)$, and then lift them to Clifford relations by incorporating Pauli corrections. To do this, we introduce a $\emph{symplectic normal form}$ that captures the stabiliser tableau of a Clifford operator and is unique up to Pauli correction. This simplification enables a streamlined derivation of a complete set of 66 relations, which we further compress to 18 symplectic relations. Our computations in $\mathrm{Sp}(2n, \mathbb{Z}_d)$ are formalised in the Agda proof assistant, providing a machine-verified proof of correctness.
Joint-work with: Xiaoning Bian, Neil J. Ross, John van de Wetering, and Yuming Zhao </aside>
<aside>
<aside>
Speaker: Nithish Raja
Abstract: In the “search with wildcards” problem [Ambainis, Montanaro, Quantum Inf. Comput.’14], one’s goal is to learn an unknown bit-string $x \in \{−1, 1\}^n$. An algorithm may, at unit cost, test equality of any subset of the hidden string with a string of its choice. Ambainis and Montanaro showed a quantum algorithm of cost $O(\sqrt{n} \log n)$ and a near-matching lower bound of $\Omega(\sqrt{n})$. Belovs [Comput. Comp.’15] subsequently showed a tight $O(\sqrt{n})$) upper bound.
We consider a natural generalization of this problem, parametrized by a subset $Q ⊆ 2^{[n]}$, where an algorithm may test whether xS = b for an arbitrary $S ∈ Q$ and $b ∈ \{−1, 1\}^S$ of its choice, at unit cost. We show the following:
All of these results are derived using a framework that we develop. We apply a symmetry reduction to the primal version of the negative-weight adversary bound, and show that the quantum query complexity of learning x is characterized, up to a constant factor, by a particular optimization program, which can be succinctly described as follows: ‘maximize over all odd functions $f : \{−1, 1\}^n \rightarrow \mathbb{R}$ the ratio of the maximum value of $f$ to the maximum (over $T ∈ Q$) standard deviation of f on a subcube whose free variables are exactly T.’
To the best of our knowledge, ours is the first work to use the primal version of the negative-weight adversary bound (which is a maximization program typically used to show lower bounds) to show new quantum query upper bounds without explicitly resorting to SDP duality.
Joint-work with: Arjan Cornelissen, Nikhil S. Mande, Subhasree Patro, and Swagato Sanyal </aside>
<aside>
<aside>