Related papers: One-Way Ticket to Las Vegas and the Quantum Adversary

One-Way Ticket to Las Vegas and the Quantum Adversary

URL: http://arxiv.org/abs/2301.02003v1
Date: Thu, 5 Jan 2023 11:05:22 GMT
Title: One-Way Ticket to Las Vegas and the Quantum Adversary
Authors: Aleksandrs Belovs and Duyal Yolcu
Abstract summary: We show that quantum Las Vegas query complexity is exactly equal to the quantum adversary bound. This is achieved by transforming a feasible solution to the adversary inversion problem into a quantum query algorithm.
Score: 78.33558762484924
License: http://creativecommons.org/licenses/by/4.0/
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.

Related papers

Taming Quantum Time Complexity [45.867051459785976]
We show how to achieve both exactness and thriftiness in the setting of time complexity. We employ a novel approach to the design of quantum algorithms based on what we call transducers.
arXiv Detail & Related papers (2023-11-27T14:45:19Z)
Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
The anticipated applications of quantum computers span across science and industry. We present a survey of several potential application areas of quantum algorithms. We outline the challenges and opportunities in each area in an "end-to-end" fashion.
arXiv Detail & Related papers (2023-10-04T17:53:55Z)
On the Two-sided Permutation Inversion Problem [45.69327512339002]
We study the setting in which the oracle allows for quantum queries to both the forward and inverse direction of the permutation. We prove several theorems connecting the hardness of the resulting variations of the inversion problem. Our results indicate that, perhaps surprisingly, the inversion problem does not become significantly easier when the adversary is granted oracle access to the inverse.
arXiv Detail & Related papers (2023-06-23T18:31:48Z)
Making the cut: two methods for breaking down a quantum algorithm [0.0]
It remains a major challenge to find quantum algorithms that may reach computational advantage in the present era of noisy, small-scale quantum hardware. We identify and characterize two methods of breaking down'' quantum algorithms into rounds of lower (query) depth. We show that for the first problem parallelization offers the best performance, while for the second is the better choice.
arXiv Detail & Related papers (2023-05-17T18:00:06Z)
Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
arXiv Detail & Related papers (2022-12-06T22:01:49Z)
Orthogonal-ansatz VQE: Locating excited states without modifying a cost-function [0.0]
We develop an excited-state VQE solver which trades increasing measurement complexity for increasing circuit complexity. We demonstrate our approach with three distinct ansatze, beginning with a simple single-body example, before generalizing to accommodate the full Hilbert space spanned by all qubits.
arXiv Detail & Related papers (2022-04-09T02:22:09Z)
Efficient Bipartite Entanglement Detection Scheme with a Quantum Adversarial Solver [89.80359585967642]
Proposal reformulates the bipartite entanglement detection as a two-player zero-sum game completed by parameterized quantum circuits. We experimentally implement our protocol on a linear optical network and exhibit its effectiveness to accomplish the bipartite entanglement detection for 5-qubit quantum pure states and 2-qubit quantum mixed states.
arXiv Detail & Related papers (2022-03-15T09:46:45Z)
Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
arXiv Detail & Related papers (2021-07-08T17:59:55Z)
On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$. This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
arXiv Detail & Related papers (2021-06-11T09:43:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.