Ankith Mohan

Decoders are a critical component of fault-tolerant quantum computing. They must identify errors based on syndrome measurements to correct quantum states. While finding the optimal correction is NP-hard and thus extremely difficult, approximate decoders with faster runtime often rely on uncontrolled heuristics. In this work, we propose a family of hierarchical quantum decoders with a tunable trade-off between speed and accuracy while retaining guarantees of optimality. We use the Lasserre Sum-of-Squares (SOS) hierarchy from optimization theory to relax the decoding problem. This approach creates a sequence of Semidefinite Programs (SDPs). Lower levels of the hierarchy are faster but approximate, while higher levels are slower but more accurate. We demonstrate that even low levels of this hierarchy significantly outperform standard Linear Programming relaxations. Our results on rotated surface codes and honeycomb color codes show that the SOS decoder approaches the performance of exact decoding. We find that Levels 2 and 3 of our hierarchy perform nearly as well as the exact solver. We analyze the convergence using rank-loop criteria and compare the method against other relaxation schemes. This work bridges the gap between fast heuristics and rigorous optimal decoding.

Quantum state discrimination is a fundamental primitive in quantum information processing, underpinning tasks in quantum communication, sensing, and learning. We study this problem through the lens of semidefinite programming and develop a general dimension-reduction framework for optimal discrimination. Our approach applies to (i) ensembles of pure states (not necessarily linearly independent), (ii) mixed states, and (iii) fully general discrimination settings in which the set of guesses and the reward assigned to each guess--state pair are arbitrary. This formulation encompasses standard minimum-error discrimination, minimum-error exclusion, discrimination with penalties for incorrect guesses, and structured reward models arising in problems such as quantum anomaly detection. We show that the resulting semidefinite program can be reduced from dimension $dL$ to $NL$, where $d$ is the Hilbert space dimension of the states, $N$ is the number of candidate states, and $L$ is the size of the set of possible guesses. Importantly, we further introduce a quantum pre-processing procedure which, given quantum access to the states to be discriminated, efficiently constructs the reduced semidefinite program, enabling our method to operate directly on quantum data. As an application, we characterize optimal identification probabilities for quantum changepoint problems in several regimes, including multiple-changepoint settings that were previously computationally inaccessible.

Quantum memory is a scarce and costly resource, yet little is known about which learning tasks remain feasible under severe memory constraints. We study the problem of computing global properties of quantum sequences when quantum systems must be measured individually, without storing or jointly processing them. In our setting, a bit string \(x \in \{0,1\}^n\) is encoded into an \(n\)-qubit product state \(\ket{\psi_{x_1}} \otimes \cdots \otimes \ket{\psi_{x_n}}\), and the goal is to infer \(f(x) \in \{0,1\}\) from measurements of this quantum encoding. We consider a simple local strategy, which we call the \emph{greedy strategy}, that applies the same optimal single-system measurement independently to each subsystem and then infers \(f(x)\) from the results. Our main result gives a complete characterization of when the greedy strategy is optimal: it achieves the same maximum success probability as an unrestricted global measurement if and only if the target Boolean function is affine (in all but finitely many cases). For general Boolean functions, we establish a universal performance guarantee, showing that the success probability of the greedy strategy is always at least the square of the optimal global success probability, in direct analogy with the Barnum--Knill bound for the pretty good measurement. These results demonstrate that even under extreme memory constraints, simple local measurement strategies can remain provably competitive for learning global properties of quantum sequences.