Xavier Coiteux-Roy

As early as 1935, Schrödinger recognized entanglement as “not one but rather the characteristic trait of quantum mechanics, the one that enforces its entire departure from classical lines of thought.” Indeed, most remarkable phenomena in quantum information science, such as quantum computing and quantum teleportation, spring from clever uses of entanglement. Among them, pseudotelepathy enables two or more players to win systematically at some cooperative games with no need for communication between them, a restriction that would make the task impossible in a classical world. We investigate the power of multipartite entanglement for pseudotelepathy. Some known games that can be won with tripartite entanglement cannot be won with bipartite entanglement, but they can be won with bipartite nonsignaling resources such as the so-called Popescu–Rohrlich nonlocal box. We exhibit a five-player game that can be won with tripartite entanglement, but not with arbitrary bipartite nonsignaling resources even in the presence of arbitrary five-partite classical resources. This illustrates both the power of bipartite nonsignaling resources (over bipartite entanglement) and the even superior power of tripartite entanglement.

A common starting point of traditional quantum algorithm design is the notion of a universal quantum computer with a scalable number of qubits. This convenient abstraction mirrors classical computations manipulating bits. It allows for a device-independent development of algorithmic primitives. Here we argue that an alternative approach centered on the physical setup can yield great benefits. As an example, we consider hybrid qubit-oscillator systems with linear optics operations augmented by certain qubit-controlled Gaussian unitaries. The continuous variable Fourier transform and certain arithmetic operations have native realizations in such systems. We put this to algorithmic use and give a polynomial-time quantum factoring algorithm which uses only one qubit and three oscillators, independent of the number being factored.

We initiate the study of state complexity for continuous-variable quantum systems. Concretely, we consider a setup with bosonic modes and auxiliary qubits, where available operations include Gaussian one- and two-mode operations and single- and two-qubit operations as well as qubit-controlled phase-space displacements. We define the (approximate) complexity of a bosonic state by the minimum size of a circuit that prepares an approximation to the state in trace distance. We propose a new circuit which prepares an approximate Gottesman-Kitaev-Preskill (GKP) state | G K P κ , Δ ⟩ . Here, κ − 2 is the variance of the envelope, and Δ 2 is the variance of the individual peaks. We show that the circuit accepts with constant probability and—conditioned on acceptance—the output state is polynomially close in ( κ , Δ ) to the state | G K P κ , Δ ⟩ . The size of our circuit is linear in ( log 1 / κ , log 1 / Δ ) . To our knowledge, this is the first protocol for GKP-state preparation with fidelity guarantees for the prepared state. We also show converse bounds, establishing that the linear circuit-size dependence of our construction is optimal. This fully characterizes the complexity of GKP states.

The notion of genuinely multipartite nonlocality (GMNL) was introduced to conceptualize the fact that nonclassical resources involving more than two parties in a nontrivial way may be needed to account for some quantum correlations. In this letter, we first recall the contradictions inherent to the historical definition of GMNL. Second, we turn to one of its redefinitions, called Local-Operations-and-Shared-Randomness GMNL (LOSR-GMNL), proving that all caterpillar graph states (including linear cluster states) have this second property. Finally, we conceptualize a third, alternative definition, which we call Local-Operations-and-Neighbour-Communication GMNL (LONC-GMNL), that is adapted to situations in which short-range communication between some parties might occur. We show that linear cluster states do not have this third property, while GHZ states do. Beyond its technical content, our letter illustrates that rigorous conceptual work is needed before applying the concepts of multipartite nonlocality or entanglement to benchmark the nonclassicality of some experimentally-produced quantum systems.

We give an almost complete characterization of the hardness of c-coloring χ-chromatic graphs with distributed algorithms, for a wide range of models of distributed computing. In particular, we show that these problems do not admit any distributed quantum advantage. To do that: We give a new distributed algorithm that finds a c-coloring in χ-chromatic graphs in Õ(n^1/α) rounds, with α = ⌊c−1/χ − 1⌋. We prove that any distributed algorithm for this problem requires Ω(n^1/α) rounds. Our upper bound holds in the classical, deterministic LOCAL model, while the near-matching lower bound holds in the non-signaling model. This model, introduced by Arfaoui and Fraigniaud in 2014, captures all models of distributed graph algorithms that obey physical causality; this includes not only classical deterministic LOCAL and randomized LOCAL but also quantum-LOCAL, even with a pre-shared quantum state. We also show that similar arguments can be used to prove that, e.g., 3-coloring 2-dimensional grids or c-coloring trees remain hard problems even for the non-signaling model, and in particular do not admit any quantum advantage. Our lower-bound arguments are purely graph-theoretic at heart; no background on quantum information theory is needed to establish the proofs.