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>
<aside>
<aside>
Abstract: Query complexity is a branch of complexity theory where we are interested in studying the number of bits of the input any algorithm must access to compute a Boolean function. Things get interesting in the quantum setting where the algorithms can query the input in superposition. The seminal result by Reichardt [SODA 2011] showed that the quantum query complexity for computing a function is exactly characterized by an optimization program (which depends on the function and the query model), namely the general adversary method.
In this talk, we first introduce quantum query complexity and the general adversary method. We then look at the "Search with Wildcards" problem where we learn a $n$-bit string using wildcard queries. In simple terms, each wildcard query is a guess of a substring of the input and the response to the query indicates if the guess was correct. This problem was previously studied by Ambainis & Montanaro [Quantum Information & Computation 2014] and Belovs [Computational Complexity 2015] where they proved that learning a $n$-bit string only requires $\Theta(\sqrt{n})$ quantum wildcard queries.
Finally, we present a symmetrization technique to simplify the general adversary method for the specific problem of learning a $n$-bit string using wildcard queries. Using this technique, we present tight (in most cases) bounds for different restrictions of wildcard queries such as prefix queries, contiguous queries and bounded queries.
Joint-work with: Arjan Cornelissen, Nikhil S. Mande, Subhasree Patro, and Swagato Sanyal </aside>
<aside>
<aside>