410 citations · 413 across the 4 of their papers we have counts for
6 papers · 1 filter
Unconditional quantum advantage with noisy planar architectures
Libor Caha, Robert Koenig, Louis Paletta
We consider quantum devices restricted to local operations in 2D and subject to local stochastic noise below a constant threshold. We show that such circuits are computationally mo…
Parallel classical simulation of noisy shallow circuits: no quantum advantage in 1D
Robert Koenig, Marco Tomamichel
We consider quantum circuits consisting of layers of nearest-neighbor two-qubit gates acting on qubits arranged on a line, where every qubit is independently depolarized wi…
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…
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…
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…
Quantum advantage with shallow circuits
Sergey Bravyi, David Gosset, Robert Koenig
We prove that constant-depth quantum circuits are more powerful than their classical counterparts. To this end we introduce a non-oracular version of the Bernstein-Vazirani problem…