Dominik Leichtle

Matilde Baroni, Igor Klep, Dominik Leichtle et al.

Compiled nonlocal games transfer the power of Bell-type multi-prover tests into a single-device setting by replacing spatial separation with cryptography. Concretely, the KLVY compiler (STOC'23) maps any multi-prover game to an interactive single-prover protocol, using quantum homomorphic encryption. A crucial security property of such compilers is quantum soundness, which ensures that a dishonest quantum prover cannot exceed the original game's quantum value. For practical cryptographic implementations, this soundness must be quantitative, providing concrete bounds rather than merely asymptotic. While quantitative quantum soundness has been established for the KLVY compiler in the bipartite case, it has only been shown asymptotically for multipartite games. This is a significant gap, as multipartite nonlocality exhibits phenomena with no bipartite analogue, and the difficulty of enforcing space-like separation makes single-device compilation especially compelling. This work closes this gap by providing quantitative upper bounds for all multipartite compiled nonlocal games via a new sequential NPA-like hierarchy. In particular, finite-level convergence yields quantitative quantum soundness with respect to the commuting quantum value, and flat optimality yields the same with respect to the tensor-product quantum value. On the way, we introduce an NPA-like hierarchy for quantum instruments and prove its completeness, thereby characterizing correlations from operationally-non-signaling sequential strategies. This NPA-like hierarchy can be seen to complement previous multipartite generalizations of the S-G-HJW purification theorem, which takes a central role in quantum information, nonlocality, and contextuality. We further develop novel geometric arguments for the decomposition of sequential strategies into their signaling and non-signaling parts, which might be of independent interest.

Alex Rice, Dominik Leichtle, Kim Worrall et al.

Many production quantum programming languages represent hybrid quantum computations by extending a classical base language with a quantum effect, where qubits are addressed by reference, and quantum operations are understood to mutate some external quantum state. However, the semantics of this view of quantum computation remains underdeveloped, especially when the language allows mid-circuit measurements and non-termination. In this work, we provide a general method for building denotational semantics for such languages, by defining the quantum orchestra monad, which precisely captures this style of quantum effect. The monad has a concrete presentation, being based on the formalism of quantum instruments, a common tool in quantum information theory for capturing the action of a quantum process along with its classical outcomes. It acts on the category DCPO, and so enables the interpretation of divergent hybrid programs. The quantum orchestra monad serves as a natural extension of both the classical state monad and the probabilistic powerdomain monad. We investigate some of the subtleties present when trying to naïvely extend these definitions to the quantum non-commutative case.

Robert I. Booth, Dominik Leichtle, Alex Rice et al.

We study the composition of classically-controlled quantum instruments--the natural quantum analogue of Markov kernels. Classically, Markov kernels compose by integrating one kernel against another. Defining this composition for quantum instruments with continuous outcomes requires an integral of quantum channel-valued functions with respect to a quantum instrument. We construct this integral in the Heisenberg picture using the Okamura-Ozawa normal extension to a von Neumann tensor product. This integral recovers the expected finite formula, preserves normal complete positivity and subunitality, and provides the multiplication for a monad governing the composition of quantum instruments. As an immediate consequence, we identify the category of quantum Markov kernels as the Kleisli category of this monad.

Elham Kashefi, Dominik Leichtle, Luka Music et al.

Recent experimental achievements motivate an ever-growing interest from companies starting to feel the limitations of classical computing. Yet, in light of ongoing privacy scandals, the future availability of quantum computing through remotely accessible servers pose peculiar challenges: Clients with quantum-limited capabilities want their data and algorithms to remain hidden, while being able to verify that their computations are performed correctly. Research in blind and verifiable delegation of quantum computing attempts to address this question. However, available techniques suffer not only from high overheads but also from over-sensitivity: When running on noisy devices, imperfections trigger the same detection mechanisms as malicious attacks, resulting in perpetually aborted computations. Hence, while malicious quantum computers are rendered harmless by blind and verifiable protocols, inherent noise severely limits their usability. We address this problem with an efficient, robust, blind, verifiable scheme to delegate deterministic quantum computations with classical inputs and outputs. We show that: 1) a malicious Server can cheat at most with an exponentially small success probability; 2) in case of sufficiently small noise, the protocol succeeds with a probability exponentially close to 1; 3) the overhead is barely a polynomial number of repetitions of the initial computation interleaved with test runs requiring the same physical resources in terms of memory and gates; 4) the amount of tolerable noise, measured by the probability of failing a test run, can be as high as 25% for some computations and will be generally bounded by 12.5% when using a planar graph resource state. The key points are that security can be provided without universal computation graphs and that, in our setting, full fault-tolerance is not needed to amplify the confidence level exponentially close to 1.