Robust and Space-Efficient Dual Adversary Quantum Query Algorithms
- URL: http://arxiv.org/abs/2306.15040v1
- Date: Mon, 26 Jun 2023 19:59:30 GMT
- Title: Robust and Space-Efficient Dual Adversary Quantum Query Algorithms
- Authors: Michael Czekanski, Shelby Kimmel, and R. Teal Witter
- Abstract summary: General adversary dual is a powerful tool in quantum computing.
It gives a query-optimal bounded-error quantumlemma deciding any Boolean function.
We develop a robust dual adversary algorithm that can handle approximately satisfied constraints.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The general adversary dual is a powerful tool in quantum computing because it
gives a query-optimal bounded-error quantum algorithm for deciding any Boolean
function. Unfortunately, the algorithm uses linear qubits in the worst case,
and only works if the constraints of the general adversary dual are exactly
satisfied. The challenge of improving the algorithm is that it is brittle to
arbitrarily small errors since it relies on a reflection over a span of
vectors. We overcome this challenge and build a robust dual adversary algorithm
that can handle approximately satisfied constraints. As one application of our
robust algorithm, we prove that for any Boolean function with polynomially many
1-valued inputs (or in fact a slightly weaker condition) there is a
query-optimal algorithm that uses logarithmic qubits. As another application,
we prove that numerically derived, approximate solutions to the general
adversary dual give a bounded-error quantum algorithm under certain conditions.
Further, we show that these conditions empirically hold with reasonable
iterations for Boolean functions with small domains. We also develop several
tools that may be of independent interest, including a robust approximate
spectral gap lemma, a method to compress a general adversary dual solution
using the Johnson-Lindenstrauss lemma, and open-source code to find solutions
to the general adversary dual.
Related papers
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP)
We generalize the SDP-inspired quantum algorithm to sum-of-squares.
Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
arXiv Detail & Related papers (2024-08-14T19:04:13Z) - Generalized quantum Arimoto-Blahut algorithm and its application to
quantum information bottleneck [55.22418739014892]
We generalize the quantum Arimoto-Blahut algorithm by Ramakrishnan et al.
We apply our algorithm to the quantum information bottleneck with three quantum systems.
Our numerical analysis shows that our algorithm is better than their algorithm.
arXiv Detail & Related papers (2023-11-19T00:06:11Z) - 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) - The Adversary Bound Revisited: From Optimal Query Algorithms to Optimal
Control [0.0]
This note complements the paper "One-Way Ticket to Las Vegas and the Quantum Adversary"
I develop the ideas behind the adversary bound - universal algorithm duality therein in a different form, using the same perspective as Barnum-Saks-Szegedy.
arXiv Detail & Related papers (2022-11-29T15:25:45Z) - Quantum Search Algorithm for Binary Constant Weight Codes [3.3555130013686014]
A binary constant weight code is a type of error-correcting code with a wide range of applications.
We propose a quantum search algorithm for binary constant weight codes.
arXiv Detail & Related papers (2022-11-09T01:57:11Z) - Quantum Sparse Coding [5.130440339897477]
We develop a quantum-inspired algorithm for sparse coding.
The emergence of quantum computers and Ising machines can potentially lead to more accurate estimations.
We conduct numerical experiments with simulated data on Lightr's quantum-inspired digital platform.
arXiv Detail & Related papers (2022-09-08T13:00:30Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits.
Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit.
We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
arXiv Detail & Related papers (2022-06-30T03:15:23Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle.
We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm.
We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
arXiv Detail & Related papers (2022-05-26T20:32:36Z) - Hardness of Random Optimization Problems for Boolean Circuits,
Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
We show that families of algorithms fail to produce nearly optimal solutions with high probability.
For the case of Boolean circuits, our results improve the state-of-the-art bounds known in circuit complexity theory.
arXiv Detail & Related papers (2020-04-25T05:45:59Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.