Publications

Entanglement is a fascinating feature of the quantum world and serves as a key resource for quantum information processing. While its foundation is well-established in the context of distinguishable particles, the concept of entanglement for identical particles is still subject to misconceptions and controversial views. To settle this issue, we first clarify conclusively that identical particles do not define proper subsystems: the algebra of observables of single particles cannot be faithfully embedded into the one of the total system, resulting inevitably in a violation of the subsystem axioms. Accordingly, no notion of entanglement and more general types of correlation between identical particles exists that is genuine, i.e., valid independent of the underlying quantum state. Yet, there exist specific non-generic wave functions which allow one to label the identical particles through disjoint spatial regions or generally orbital subspaces. As a consequence of our work, the crucial idea of `electron correlation' can only be established ad hoc, without the common operational meaning, as the deviation of a given many-electron wave function from the manifold of mean-field states.

Twin-field quantum key distribution (TF-QKD) dramatically enhances the secure key rate (SKR) over inter-city distances through its square-root scaling. Further improvements in aggregate SKR can be achieved by wavelength-division multiplexing (WDM) of parallel QKD channels. However, direct implementation in TF-QKD poses significant challenges, as each wavelength channel requires an independent ultra-stable seed laser, narrow-linewidth transmitters, and optical phase locked loops (OPLLs), which are not easily scalable. Here, we circumvent these limitations by employing two independent, integrated dissipative Kerr soliton (DKS) microcombs at Alice and Bob as multi-wavelength sources. High-visibility single-photon interference across all wavelength channels is achieved by stabilizing the frequencies of every comb line—requiring only the stabilization of the pump wavelength and repetition rates of the two microcombs. Based on this architecture, we perform a full TF-QKD experiment using the sending-or-not-sending protocol, achieving a total SKR of 1.57 Mbps over 201.1 km of fiber using 16 DWDM channels. This result represents more than an order-of-magnitude enhancement compared with single-wavelength TF-QKD at the same distance. Given that a single DKS comb can support over 100 coherent lines across the C-band, this approach offers a scalable pathway toward high-rate quantum key distribution over inter-city distances.

Quantum key distribution (QKD) is a promising technology for secure communication, particularly for satellite-based global networks, but its implementation is limited by atmospheric turbulence. In this study, we develop a 1.3 km campus-scale free-space optical link as a testbed for entanglement-based QKD and implement a Sagnac-based polarization-entangled photon source using a type-II PPKTP crystal. The photon-pair generation rate is characterized as a function of pump power, showing slopes of 244.8 kHz/mW with a 10 nm bandpass filter, achieving up to 1 MHz pair rate. The coincidence-to-accidental ratio (CAR) is also measured, revealing a trade-off between pair rate and multi-pair-induced degradation. These results establish a robust platform for future entanglement distribution over atmospheric channels and provide a foundation for satellite-based QKD systems.

We demonstrate a continuous-variable quantum key distribution system with an integrated silicon photonic receiver, achieving a 1.89 Mbps asymptotic secret key rate over 60 km, enabling metropolitan-area chip-based quantum secure communications.

In recent years, the quantum oracle model introduced by Aaronson and Kuperberg (2007) has found a lot of use in showing oracle separations between complexity classes and cryptographic primitives. It is generally assumed that proof techniques that do not relativize with respect to quantum oracles will also not relativize with respect to classical oracles. We show that this is not the case by showing a complexity class containment that relativizes with respect to classical oracles but not with quantum oracles. Specifically, we show that there is a quantum oracle problem that is contained in the class QMA, but not in a class we call polyQCPH. However, with respect to classical oracles, QMA is contained in polyQCPH, because polyQCPH is equal to PSPACE with respect to classical oracles. Our result works for bounded-error complexity classes, thus it resolves an open problem from Aaronson (2009). We also show that the same separation holds relative to a distributional oracle, which is a model introduced by Natarajan and Nirkhe (2024). We believe our findings show the need for some caution when using these non-standard oracle models, particularly when showing separa- tions between quantum and classical resources.

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.

While extracting the entanglement spectrum is essential for probing exotic quantum many-body phases, standard tomographic methods are limited by exponential measurement overhead. To overcome this scalability barrier, we propose a hybrid quantum-classical algorithm for the partial singular value decomposition (SVD) of bipartite states, grounded in the canonical form of matrix product states. Our framework extracts the dominant and subdominant Schmidt components via sequential deflation-based optimization. Because finite circuit depths and hardware noise degrade the mutual orthogonality between these sequentially extracted vectors, we introduce an explicit classical orthogonality correction using pseudo-inverses. Acting as an error-filtering mechanism, this post-processing enforces orthogonality to high numerical precision. Consequently, it relaxes the expressivity requirements on the quantum processor, allowing the use of shallow and suboptimal ansatzes. This tolerance for shallow circuits also enables a concurrent, synergistic architecture. The classically tractable evaluation of overlap matrices is offloaded to tensor-network contractions. Concurrently, the quantum processor is dedicated solely to computing cross-terms with the complex target state, facilitated by an auxiliary shallow reference state. This quantum evaluation design bypasses the need for controlled target-state preparations, thereby suppressing the error accumulation from massive gate sequences while maintaining linear signal sensitivity. We benchmarked our deflation-based algorithm on the ground states of one- and two-dimensional Heisenberg models, where it demonstrates improved precision over global single-circuit optimization methods that target the entire spectrum. By structurally decoupling numerical accuracy from the quantum circuit optimization, our framework provides a robust solution for large-scale entanglement spectrum estimation on advanced near-term quantum devices and early fault-tolerant platforms.

We prove by construction that the Bravyi-Poulin-Terhal bound on the spatial density of stabilizer codes does not generalize to stabilizer circuits. To do so, we construct a fault tolerant quantum computer with a coding rate above 5$\%$ and quasi-polylog time overhead, out of a line of qubits with nearest-neighbor connectivity, and prove it has a threshold. The construction is based on modifications to the tower of Hamming codes of Yamasaki and Koashi (Nature Physics, 2024), with operators measured using a variant of Shor’s measurement gadget.

A central challenge of quantum physics is to understand the structural properties of many-body systems, both in equilibrium and out of equilibrium. For classical systems, we have a unified perspective which connects structural properties of systems at thermal equilibrium to the Markov chain dynamics which mix to them. We lack such a perspective for quantum systems: many of the most fundamental ideas of the modern classical theory are notably absent from our quantum toolkit. We develop a theory which brings the broad scope and flexibility of the classical theory to quantum Gibbs states at high temperature. At its core is a natural quantum analogue of Dobrushin’s condition; whenever this condition holds, a concise path-coupling argument proves rapid mixing for the corresponding Markovian evolution. The same machinery bridges dynamic and structural properties: rapid mixing yields exponential decay of CMI without restrictions on the size of the probed subsystems, resolving a central question in the theory of open quantum systems. Our key technical insight is an optimal transport viewpoint which couples the quantum dynamics to a linear differential equation, enabling precise control over how local deviations from equilibrium propagate to distant sites.

The Generalized Quantum Stein's Lemma is a theorem in quantum hypothesis testing that provides an operational meaning to the relative entropy within the context of quantum resource theories. Its original proof was found to have a gap, which led to a search for a corrected proof. We formalize the proof presented in [Hayashi and Yamasaki (2024)] in the Lean interactive theorem prover. This is the most technically demanding theorem in physics with a computer-verified proof to date, building with a variety of intermediate results from topology, analysis, and operator algebra. In the process, we rectified minor imprecisions in [HY24]'s proof that formalization forces us to confront, and refine a more precise definition of quantum resource theory. Formalizing this theorem has ensured that our Lean-QuantumInfo library, which otherwise has begun to encompass a variety of topics from quantum information, includes a robust foundation suitable for a larger collaborative program of formalizing quantum theory more broadly.

We give a meta-complexity characterization of EFI pairs, which are considered the “minimal” primitive in quantum cryptography (due to their equivalence to quantum commitments and for being implied by almost all other known quantum cryptographic primitives). More precisely, we show that the existence of EFI pairs is equivalent to the following: there exists a non-uniformly samplable distribution over pure states such that the problem of estimating a certain Kolmogorov-like complexity measure is hard given a single copy. The complexity measure that we consider is a smoothed version of the algorithmic entropy notion introduced by Gács [Gác01]. A key technical step in our proof, which may be of independent interest, is to show that the existence of EFI pairs is equivalent to the existence of non-uniform single-copy secure pseudorandom state generators (nu 1-PRS). As a corollary, we get an alternative, arguably simpler, construction of a universal EFI pair.

We construct a publicly-verifiable non-interactive zero-knowledge argument system for QMA with the following properties of interest. - Transparent setup. Our protocol only requires a uniformly random string (URS) setup. The only prior publicly-verifiable NIZK for QMA (Bartusek and Malavolta, ITCS 2022) requires an *entire obfuscated program* as the common reference string. - Extractability. Valid QMA witnesses can be extracted directly from our accepting proofs. That is, we obtain a publicly-verifiable non-interactive argument of *quantum knowledge*, which was previously only known in a privately-verifiable setting (Coladangelo, Vidick, and Zhang, CRYPTO 2020). Our construction introduces a novel type of ZX QMA verifier with "strong completeness" and builds upon the coset state authentication scheme from (Bartusek, Brakerski, and Vaikuntanathan, STOC 2024) within the context of QMA verification. Along the way, we establish new properties of the authentication scheme. The security of our construction rests on the heuristic use of a post-quantum indistinguishability obfuscator. Rather than rely on the full-fledged classical oracle model (i.e. ideal obfuscation), we isolate a particular game-based property of the obfuscator that suffices for our proof, which we dub the *evasive composability* heuristic. As an additional contribution, we study a general method for replacing heuristic use of obfuscation with heuristic use of hash functions in the post-quantum setting. In particular, we establish security of the ideal obfuscation scheme of Jain, Lin, Luo, and Wichs (CRYPTO 2023) in the *quantum* pseudorandom oracle model (QPrO), which can be heuristically instantiated with a hash function. This gives us NIZK arguments of quantum knowledge for QMA in the QPrO, and additionally allows us to translate several quantum-cryptographic results that were only known in the classical oracle model to results in the QPrO.

Given a matrix $A$ of dimension $M\times N$ and a vector $\vec{b}$, the quantum linear system (QLS) problem asks for the preparation of a quantum state $\ket{\vec{y}}$ proportional to the solution of $A\vec{y} = \vec{b}$. Existing QLS algorithms typically have runtimes that scale linearly with the condition number $\kappa(A)$, the sparsity of $A$, and logarithmically with the inverse precision. However, these algorithms often overlook structural properties of the input vector $\vec{b}$, despite the fact that its alignment with the eigenspaces of $A$ can significantly affect performance. In this work, we present a new QLS algorithm that explicitly leverages the structure of the right-hand side vector $\vec{b}$. Let the sparsity of a matrix be defined as the maximum number of nonzero entries in any row or column. The runtime of our algorithm depends polynomially on the sparsity $\s$ of the augmented matrix $H = [A , -\vec{b}]$, the inverse precision, the $\ell_2$ norm of the solution $\vec{y} = A^+ \vec{b}$, and a new instance-dependent parameter $$ ET = \sum_{i=1}^M p_i^2 \cdot d_i, $$ where $\vec{p} = (AA^{\top})^+ \vec{b}$, and $d_i$ denotes the squared $\ell_2$-norm of the $i$-th row of $H$. To further reduce the runtime for certain applications we introduce a structure-aware rescaling technique tailored to the solution $\vec{y} = A^+ \vec{b}$. Unlike \emph{left} preconditioning methods, which transform the system to $DA\vec{z} = D\vec{b}$, our approach applies a \emph{right} rescaling matrix, reformulating the linear system as $A D \vec{z} = \vec{b}$. This combination of an instance-aware QLS algorithm and a rescaling strategy reopens the possibilities for achieving superpolynomial quantum speedups in various domains, such as nonlinear differential equations and polynomial systems. As a application, we develop a new quantum algorithm for solving multivariate polynomial systems in regimes where previous QLS-based methods fail. Our results yield a new end-to-end algorithmic framework, grounded in our new QLS algorithm, that applies to a broad class of problems. In particular, we apply our approach to the maximum independent set (MIS) problem, formulated as a special case of a polynomial system. Given a graph, the MIS problem asks for finding the largest subset of vertices such that no two vertices in the subset share an edge. We provide a detailed runtime analysis and show that, under certain conditions, our quantum algorithm for the MIS problem runs in polynomial time. While no classical algorithms have been developed under these conditions, a promising feature of our quantum algorithm is that its runtime explicitly depends on the structure of the independent sets in the input graph.

In this work we present a publicly verifiable quantum money protocol which assumes close to no quantum computational capabilities. We rely on one-time memories which in turn can be built from quantum conjugate coding and hardware-based assumptions. Specifically, our scheme allows for a limited number of verifications and also allows for quantum tokens for digital signatures. Double spending is prevented by the no-cloning principle of conjugate coding states. An implementation of the concepts presented in this work can be found at https://github.com/neverlocal/otm_billz.

How could quantum cryptography help us achieve what are not achievable in classical cryptography? In this work we study the classical cryptographic problem that two parties would like to perform secure computations with long outputs. As a basic primitive and example, we first consider the following problem which we call secure function sampling with long outputs: suppose $f:\{0,1\}^n\rightarrow \{0,1\}^m$ is a public, efficient classical function, where $m$ is big; Alice would like to sample $x$ from its domain and sends $f(x)$ to Bob; what Bob knows should be no more than $f(x)$ even if it behaves maliciously. Classical cryptography, like FHE and succinct arguments [Gen09,Kil92,HW15], allows us to achieve this task within communication complexity $O(n+m)$; could we achieve this task with communication complexity independent of $m$? In this work, we first design a quantum cryptographic protocol that achieves secure function sampling with approximate security, within $O(n)$ communication (omitting the dependency on the security parameter and error tolerance). We also prove the classical impossibility using techniques in [HW15], which means that our protocol indeed achieves a type of quantum advantage. Building on the secure function sampling protocol, we further construct protocols for general secure two-party computations [Yao86,GB01] with approximate security, with communication complexity only depending on the input length and the targeted security. In terms of the assumptions, we construct protocols for these problems assuming only the existence of collapsing hash functions [Unr16]; what's more, we also construct a classical-channel protocol for these problems additionally assuming the existence of noisy trapdoor claw-free functions [BCMVV,BKVV].

Directed $st$-connectivity (DSTCON) is the problem of deciding if there exists a directed path between a pair of distinguished vertices $s$ and $t$ in an input directed graph. This problem appears in many algorithmic applications, and is also a fundamental problem in complexity theory, due to its ${\sf NL}$-completeness. We show that for any $S\geq \log^2(n)$, there is a quantum algorithm for DSTCON using space $S$ and time $T\leq 2^{\frac{1}{2}\log(n)\log(n/S)+o(\log^2(n))}$, which is an (up to quadratic) improvement over the best classical algorithm for any $S=o(\sqrt{n})$. Of the $S$ total space used by our algorithm, only $O(\log^2(n))$ is quantum space -- the rest is classical. This effectively means that we can tradeoff classical space for quantum time.

Atmospheric turbulence poses a significant challenge to free-space measurement-device-independent quantum key distribution (FSO MDI-QKD) by inducing polarization distortions and stochastic propagation losses, which together degrade the secret key rate (SKR). In this paper, we propose a composite channel framework that unifies phase perturbations, beam spreading, beam drift, receiver-aperture truncation, scintillation-induced fading, and atmospheric attenuation into a compact set of closed-form interface parameters: an effective depolarization parameter, an effective decoherence parameter, and an effective end-to-end detection probability. By modeling turbulence-induced polarization changes as random polarization rotations with axis statistics captured by a directional distribution, we obtain a Pauli-diagonal effective depolarizing–dephasing description and derive an analytic SKR evaluation that can be directly embedded into standard MDI-QKD security analysis. We incorporate representative clear, overcast, and hazy profiles through weather-dependent attenuation and turbulence conditions, and the resulting parameterization enables computationally efficient SKR evaluation and link-parameter sweeps. Numerical case studies on a ground-to-satellite free-space link illustrate the SKR trends under the proposed framework, supporting physical-layer design and performance assessment for satellite-based MDI-QKD networks.

We study the problem of approximating the partition function of the transverse-field Ising model (TFIM), a widely studied quantum many-body model with important applications in quantum simulation and quantum annealing. Despite its fundamental importance, the algorithmic landscape for computing the TFIM partition function has remained poorly understood beyond restricted parameter regimes. We provide a precise characterization of the temperature regimes in which efficient approximation is possible, establishing a sharp computational phase transition. Let $J$ denote the symmetric interaction matrix and $\Delta(J) = \lambda_{\max}(J)-\lambda_{\min}(J)$ be its spectral width. We show that for all inverse temperatures $\beta \in [0,1/\Delta(J)]$, there exists an efficient classical randomized algorithm that approximates the partition function $\tr(e^{-\beta H})$ to within an arbitrarily small multiplicative factor. We apply the standard Trotter decomposition to map the quantum model to a classical spin system, then leverage new techniques in Markov chain analysis to show an efficient algorithm that samples from and computes the partition function of the resulting distribution. This temperature threshold is tight: for $\beta > 1/\Delta(J)$, we show that approximating the partition function is NP-hard and thus is unlikely to admit an efficient classical or quantum algorithm.

In quantum key distribution (QKD) networks, key resources are limited, and efficient key relay is essential for stable multi-site operation. However, evaluating how effective the key relay paths are requires large-scale and iterative verification using real networks, which entails substantial costs and practical constraints. This paper reports on a simulator that was developed to evaluate the performance and effectiveness of key relay path computation models in large-scale QKD networks. The simulator takes as input the results of key relay path selection obtained from various routing models and simulates fluctuations in the amount of key across the entire QKD network. Using this simulator, we confirmed that it is possible to systematically verify whether the key relay paths are suitable for efficient and stable operation of QKD networks under various network scales and operational conditions. The results provide a useful foundation for the design and evaluation of future QKD networks.

We study the problem of verifying quantum states in restricted-access quantum devices, as commonly encountered in cloud-based quantum computing. In such scenarios, users interact with hardware through limited interfaces, motivating verification approaches that rely only on observed statistics, in the spirit of device-independent and semi-device-independent frameworks. We introduce a black-box model in which the device is treated as an oracle with constrained input-output capabilities. Within this setting, we define a simple and implementation-agnostic statistical test for the certification of bipartite entangled states, specifically Bell states, based solely on measurement outcomes. The test is formulated as a hypothesis test using an error parameter analogous to the Quantum Bit Error Rate (QBER). Our main contribution is the introduction of this test together with its experimental validation under realistic access constraints. We implement the proposed method on a 2-qubit NMR platform and observe a stable baseline error rate of approximately 9%, which we interpret as an empirical noise floor. This value naturally defines a tolerance threshold for detecting statistically significant deviations from ideal behavior. Our results provide a concrete instance of semi-device-independent verification and suggest that noise profiles can be leveraged as practical certification tools in access-constrained quantum systems.

We present a symmetry-enabled direct quantum algorithm for computing many-body Green’s functions, a central tool for studying strongly correlated quantum systems. Our protocol relies only on native time evolution and straightforward measurements available on current hardware platforms. By exploiting parity symmetry—satisfied by a broad class of Hamiltonians in condensed matter physics and quantum chemistry, including the Fermi–Hubbard and Heisenberg models—we introduce a tailored quench spectroscopy scheme that recovers both the real and imaginary parts of two-point time correlators, from which Green’s functions can be reconstructed via efficient classical signal analysis. We further develop a tailored quantum Gibbs sampler that prepares parity-resolved (symmetric and antisymmetric) thermal states, enabling finite-temperature applications within the same framework. Finally, we show that the same symmetry-based measurement primitive extends naturally to out-of-time-ordered correlators (OTOCs), providing a practical path toward probing finite-temperature dynamics of strongly correlated quantum systems on near-term and early fault-tolerant quantum hardware.

Secure key leasing allows a cryptographic key to be leased as a quantum state in such a way that the key can later be revoked in a verifiable manner. In this work, we propose a modular framework for constructing secure key leasing with a classical-lessor, where the lessor is entirely classical and, in particular, the quantum secret key can be both leased and revoked using only classical communication. Based on this framework, we obtain classical-lessor secure key leasing schemes for public-key encryption (PKE), pseudorandom function (PRF), and digital signature. We adopt the strong security notion known as security against verification key revealing attacks (VRA security) proposed by Kitagawa et al. (Eurocrypt 2025) into the classical-lessor setting, and we prove that all three of our schemes satisfy this notion under the learning with errors assumption. Our PKE scheme improves upon the previous construction by Goyal et al. (Eurocrypt 2025), and our PRF and digital signature schemes are respectively the first PRF and digital signature with classical-lessor secure key leasing property. Along the way, we also construct a watermarking scheme and a dual-mode secure function evaluation scheme that satisfy certain useful properties, which may be of independent interest.

The Clifford group plays a central role in quantum information science. It is the building block for many error-correcting schemes and matches the first three moments of the Haar measure over the unitary group—a property that is essential for a broad range of quantum algorithms, with applications in pseudorandomness, learning theory, benchmarking, and entanglement distillation. At the heart of understanding many properties of the Clifford group lies the Clifford commutant: the set of operators that commute with $k$-fold tensor powers of Clifford unitaries. Previous understanding of this commutant has been limited to relatively small values of $k$, constrained by the number of qubits $n$. In this work, we develop a complete theory of the Clifford commutant. Our first result provides an explicit orthogonal basis for the commutant and computes its dimension for arbitrary $n$ and $k$. We also introduce an alternative and easy-to-manipulate basis formed by isotropic sums of Pauli operators. We show that this basis is generated by products of permutations— which generate the unitary group commutant— and at most three other operators. Additionally, we develop a \emph{graphical calculus} allowing a diagrammatic manipulation of elements of this basis. These results enable a wealth of applications: among others, we characterize all \emph{measurable} magic measures and identify optimal strategies for stabilizer property testing, whose success probability also offers an operational interpretation to stabilizer entropies. Finally, we show that these results also generalize to multi-qudit systems with prime local dimension. This submission merges two of our recent works: one presenting a complete theory of the Clifford commutant with applications, and one focused on showcasing a major application to state $k$-design convergence.

Non-local quantum computation (NLQC) replaces a local interaction between two systems with a single round of communication and shared entanglement. Despite many partial results, it is known that a characterization of entanglement cost in at least certain NLQC tasks would imply significant breakthroughs in complexity theory. Here, we avoid these obstructions and take an indirect approach to understanding resource requirements in NLQC, which mimics the approach used by complexity theorists: we study the relative hardness of different NLQC tasks by identifying resource efficient reductions between them. Most significantly, we prove that $f$-measure and $f$-route, the two best studied NLQC tasks, are in fact equivalent under $O(1)$ overhead reductions. This result simplifies many existing proofs in the literature and extends several new properties to $f$-measure. For instance, we obtain sub-exponential upper bounds on $f$-measure for all functions, and efficient protocols for functions in the complexity class $\mathsf{Mod}_k\mathsf{L}$. Beyond this, we study a number of other examples of NLQC tasks and their relationships.

Non-local quantum computation (NLQC) replaces a local interaction between two systems with a single round of communication and shared entanglement. Despite many partial results, it is known that a characterization of entanglement cost in at least certain NLQC tasks would imply significant breakthroughs in complexity theory. Here, we avoid these obstructions and take an indirect approach to understanding resource requirements in NLQC, which mimics the approach used by complexity theorists: we study the relative hardness of different NLQC tasks by identifying resource efficient reductions between them. Most significantly, we prove that $f$-measure and $f$-route, the two best studied NLQC tasks, are in fact equivalent under $O(1)$ overhead reductions. This result simplifies many existing proofs in the literature and extends several new properties to $f$-measure. For instance, we obtain sub-exponential upper bounds on $f$-measure for all functions, and efficient protocols for functions in the complexity class $\mathsf{Mod}_k\mathsf{L}$. Beyond this, we study a number of other examples of NLQC tasks and their relationships.

We continue the line of work initiated by Kalai et al. (STOC '23), studying "compiled" nonlocal games played between a classical verifier and a single quantum prover, with cryptography simulating the spatial separation between the players. The central open question in this area is to understand the soundness of this compiler against quantum strategies, and apart from results for specific games, all that is known is the recent "qualitative" result of Kulpe et al. (STOC '25) showing that the success probability of a quantum prover in the compiled game is bounded by the game's quantum commuting-operator value in the limit as the cryptographic security parameter goes to infinity. In this work, we make progress towards a quantitative understanding of quantum soundness for general games, by giving a concrete framework to bound the quantum value of compiled nonlocal games. Building on the result of Kulpe et al. together with the notion of "nice" sum-of-squares certificates, introduced by Natarajan and Zhang (FOCS '23) to bound the value of the compiled CHSH game, we extend the niceness framework and construct a hierarchy of semidefinite programs that searches exclusively over nice certificates. We show that this hierarchy converges to the optimal quantum value of the game. Additionally, we present a transformation to make any degree-1 sum-of-squares certificate nice. This approach provides a systematic method to reproduce all known bounds for special classes of games together with Kulpe et al.'s bound for general games from the same framework.

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.

We present a protocol for fault-tolerantly implementing the logical quantum random access memory (QRAM) operation, given access to a specialized, noisy QRAM device. For coherently accessing classical memories of size 2^n, our protocol consumes only poly(n) fault-tolerant quantum resources (logical gates, logical qubits, quantum error correction cycles, etc.), avoiding the need to perform active error correction on all Ω(2^n) components of the QRAM device. This is the first rigorous conceptual demonstration that a specialized, noisy QRAM device could be useful for implementing a fault-tolerant quantum algorithm. In fact, the fidelity of the device can be as low as 1/poly(n). The protocol queries the noisy QRAM device poly(n) times to prepare a sequence of n-qubit QRAM resource states, which are moved to a general-purpose poly(n)-size processor to be encoded into a QEC code, distilled, and fault-tolerantly teleported into the computation. To aid this protocol, we develop a new gate-efficient streaming version of quantum purity amplification that matches the optimal sample complexity in a wide range of parameters and is therefore of independent interest. The exponential reduction in fault-tolerant quantum resources comes at the expense of an exponential quantity of purely classical complexity---each of the n iterations of the protocol requires adaptively updating the 2^n-size classical dataset and providing the noisy QRAM device with access to the updated dataset at the next iteration. We show that this classical operation can be parallelized to poly(n) classical circuit depth, but only in a model where classical sparse matrix-vector multiplication for 2^n-dimensional vectors can be as well. While our protocol demonstrates that QRAM is more compatible with fault-tolerant quantum computation than previously thought, the need for significant classical computational complexity exposes potentially fundamental limitations to realizing a truly poly(n)-cost fault-tolerant QRAM.

Graph states admit a clean graph-theoretic classification of local-Clifford equivalence: two graph states are equivalent under tensor products of single-qubit Cliffords if and only if their graphs are related by a sequence of local complementations. Graph states are themselves a special case of graph codes, in which a vertex subset selects a logical qubit encoded across the vertices of the underlying graph. We provide the analog of the local-Clifford story for the single-qubit-encoded case: an explicit graph-theoretic recipe for the action of every logical single-qubit Clifford on the graph-code descriptor and the encoded-state coefficients. Each logical Clifford is implemented at the physical level by a circuit of single-qubit Cliffords alone, with no two-qubit entangling gates. We discuss the calculus, its closure, its physical implementation, and several open directions.

Quantum walks, both discrete and continuous, serve as fundamental tools in quantum information processing with diverse applications. This work introduces a hybrid quantum walk model that integrates the coin mechanism of discrete walks with the Hamiltonian-driven time evolution of continuous walks. Through systematic analysis of probability distributions, standard deviations, and entanglement entropy on fundamental graph structures (2-vertex circles, stars, and lines), we reveal distinctive dynamical characteristics that differentiate our model from conventional quantum walk paradigms. The proposed framework demonstrates unifying capabilities by naturally encompassing existing quantum walk models as special cases. Two significant applications emerge from this hybrid architecture: (1) We develop a novel protocol for perfect state transfer(PST) in general connected graphs, overcoming the limitations of previous graph-specific approaches. A PST on a tree graph has been implemented on a quantum superconducting processor. (2) We devise a quantum algorithm for multiplying $K$ adjacency matrices of $n$-vertex regular graphs with time complexity $O(n^2d_1\cdots d_K)$, outperforming classical matrix multiplication $(O(n^{2.371552}))$ when vertex degrees $d_i$ are bounded. The algorithm's efficacy for triangle counting is experimentally validated through the quantum simulation on PennyLane. These results establish the hybrid quantum walk as a versatile framework bridging discrete and continuous paradigms while enabling practical quantum advantage in graph computation tasks.

When designing quantum circuits for a given unitary, it can be much cheaper to achieve a good approximation on most inputs than on all inputs. In this work we formalize this idea, and propose that such "optimistic quantum circuits" are often sufficient in the context of larger quantum algorithms. For the rare algorithm in which a subroutine needs to be a good approximation on all inputs, we provide a reduction which transforms optimistic circuits into general ones. Applying these ideas, we build an optimistic circuit for the in-place quantum Fourier transform (QFT). Our circuit has depth O(log(n/ϵ)) for tunable error parameter ϵ, uses n total qubits, i.e. no ancillas, is local for input qubits arranged in 1D, and is measurement-free. The circuit's error is bounded by ϵ on all input states except an ϵ-sized fraction of the Hilbert space. The circuit is also rather simple and thus may be practically useful. Combined with recent QFT-based fast arithmetic constructions, the optimistic QFT yields factoring circuits of nearly linear depth using only 2n + O(n/log n) total qubits. Additionally, we apply our reduction technique to yield an approximate QFT with well-controlled error on all inputs; it is the first to achieve the asymptotically optimal depth of O(log (n/ϵ)) with a sublinear number of ancilla qubits. The reduction uses long-range gates but no measurements.

We introduce a mixed-state magic criterion, the Triangle Criterion, which plays a role for magic analogous to the Positive Partial Transposition (PPT) criterion for entanglement: it combines strong detection capability, a clear geometric interpretation, and an operational link to magic distillation. Using this criterion, we uncover several new features of multi-qubit magic distillation and detection. We prove that genuinely multi-qubit magic distillation protocols are strictly more powerful than all single-qubit schemes by showing that the Triangle Criterion is not stable under tensor products, in sharp contrast to the PPT criterion. Moreover, we show that, with overwhelming probability, multi-qubit magic states with relatively low rank cannot be distilled by any single-qubit distillation protocol. We derive an upper bound on the minimal purity of magic states, which is conjectured to be tight with both numerical and constructive evidences. Using this minimal-purity result, we predict the existence of unfaithful magic states, namely states that cannot be detected by any fidelity-based magic witness, and reveal fundamental limitations of mixed-state magic detection in any single-copy scheme.

In this work, we present a new algorithm for generating quantum circuits that efficiently implement continuous time quantum walks on arbitrary simple sparse graphs. The algorithm, called matching decomposition, works by decomposing a continuous-time quantum walk Hamiltonian into a collection of exactly implementable Hamiltonians corresponding to matchings in the underlying graph followed by a novel graph compression algorithm that merges edges in the graph. Lastly, we convert the walks to a circuit and Trotterize over these components. The dynamics of the walker on each edge in the matching can be implemented in the circuit model as sequences of CX and CRx gates. We do not use Pauli decomposition when implementing walks along each matching. Furthermore, we compare matching decomposition to a standard Pauli-based simulation pipeline and find that matching decomposition consistently yields substantial resource reductions, requiring up to 43% fewer controlled gates and up to 54% shallower circuits than Pauli decomposition across multiple graph families. Finally, we also present examples and theoretical results for when matching decomposition can exactly simulate a continuous-time quantum walk on a graph.

Simulating universal quantum circuits is of fundamental and practical importance for the development of quantum computation. But existing simulators, despite being powerful in their own regimes, are limited for quantum error correction (QEC) tasks like testing the fault-tolerance of a QEC gadget or accurately decoding and computing logical error rates under realistic noise. In this work, we propose a simulator called SyQMA that is especially amenable to QEC-related tasks through several attractive features. SyQMA can represent Clifford circuits with incoherent Pauli noise, coherent Pauli rotations and Pauli measurements, returns expected values and probabilities as analytical functions of the error rates, rotation angles and Pauli measurement outputs, and produces samples from the outcome distribution. For QEC, this simulator can perform maximum likelihood (MLD) decoding to return exact and analytical expressions of the logical error rate in stabiliser and magic state preparations, avoiding the problem of rare-event sampling in Monte Carlo simulations. SyQMA is based on an intuitive extension of stabiliser simulators where every non-Clifford Pauli rotation and incoherent Pauli channel is compactly represented with the addition of a virtual qubit, allowing for the consumption of only polynomial memory. We demonstrate the simulator on the FT preparation of stabiliser and magic states in the Iceberg, Steane, [[15,1,3]], and [[17,1,5]] codes.

A discrete time quantum walk is known to be the single-particle sector of a quantum cellular automaton. For a long time, these models have interested the community for their nice properties such as locality or translation invariance. This work introduces a model of distributed computation for arbitrary graphs inspired by quantum cellular automata. As a by-product, we show how this model can reproduce the dynamic of a quantum walk on graphs. In this context, we inves- tigate the communication cost for two interaction schemes. Finally, we explain how this particular quantum walk can be applied to solve the search problem and present numerical results on different types of topologies.

Efficient and coherent data retrieval and storage are essential for harnessing quantum algorithms' speedup. Such a fundamental task is addressed by a quantum Random Access Memory (qRAM). Despite their promising scaling properties, current qRAM proposals demand excessive resources and rely on operations beyond the capabilities of current hardware requirements, rendering their practical realization inefficient. We introduce a novel architecture that significantly reduces resource requirements while preserving optimal complexity scaling for quantum queries. Moreover, unlike previous proposals, our algorithm design leverages a simple, repeated operational block based exclusively on local unitary operations and short-range interactions between a limited number of quantum walkers traveling over a single binary tree. This novel approach not only simplifies experimental requirements by reducing the complexity of necessary operations but also enhances the architecture's scalability by ensuring a resource-efficient, modular design that maintains optimal quantum query performance.

We present a rigorous and complete security proof of the decoy-state BB84 quantum key distribution (QKD) protocol. Our analysis aims to achieve a high standard of mathematical rigour and completeness, thereby providing the necessary foundation for certification and standardization efforts. Beyond establishing the security of a specific protocol, this work develops a general and modular framework that can be readily adapted to a broad class of QKD protocols, including both prepare-and-measure and entanglement-based variants. Our framework unifies all major ingredients required for the analysis of realistic QKD protocols, including the analysis of classical authentication and classical processing, source-replacement schemes, finite-size analysis, source maps, squashing maps, and decoy-state techniques. In doing so, this work consolidates a diverse range of techniques scattered across the QKD literature into a unified formalism, representing a general and rigorous treatment of QKD security. Finally, it outlines a clear path towards incorporating practical imperfections within the same framework, thereby laying the groundwork for addressing implementation security in future analysis.

We present a rigorous and complete security proof of the decoy-state BB84 quantum key distribution (QKD) protocol. Our analysis aims to achieve a high standard of mathematical rigour and completeness, thereby providing the necessary foundation for certification and standardization efforts. Beyond establishing the security of a specific protocol, this work develops a general and modular framework that can be readily adapted to a broad class of QKD protocols, including both prepare-and-measure and entanglement-based variants. Our framework unifies all major ingredients required for the analysis of realistic QKD protocols, including the analysis of classical authentication and classical processing, source-replacement schemes, finite-size analysis, source maps, squashing maps, and decoy-state techniques. In doing so, this work consolidates a diverse range of techniques scattered across the QKD literature into a unified formalism, representing a general and rigorous treatment of QKD security. Finally, it outlines a clear path towards incorporating practical imperfections within the same framework, thereby laying the groundwork for addressing implementation security in future analysis.

We present a robust and composable device-independent (DI) quantum protocol between two parties for oblivious transfer (OT) using Magic Square devices in the bounded storage model [DFR`07, DFSS08] in which the (honest and cheating) devices and parties have no long-term quantum memory. After a fixed constant (real-world) time interval, referred to as DELAY, the quantum states decohere completely. The adversary (cheating party), with full control over the devices, is allowed joint (non-IID) quantum operations on the devices, and there are no time and space complexity bounds placed on its powers. The running time of the honest parties is polylog(λ) (where λ is the security parameter). Our protocol has a negligible (in λ) security error and can be implemented in the NISQ (Noisy Intermediate Scale Quantum) era. By robustness, we mean that our protocol is correct even when devices are slightly off (by a small constant) from their ideal specification. This is an important property since small manufacturing errors in the real-world devices are inevitable. Our protocol is sequentially composable and, hence, can be used as a building block to construct larger protocols (including DI bit-commitment and DI secure multi-party computation) while still preserving correctness and security guarantees. None of the known DI protocols for OT in the literature are secure against arbitrary (non-IID) devices and provide simulator-based (composable) security. This was a major open question in device-independent two-party distrustful cryptography, which we resolved. We prove a parallel repetition theorem for a certain class of entangled games with a hybrid (quantum-classical) strategy. This parallel repetition allows us to show min-entropy guarantees on certain random variables, which helps in proving the security of our protocol. The hybrid strategy helps to incorporate DELAY in our protocol. This parallel repetition theorem is a main technical contribution of our work. Since our games use hybrid strategies and the inputs to our games are not independent, we use a novel combination of ideas from previous works showing parallel repetition of classical games [Raz95, Hol07], quantum games [JPY14, JMS20, JK25], and anchored games [BVY17, JK21]. Although we present security proof for protocols in the bounded storage model with no long-term quantum memory (after DELAY), we can extend our results, along the lines of [DFR`07], to incorporate linear (in the number of devices) long-term quantum memory.

The complexity class Quantum Statistical Zero-Knowledge (𝖰𝖲𝖹𝖪), introduced by Watrous (FOCS 2002) and later refined in Watrous (SICOMP, 2009), has the best known upper bound 𝖰𝖨𝖯(𝟤)∩co-𝖰𝖨𝖯(𝟤), which was simplified following the inclusion 𝖰𝖨𝖯(𝟤)⊆𝖯𝖲𝖯𝖠𝖢𝖤 established in Jain, Upadhyay, and Watrous (FOCS 2009). Here, 𝖰𝖨𝖯(𝟤) denotes the class of promise problems that admit two-message quantum interactive proof systems in which the honest prover is typically computationally unbounded, and co-𝖰𝖨𝖯(𝟤) denotes the complement of 𝖰𝖨𝖯(𝟤). We slightly improve this upper bound to 𝖰𝖨𝖯(𝟤)∩co-𝖰𝖨𝖯(𝟤) with a quantum linear-space honest prover. A similar improvement also applies to the upper bound for the non-interactive variant 𝖭𝖨𝖰𝖲𝖹𝖪. Our main techniques are an algorithmic version of the Holevo-Helstrom measurement and the Uhlmann transform, both implementable in quantum linear space, implying polynomial-time complexity in the state dimension, using the recent space-efficient quantum singular value transformation of Le Gall, Liu, and Wang (CC, to appear).

We introduce a machine-learning-aided tensor network (TN) framework for discovering quantum error-correcting codes (QECCs). By directly representing the code space projector as a 2D TN, our approach captures standard stabilizer formalisms while extending naturally to non-additive codes. We frame QECC discovery as a hybrid optimization problem, using continuous gradient-based methods alongside discrete reinforcement learning to simultaneously optimize tensor weights and network topology. This provides a scalable, automated methodology for exploring novel QECCs.

Bosonic quantum communication has extensively been analysed in the asymptotic setting, assuming infinite channel uses and vanishing communication errors. Comparatively fewer detailed analyses are available in the non-asymptotic setting, which addresses a more precise, quantitative evaluation of the optimal communication rate: how many uses of a bosonic Gaussian channel are required to transmit $k$ qubits, distil $k$ Bell pairs, or generate $k$ secret-key bits, within a given error tolerance $\varepsilon$? In this work, we address this question by finding easily computable lower bounds on the non-asymptotic capacities of Gaussian channels, and we provide explicit evaluations for the pure loss channel, for the pure amplifier channel and for a non-Markovian noise that generalizes the pure loss channel, introduced in [IEEE Transactions on Information Theory 70, 8844–8869 (2024]. To derive our results, we develop new tools of independent interest. In particular, we find a stringent bound on the probability $P_{>N}$ that a Gaussian state has more than $N$ photons, demonstrating that $P_{>N}$ decreases exponentially with $N$. Furthermore, we design the first algorithm capable of computing the trace distance between two Gaussian states up to a fixed precision. To address the non-Markovian case, we also prove properties of singular values of Toeplitz matrices, providing an error bound on the convergence rate of the celebrated Avram–Parter’s theorem, which we regard as a new tool of independent interest for the field of quantum information theory and matrix analysis.

Quantum effect enables enhanced estimation precision in metrology, with the Heisenberg limit (HL) representing the ultimate limit allowed by quantum mechanics. Although the HL is generally unattainable in the presence of noise, quantum error correction (QEC) can recover the HL in various scenarios. A notable example is estimating a Pauli-$Z$ signal under bit-flip noise using the repetition code, which is both optimal for metrology and robust against noise. However, previous protocols often assume noise affects only the signal accumulation step, while the QEC operations---including state preparation and measurement---are noiseless. To overcome this limitation, we study fault-tolerant quantum metrology where all qubit operations are subject to noise. We focus on estimating a Pauli-$Z$ signal under bit-flip noise, together with state preparation and measurement errors in all QEC operations. We propose a fault-tolerant metrological protocol where a repetition code is prepared via repeated syndrome measurements, followed by a fault-tolerant logical measurement. We demonstrate the existence of an error threshold, below which errors are effectively suppressed and the HL is attained.

Quantum low-density parity check (qLDPC) codes are among the leading candidates to realize error-corrected quantum memories with low qubit overhead. Potentially high encoding rates and large distance relative to their block size make them appealing for practical suppression of noise in near-term quantum computers. In addition to increased qubit-connectivity requirements compared to more conventional topological quantum error correcting codes, qLDPC codes remain notoriously hard to compute with. In this work, we introduce a construction to implement all Clifford quantum gate operations on the recently introduced lift-connected surface (LCS) codes. These codes can be implemented in a 3D-local architecture and achieve asymptotic scaling $[[n, O(n^{1/3}), O(n^{1/3})]]$. In particular, LCS codes realize favorable instances with small numbers of qubits: For the [[15,3,3]] LCS code, we provide deterministic fault-tolerant (FT) circuits of the logical gate set {H, S, CNOT} based on flag qubits. By adding a procedure for FT magic state preparation, we show quantitatively how to realize an FT universal gate set in d=3 LCS codes. Numerical simulations indicate that our gate constructions can attain pseudothresholds in the range $p_th = 4.8 x 10^{-3} - 1.2 x 10^{-2}$ for circuit-level noise. The schemes use a moderate number of qubits and are therefore feasible for near-term experiments, facilitating progress for fault-tolerant error corrected logic in high-rate qLPDC codes.

Advantage Distillation (AD) is a classical post-processing technique that enhances Quantum Key Distribution (QKD) protocols by increasing the maximum acceptable Quantum Bit Error Rate (QBER) and thus extending the distance at which QKD links can be securely established. AD operates by post-selecting blocks of bits and extracting fewer high-fidelity bits, exhibiting a reduced QBER and thus lowering the amount of information that has to be disclosed during the information reconciliation step. In this work we present the first comprehensive finite key-size analysis of decoy-state BB84 enhanced via AD post-processing. We demonstrate that through the use of AD the maximum acceptable QBER increases from around 9.5% to around 17.3% for realistic key sizes. This result shows that substantial performance enhancements can be achieved in scenarios which are constrained by the maximum tolerable QBER via improvements of the post-processing method alone.

The main bottleneck for distributed quantum computing is the rate at which entanglement is produced between quantum processing units (QPUs). In this work, we prove that multiple QPUs connected through slow interconnects can outperform a monolithic architecture made with a single QPU. We present a distributed version of Clifford noise reduction (CliNR), a partial error correction scheme, and show that it outperforms a monolithic version of CliNR. Distributed CliNR has lower depth and lower logical error rates than monolithic CliNR even when the interconnects are slow. In simulations we show that the advantage persists with interconnects that are five times slower than two qubit gates. We also prove a sufficient condition for distributed CliNR to outperform monolithic CliNR. In addition, we present two methods for improving CliNR, allowing lower logical error rates and efficient performance for arbitrary length Clifford circuits. Finally we present results from an experimental implementation of a variant of CliNR on an ion trap quantum computer. This work is based on three papers that are available on arXiv (see extended abstract).

Simulating electron–phonon interactions on quantum computers remains challenging, with most algorithmic effort focused on Hamiltonian simulation and circuit optimization. In this work, we study the single-electron Holstein model and propose an initial-state ansatz that substantially enhances ground-state overlap in the strong-coupling regime, thereby reducing the number of iterations required in standard quantum phase estimation. We further show that this ansatz can be implemented efficiently and yields an exponential reduction in overall circuit costs relative to conventional initial guesses. Our results highlight the practical value of incorporating physical intuition into initial state preparation for electron–phonon coupled systems.

Quantum state learning is a fundamental problem in physics and computer science. As near-term quantum devices are error-prone, it is important to design error-resistant algorithms. Apart from device errors, other unexpected factors could also affect the algorithm, such as careless human read-out error, or even a malicious hacker deliberately altering the measurement results. Thus, we want our algorithm to work even in the worst case when things go against our favor. We consider the practical setting of single-copy measurements and propose the $\gamma$-adversarial corruption model where an imaginary adversary can arbitrarily change $\gamma$-fraction of the measurement outcomes. This is stronger than the $\gamma$-bounded SPAM noise model, where the post-measurement state changes by at most $\gamma$ in trace distance. Under our stronger model of corruption, we design an algorithm using non-adaptive measurements that can learn an unknown rank-$r$ state up to $\tilde{O}(\gamma\sqrt{r})$ in trace distance, provided that the number of copies is sufficiently large. We further prove an information-theoretic lower bound of $\Omega(\gamma\sqrt{r})$ for non-adaptive measurements, demonstrating the optimality of our algorithm. Our upper and lower bounds also hold for quantum state testing, where the goal is to test whether an unknown state is equal to a given state or far from it. Our results are intriguingly optimistic and pessimistic at the same time. For general states, the error is dimension-dependent and $\gamma\sqrt{d}$ in the worst case, meaning that only corrupting a very small fraction ($1/\sqrt{d}$) of the outcomes could totally destroy any non-adaptive learning algorithm. However, for constant-rank states that are useful in many quantum algorithms, it is possible to achieve dimension-independent error, even in the worst-case adversarial setting.

We show that if an adaptive Z2-linear measurement-based quantum computing protocol deterministically computes a non-affine Boolean function, then the underlying quantum resource satisfies an inconsistent set of linear equations. This witnesses an algebraic form of strong contextuality generalising Mermin’s All-versus-Nothing arguments. Such algebraic contextuality can be detected cohomologically, resolving an open question posed by Raussendorf, who had established cohomological witnesses of contextuality for non-adaptive protocols, but left the adaptive case open. We prove this result constructively: we model adaptive measurement protocols as ordinary measurements on a scenario of tree-like measurements, and explicitly build the inconsistent equations inductively.

Device-independent self-testing refers to the certification of quantum states based entirely on the correlations exhibited by measurements on separate subsystems. The fact that such a certification is possible at all is remarkable in its own right, and is intimately connected to the violation Bell’s inequalities by entangled quantum systems. In the bipartite case, self-testing of states has been completely characterized, up to local isometries, as there exist protocols that self-test arbitrary pure states of any local dimension. Despite the growing interest in device-independent certification protocols, an analogous result in the general multipartite case has remained elusive. In this work, we give a complete characterization of the qubit case, showing that any multipartite entangled state of qubits can be self-tested.

Free-space quantum communications offers a promising route for securely transmitting information over long distances. However, a major challenge for these systems is atmospheric turbulence, which distorts the spatial structure of light and can severely limit the amount of information that can be reliably transmitted. In this work, we propose and demonstrate a turbulence-resilient scheme for free-space quantum communication. By leveraging the phase conjugation property of stimulated parametric down-conversion, our scheme enables all-optical dynamic correction of spatial-mode distortion induced by atmospheric turbulence, thereby enhancing the secure key rate in high-dimensional quantum key distribution. We develop a theoretical model that provides detailed guidelines for selecting the optimal basis and spatial properties needed to maximize the efficiency of the proposed scheme. Both numerical simulations and experimental results show that, even under strong turbulence, our scheme can reduce the quantum error rates well below the security threshold. These results highlight the potential of nonlinear optical approaches as powerful tools for robust quantum communication in realistic free-space environments.

We propose a general framework for analysing the performance of quantum algorithms that consist of performing discrete operations controlled by a Poisson process. This extends our previous work [1]. In particular, we are interested in emulating certain features of adiabatic quantum computation without having to simulate time-dependent Hamiltonian evolution, since this typically causes a significant discretisation cost. We can also Poissonise the discretisation processes themselves. In this way we are able to show that discretisation in the context of adiabatic quantum computing is less costly than the general bounds on the Trotterisation error would imply. In this way we are able to reproduce key results from [2]. The resulting error bounds share many key features with the error bounds in adiabatic quantum computation. And many results are directly applicable. As applications, we show how our framework yields six distinct approaches to both the Grover search problem and the quantum linear systems problem that almost all achieve optimal asymptotic complexity.

In a recent breakthrough in additive combinatorics, Gowers, Green, Manners, and Tao (Annals of Mathematics, 2025) resolved the polynomial Freiman-Ruzsa conjecture. Here, we algorithmize their main result by dequantizing the stabilizer learning algorithm of Chen et al. [QIP'25]

Quantum topological data analysis is one of the most promising areas for quantum advantage. In particular, the LGZ algorithm is the most basic algorithm for estimating Betti numbers, which are considered to be the essential shape of point clouds. Since LGZ, various quantum algorithms have been proposed, but many of them are based on FTQC and require a large number of quantum resources. In this paper, we propose a QTDA algorithm that does not require ancilla bits using a Hamiltonian based on supersymmetry, which has not been widely used in existing research. In particular, by imposing constraints on the graph, we show that there is always a known 0 eigenvalue and eigenstate in the Hamiltonian, this allows us to use ancilla-free measurement algorithms. Moreover, by using randomization, we reduce the required number of samples.

Statistical mechanics assumes that a quantum many-body system at low temperature can be described by its Gibbs state. However, many complex quantum systems only exist as metastable states of dissipative open system dynamics, which substantially deviate from true thermal equilibrium. Why, then, should the predictions of thermal equilibrium--such as the area law--be so unreasonably effective in explaining low-temperature phenomena? In this work, we model metastable states as approximate stationary states of a quasi-local, (KMS)-detailed-balanced master equation representing Markovian system-bath interaction. We show that all metastable states exhibit universal structures that parallel true quantum Gibbs states: an area law of mutual information and a local Markov property. The more metastable the states are, the larger the regions to which these structural results apply. Behind our structural results lies a systematic framework encompassing sharp equivalences between local minima of free energy, a non-commutative Fisher information, as well as approximate detailed-balance and Kubo-Martin-Schwinger conditions, ultimately building towards a quantitative theory of thermal metastability.

The assumed hardness of the Shortest Vector Problem in high-dimensional lattices is one of the cornerstones of post-quantum cryptography. The fastest known heuristic attacks on SVP are via so-called sieving methods. While these still take exponential time in the dimension $d$, they are significantly faster than non-heuristic approaches and their heuristic assumptions are verified by extensive experiments. $k$-Tuple sieving is an iterative method where each iteration takes as input a large number of lattice vectors of a certain norm, and produces an equal number of lattice vectors of slightly smaller norm, by taking sums and differences of $k$ of the input vectors. Iterating these ``sieving steps'' sufficiently many times produces a short lattice vector. The fastest attacks (both classical and quantum) are for $k=2$, but taking larger $k$ reduces the amount of memory required for the attack. In this paper we improve the quantum time complexity of 3-tuple sieving from $2^{0.3098 d}$ to $2^{0.2846 d}$, using a two-level amplitude amplification aided by a preprocessing step that associates the given lattice vectors with nearby ``center points'' to focus the search on the neighborhoods of these center points. Our algorithm uses $2^{0.1887d}$ classical bits and QCRAM bits, and $2^{o(d)}$ qubits. This is the fastest known quantum algorithm for SVP when total memory is limited to $2^{0.1887d}$.

We offer the first operational interpretation of the α-z relative entropies, a measure of distinguishability between two quantum states introduced by Jakšić et al. and Audenaert and Datta. We show that these relative entropies appear when formulating conditions for large-sample or catalytic relative majorization of pairs of flat states and certain generalizations of them. Indeed, we show that such transformations exist if and only if all the α-z relative entropies of the two pairs are ordered. In this setting, the α and z parameters are truly independent from each other. These results also yield an expression for the optimal rate of converting one flat state pair into another. Our methods use real-algebraic techniques involving preordered semirings and certain monotone homomorphisms and derivations on them.

In a previous work [Senno et al., Phys. Rev. Lett. 131, 130202 (2023)], we provided a framework to quantify the amount of intrinsic randomness produced by characterized but untrusted prepare-and-measure (P\&M) setups. While the cases of pure state preparations or extremal measurements were shown to be defined by semidefinite programs (SDPs), up until now we were missing computational methods for the general scenario of mixed states and nonextremal measurements. In this work, we present a hierarchy of SDP relaxations to lower bound the device-dependent conditional min-entropy. Benchmarking against known special cases, we find that the first level of the hierarchy already attains the optimal value. We then provide two applications. First, for setups affected by global depolarizing noise, we compute a matching lower bound to the analytical attack derived in [Curran et al., arXiv:2506.22294 (2025)], thus showing its optimality. Finally, we show that restricting the correlations between the P\&M boxes to be classical strictly decreases an adversary's predictive power, already in the most elementary setup of a qubit binary measurement.

Learning properties of quantum states from measurement data is a fundamental challenge in quantum information. The sample complexity of such tasks depends crucially on the measurement primitive. While shadow tomography achieves sample- efficient learning by allowing entangling measurements across many copies, it requires prohibitively deep circuits. At the other extreme, two-copy measurements already yield exponential advantages over single-copy strategies in tasks such as Pauli tomography. In this work we show that such sharp separations extend far beyond the two-copy regime: for every prime k we construct explicit learning tasks of degree k, which are exponentially hard with (k − 1)-copy measurements but efficiently solvable with k- copy measurements. Our protocols are not only sample-efficient but also realizable with shallow circuits. Extending further, we show that such finite-degree tasks ex- ist for all square-free integers k, pointing toward a general principle underlying their existence. Together, our results reveal an infinite hierarchy of multi-copy learning prob- lems, uncovering new phase transitions in sample complexity and underscoring the role of reliable quantum memory as a key resource for exponential quantum advantage

Continuous-variable quantum key distribution (CV QKD) is a promising approach for implementing quantum secured communication using coherent detection and standard optical communication components. In this work, we investigate the relationship between the secret key rate and modulation variance in a CV-QKD system through numerical simulation. The simulation is performed by considering system parameters relevant to our experimental setup, allowing us to estimate the expected key rate behavior as a function of modulation variance. In addition, we experimentally verify the corresponding optical power levels generated by the modulation process, providing a practical connection between the theoretical modulation variance and measurable optical power in the actual system.

Device-independent (DI) cryptography represents the highest level of security, enabling cryp- tographic primitives to be executed safely on uncharacterized devices. Moreover, with successful proof-of-concept demonstrations in randomness expansion, randomness amplification, and quantum key distribution, the field is steadily advancing toward commercial viability. Critical to this continued progression is the development of tighter finite-size security proofs. In this work, we provide a simple method to obtain tighter finite-size security proofs for protocols based on the CHSH game, which is the nonlocality test used in all of the proof-of-concept experiments. We achieve this by analytically solving key-rate optimization problems based on Rényi entropies, providing a simple method to obtain tighter finite-size key rates.

Hardy’s non-locality provides a proof of the incompatibility between quantum mechanics and local realism without using Bell inequalities. While this argument has been extensively studied for two- and three-qubit systems, a detailed analysis of the four-qubit case is still lacking. In this work, we investigate Hardy’s non-locality for a four-qubit system within the standard two-setting framework. We explicitly construct the entangled state satisfying the Hardy conditions and determine the measurement settings that maximize the success probability. Furthermore, we extend the analysis to multipartite qubit systems and investigate how the Hardy success probability behaves as the number of qubits increases. The results indicate a monotonic increase of the Hardy success probability for larger multipartite systems.

The no-cloning theorem in quantum mechanics has been used as a basis for quantum money constructions, which guarantee unconditionally unforgeable currency. Existing schemes, however, either (i) require long-term quantum memory and quantum communication between the user and the bank in order to verify the validity of a bill or (ii) fail to protect user privacy due to the uniqueness of each bill issued by the bank, which can allow its usage to be tracked. We introduce a construction of single-use quantum money that gives users the ability to detect whether the issuing authority is tracking them, employing an auditing procedure for which we prove unconditional security. The use of our scheme does not require long-term quantum memory or quantum communication from the users themselves since their validation is a purely classical operation, making the protocol relatively practical to deploy. We discuss potential applications beyond money, including anonymous one-time pads and voting.