25 citations · 64 across the 12 of their papers we have counts for
14 papers
Distributed Quantum Algorithms Cannot Color Cycles with Probability 1
Xavier Coiteux-Roy, Maxime Flin, Carlos de Gois +3
We prove that any distributed quantum algorithm that finds a -coloring with probability in a cycle of anonymous identical computers has to be global, that is, it needs $Ω(n)…
Factoring an integer with three oscillators and a qubit
Lukas Brenner, Libor Caha, Xavier Coiteux-Roy +1
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…
Distributed Quantum Advantage for Local Problems
Alkida Balliu, Sebastian Brandt, Xavier Coiteux-Roy +10
We present the first local problem that shows a super-constant separation between the classical randomized LOCAL model of distributed computing and its quantum counterpart. By prio…
The complexity of Gottesman-Kitaev-Preskill states
Lukas Brenner, Libor Caha, Xavier Coiteux-Roy +1
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 operatio…
The genuinely multipartite nonlocality of graph states is model-dependent
Xavier Coiteux-Roy, Owidiusz Makuta, Fionnuala Curran +2
Bell's theorem proves that some quantum state correlations can only be explained by bipartite non-classical resources. The notion of genuinely multipartite nonlocality (GMNL) was l…
Online Locality Meets Distributed Quantum Computing
Amirreza Akbari, Xavier Coiteux-Roy, Francesco d'Amore +8
We connect three distinct lines of research that have recently explored extensions of the classical LOCAL model of distributed computing: A. distributed quantum computing and non-s…
A colossal advantage: 3D-local noisy shallow quantum circuits defeat unbounded fan-in classical circuits
Libor Caha, Xavier Coiteux-Roy, Robert Koenig
We present a computational problem with the following properties: (i) Every instance can be solved with near-certainty by a constant-depth quantum circuit using only nearest-neighb…
No distributed quantum advantage for approximate graph coloring
Xavier Coiteux-Roy, Francesco d'Amore, Rishikesh Gajjala +7
We give an almost complete characterization of the hardness of -coloring -chromatic graphs with distributed algorithms, for a wide range of models of distributed computing. I…
Single-qubit gate teleportation provides a quantum advantage
Libor Caha, Xavier Coiteux-Roy, Robert Koenig
Gate-teleportation circuits are arguably among the most basic examples of computations believed to provide a quantum computational advantage: In seminal work [Quantum Inf. Comput.,…
Experimental Demonstration that No Tripartite-Nonlocal Causal Theory Explains Nature's Correlations
Huan Cao, Marc-Olivier Renou, Chao Zhang +7
Quantum theory predicts the existence of genuinely tripartite-entangled states, which cannot be obtained from local operations over any bipartite entangled states and unlimited sha…
No Bipartite-Nonlocal Causal Theory Can Explain Nature's Correlations
Xavier Coiteux-Roy, Elie Wolfe, Marc-Olivier Renou
We show that some tripartite quantum correlations are inexplicable by any causal theory involving bipartite nonclassical common causes and unlimited shared randomness. This constit…
Any Physical Theory of Nature Must Be Boundlessly Multipartite Nonlocal
Xavier Coiteux-Roy, Elie Wolfe, Marc-Olivier Renou
We introduce the class of Genuinely Local Operation and Shared Randomness (LOSR) Multipartite Nonlocal correlations, that is, correlations between N parties that cannot be obtained…
Can't Touch This: unconditional tamper evidence from short keys
Bart van der Vecht, Xavier Coiteux-Roy, Boris Skoric
Storing data on an external server with information-theoretic security, while using a key shorter than the data itself, is impossible. As an alternative, we propose a scheme that a…
The Korteweg-de Vries equation and its symmetry-preserving discretization
Alexander Bihlo, Xavier Coiteux-Roy, Pavel Winternitz
The Korteweg-de Vries equation is one of the most important nonlinear evolution equations in the mathematical sciences. In this article invariant discretization schemes are constru…