Cold atoms on a one-way ticket

Elizabeth A. Schoene

Anonymous

Aleksandrs Belovs, Duyal Yolcu

We propose a new definition of quantum Las Vegas query complexity. We show that it is exactly equal to the quantum adversary bound. This is achieved by a new and very simple way of transforming a feasible solution to the adversary optimisation problem into a quantum query algorithm. This allows us to generalise the bound to include unidirectional access, multiple input oracles, and input oracles that are not unitary. As an application, we demonstrate a separation between unidirectional and bidirectional access to an input oracle for a rather natural unitary permutation inversion problem.

Researchers at the Institut d'Optique Graduate School at the CNRS and Université Paris-Saclay in France have developed a new way to rearrange cold atoms one-by-one in fully ordered arrays.