Matilde Baroni
Title: Bounding the asymptotic quantum value of all multipartite
compiled nonlocal games
Abstract: Nonlocal games are a powerful tools to distinguish between correlations possible in classical and quantum worlds. Kalai et al. (STOC’23) proposed a compiler that converts multipartite nonlocal games into interactive protocols with a single prover, relying on cryptographic tools to remove the assumption of physical separation of the players. While quantum completeness and classical soundness of the construction have been established for all multipartite games, quantum soundness is known only in the special case of bipartite games.We prove that Kalai’s compiler indeed achieves quantum soundness for all multipartite compiled nonlocal games, by showing that any correlations that can be generated in the asymptotic case correspond to quantum commuting strategies. Our proof uses techniques from the theory of operator algebras, and relies on a characterisation of sequential operationally no-signalling strategies as quantum commuting operator strategies in the multipartite case, thereby generalising several previous results. On the way, we prove a new chain rule for Radon-Nikodym derivatives of completely positive maps on $C^\ast$-algebras which may be of independent interest.
Claude Crépeau
Title: …And then there were three…
Abstract: In this work we extend the study of local reductions among pseudo-telepathy games initiated in [1] and [2], in the sense that a black-box winning strategy to one game is usable to win another by local players. Our main contribution highlights that there are three different coexisting definitions of the Magic Square game in the literature, and we show that they do not appear to be equivalent in a well defined local sense. Extra care is therefore necessary when authors refer to the magic square game.
Igor Klep
Title: Karush-Kuhn-Tucker first-order optimality conditions for the NPA hierarchy
Abstract: The NPA hierarchy is a cornerstone computational method in quantum information, offering converging upper bounds on the maximum quantum values achievable in Bell scenarios via a sequence of semidefinite programs (SDPs). In this talk we extend the classical Karush-Kuhn-Tucker (KKT) conditions from convex optimization to the NPA hierarchy. This extension leads to a strengthened hierarchy, and the practical utility of the resulting optimality conditions will be demonstrated through computations of local properties of ground states in many-body spin systems and evaluations of maximal quantum violations of Bell inequalities. This is based on joint work https://arxiv.org/abs/2311.18707 with Mateus Araújo, Andrew Garner, Tamás Vértesi, Miguel Navascués
Denis Rochette
Title: Highly symmetric states and multiplayer non‑locality
Abstract: We investigate the extent to which two particles can be maximally entangled when they are also similarly entangled with other particles on a complete graph, focusing on states symmetric under a group action. To that end, we extend the standard notion of n-extendibility to graph extendibility. We formalize graph-extendibility problems as optimization problems, and solve them analytically via representation-theoretic block-diagonalization. Finally, we explore how these highly symmetric and entangled states perform as strategies for extended non-local games, examining whether the same states that saturate extendibility bounds also maximize the quantum value in a multiplayer non-local game.
Isadora Veeren
Title: Quantum Advantage in Distributed Computing
Abstract: In the framework of distributed computing, several processing units must cooperate to solve big problems using local computation and communicating with neighboring units. Since communicating typically takes longer than the step of local computation, the fewer communication rounds needed to achieve the correct answer, the better.
While this model of computation is already a ubiquitous reality for many current tasks (such as online banking, streaming and gaming), a novel research direction studies how to migrate to quantum technologies, where distributed tasks would be performed on quantum networks, with quantum computers doing local computation and communication between neighbors being done through quantum channels.
In this work, we introduce the first local distributed problem, formalized in the structure of a game, that displays an advantage to quantum strategies when compared to classical ones. We put forward an iterated network task based on the GHZ game, where the goal is to reproduce the correlations of the GHZ state. We bound the communication-round complexity of any classical strategy, and provide a quantum strategy that outperforms this classical bound.
Xiangling Xu
Title: Quantitative soundness of compiled Bell games at finite security
Abstract: Compiled Bell games, using Quantum Homomorphic Encryption (QHE) to replace physical separation, allow probing nonlocality with a single untrusted device. While Kalai et al. (STOC’23) showed this compilation preserves quantum advantage over classical strategies, the important aspect of quantum soundness—whether a dishonest quantum prover can exceed the original Bell game’s score—has been characterized for specific games and recently proven qualitatively for all bipartite games (assuming infinitely secure QHE). Nevertheless, quantitative soundness, particularly under finite security, remains a critical open question.
This work establishes the first quantitative soundness bound for all bipartite compiled Bell games at finite security. We show the compiled game score is provably close to the ideal quantum score, provided the convergence rate of a novel sequential Navascués-Pironio-Acín (NPA) hierarchy is known. We further argue for the necessity of this convergence rate information, highlighting an open challenge in QHE correctness for “weakly commuting” registers. Our techniques, involving operator algebras and noncommutative polynomial optimization, also introduce and characterize this sequential NPA hierarchy and its conic dual, potentially of independent interest.
Nagisa Hara <nhara@uottawa.ca>
Title:
A classical proof of quantum knowledge for multi-prover interactive proof systems
Abstract:
In a proof of knowledge (PoK), a verifier becomes convinced that a prover possesses privileged information. In combination with zero-knowledge proof systems, PoKs are an important part of secure protocols such as digital signature schemes and authentication schemes as they enable a prover to demonstrate possession of a certain piece of information (such as a private key or a credential), without revealing it. Formally, A PoK is defined via the existence of an extractor, which is capable of reconstructing the key information that makes a verifier accept, given oracle access to the prover. We extend the concept of a PoK in the setting of a single classical verifier and two quantum provers, and exhibit the PoK property for a non-local game for the local Hamiltonian problem. More specifically, we construct an extractor which, given oracle access to a provers’ strategy that leads to high acceptance probability, is able to reconstruct the ground state of a local Hamiltonian. Our result can be seen as a new form of self-testing, where, in addition to certifying a pre-shared entangled state and the prover’s strategy, the verifier also certifies a local quantum state. This technique thus provides a method to ascertain that a prover has access to a quantum system, in particular, a ground state, thus indicating a new level of verification for a proof of quantumness.
Calvin (Yinchen) Liu <yc5liu@uwaterloo.ca>
Title:
Quantum advantage from measurement-induced entanglement in random shallow circuits
Abstract:
We study random constant-depth quantum circuits in a two-dimensional architecture. While these circuits only produce entanglement between nearby qubits on the lattice, long-range entanglement can be generated by measuring a subset of the qubits of the output state. It is conjectured that this long-range measurement-induced entanglement (MIE) proliferates when the circuit depth is at least a constant critical value. For circuits composed of Haar-random two-qubit gates, it is also believed that this coincides with a quantum advantage phase transition in the classical hardness of sampling from the output distribution. Here we provide evidence for a quantum advantage phase transition in the setting of random Clifford circuits. Our work extends the scope of recent separations between the computational power of constant-depth quantum and classical circuits, demonstrating that this kind of advantage is present in canonical random circuit sampling tasks. In particular, we show that in any architecture of random shallow Clifford circuits, the presence of long-range MIE gives rise to an unconditional quantum advantage. In contrast, any depth-d 2D quantum circuit that satisfies a short-range MIE property can be classically simulated efficiently and with depth O(d). Finally, we introduce a two-dimensional, depth-2, “coarse-grained” circuit architecture, composed of random Clifford gates acting on O(log n) qubits, for which we prove the existence of long-range MIE and establish an unconditional quantum advantage. Based on joint work with Adam Bene Watts, David Gosset, and Mehdi Soleimanifar.
Kieran Mastel <kmastel@uwaterloo.ca>
Title:
The complexity of entangled constraint systems
Abstract:
Entanglement allows for correlations between spatially separated experiments that are not possible classically. One way to study the computational power of entanglement is via nonlocal games. I will discuss my recent works with Eric Culf and William Slofstra on constraint system games, a rich and well studied class of nonlocal games. Different types of perfect entangled strategies for these games can be understood as representations of the algebra of the underlying constraint system. The weighted algebra formalism extends this to non-perfect strategies. Using this formalism we can show that certain classical reductions between constraint systems are sound against quantum provers, which allows us to prove the RE-completeness of some constraint system games and to show that MIP* admits two prover perfect zero knowledge proofs.
Denis Rochette <Denis.Rochette@uottawa.ca>
Title:
Highly symmetric states and multiplayer non‑locality
Abstract:
We investigate the extent to which two particles can be maximally entangled when they are also similarly entangled with other particles on a complete graph, focusing on states symmetric under a group action. To that end, we extend the standard notion of n-extendibility to graph extendibility. We formalize graph-extendibility problems as optimization problems, and solve them analytically via representation-theoretic block-diagonalization. Finally, we explore how these highly symmetric and entangled states perform as strategies for extended non-local games, examining whether the same states that saturate extendibility bounds also maximize the quantum value in a multiplayer non-local game.
Pulkit Sinha <psinha@uwaterloo.ca>
Title:
Dimension Independent and Computationally Efficient Shadow Tomography
Abstract:
We describe a new shadow tomography algorithm that uses n=Θ(sqrt(m)logm/ϵ^2) samples, for m measurements and additive error ϵ, which is independent of the dimension of the quantum state being learned. This stands in contrast to all previously known algorithms that improve upon the naive approach. The sample complexity also has optimal dependence on ϵ. Additionally, this algorithm is efficient in various aspects, including quantum memory usage (possibly even O(1)), gate complexity, classical computation, and robustness to qubit measurement noise. It can also be implemented as a read-once quantum circuit with low quantum memory usage, i.e., it will hold only one copy of ρ in memory, and discard it before asking for a new one, with the additional memory needed being O(m logn). Our approach builds on the idea of using noisy measurements, but instead of focusing on gentleness in trace distance, we focus on the gentleness in shadows, i.e., we show that the noisy measurements do not significantly perturb the expected values.
Sebastian Zur <sebastian.zur@cwi.nl>
Title:
The compressed oracle is a worthy adversary
Abstract:
While it is fascinating to explore what quantum computers are capable of, it is equally important to study their limitations. One way to do this is by proving explicit lower bounds on the quantum query complexity of computational problems.
One of the frameworks to prove these lower bounds is the compressed oracle technique [Zha19], which can be used to derive quantum query lower bounds for problems where a quantum algorithm interacts with a quantum oracle that accesses a random function. This framework has proven to be very useful and convenient to use, since deriving a lower bound reduces to mostly combinatorial arguments. It is unclear, however, how this frameworks compares with the more established lower bound methods for quantum query complexity.
In this talk, we show how the compressed oracle technique can be reduced to the multiplicative adversary method [Spa08] and discuss how this could give insights into generalising the compressed oracle technique to go beyond random functions.
Joint work with Stacey Jeffery.
Arthur Braida <arthur.braida@irif.fr>
Title: Unstructured Adiabatic Quantum Optimization: Optimality with Limitations
Abstract:
In the circuit model of quantum computing, amplitude amplification techniques can be used to find solutions to NP-hard problems defined on $n$-bits in time $\text{poly}(n) 2^{n/2}$. In this work, we investigate whether such general statements can be made for adiabatic quantum optimization, as provable results regarding its performance are mostly unknown. Although a lower bound of $\Omega(2^{n/2})$ has existed in such a setting for over a decade, a purely adiabatic algorithm with this running time has been absent. We show that adiabatic quantum optimization using an unstructured search approach results in a running time that matches this lower bound (up to a polylogarithmic factor) for a broad class of classical local spin Hamiltonians. For this, it is necessary to bound the spectral gap throughout the adiabatic evolution and compute beforehand the position of the avoided crossing with sufficient precision so as to adapt the adiabatic schedule accordingly. However, we show that the position of the avoided crossing is approximately given by a quantity that depends on the degeneracies and inverse gaps of the problem Hamiltonian and is NP-hard to compute even within a low additive precision. Furthermore, computing it exactly (or nearly exactly) is \#P-hard. Our work indicates a possible limitation of adiabatic quantum optimization algorithms, leaving open the question of whether provable Grover-like speed-ups can be obtained for any optimization problem using this approach.
Joint work with Shantanav Chakraborty, Alapan Chaudhuri, Joseph Cunningham, Rutvij Menavlikar, Leonardo Novo, Jérémie Roland.
André Chailloux <andre.chailloux@inria.fr>
Title:
Quantum advantage from soft decoders
Abstract:
In the last years, Regev’s reduction has been used as a quantum algorithmic tool for providing a quantum advantage for variants of the decoding problem. Following this line of work, the authors of [JSW+24] have recently come up with a quantum algorithm called Decoded Quantum Interferometry that is able to solve in polynomial time several optimization problems. They study in particular the Optimal Polynomial Interpolation (OPI) problem, which can be seen as a decoding problem on Reed-Solomon codes. In this work, we provide strong improvements for some instantiations of the OPI problem. The most notable improvements are for the ISIS∞ problem (originating from lattice-based cryptography) on Reed-Solomon codes but we also study different constraints for OPI. Our results provide natural and convincing decoding problems for which we believe to have a quantum advantage. Our proof techniques involve the use of a soft decoder for Reed-Solomon codes, namely the decoding algorithm from Koetter and Vardy [KV03]. In order to be able to use this decoder in the setting of Regev’s reduction, we provide a novel generic reduction from a syndrome decoding problem to a coset sampling problem, providing a powerful and simple to use theorem, which generalizes previous work and is of independent interest. We also provide an extensive study of OPI using the Koetter and Vardy algorithm.
Joint work with Jean-Pierre Tillich.