One-Way Ticket to Las Vegas and the Quantum Adversary

2023/01/05 by Aleksandrs Belovs, Belovs, Aleksandrs, Duyal Yolcu +1 · 4 citations
Computer Science · #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #Quantum-Dot Cellular Automata

paper · pdf · doi:10.48550/arxiv.2301.02003

openalex publication_date 2023/01/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Cited by

• Tight Quantum Time-Space Tradeoffs for Permutation Inversion
• Quantum walks through generalized graph composition
• Amplitude amplification and estimation require inverses
• An adversary bound for quantum signal processing

Related

• Variations on Quantum Adversary
• Applications of the Adversary Method in Quantum Query Algorithms
• The Adversary Bound Revisited: From Optimal Query Algorithms to Optimal Control
• A Brief Introduction to Quantum Query Complexity
• Robust and Space-Efficient Dual Adversary Quantum Query Algorithms