Computing the quantum guesswork: a quadratic assignment problem
- URL: http://arxiv.org/abs/2112.01666v2
- Date: Fri, 25 Aug 2023 11:59:56 GMT
- Title: Computing the quantum guesswork: a quadratic assignment problem
- Authors: Michele Dall'Arno, Francesco Buscemi, Takeshi Koshiba
- Abstract summary: Previous approaches to the computation of the guesswork were based on standard semi-definite programming techniques.
We show that computing the quantum guesswork of qubit ensembles with uniform probability distribution leads to a more-than-quadratic speedup.
As examples, we compute the guesswork of regular and quasi-regular sets of qubit states.
- Score: 6.445605125467573
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The quantum guesswork quantifies the minimum number of queries needed to
guess the state of a quantum ensemble if one is allowed to query only one state
at a time. Previous approaches to the computation of the guesswork were based
on standard semi-definite programming techniques and therefore lead to
approximated results. In contrast, we show that computing the quantum guesswork
of qubit ensembles with uniform probability distribution corresponds to solving
a quadratic assignment problem and we provide an algorithm that, upon the input
of any qubit ensemble over a discrete ring, after finitely many steps outputs
the exact closed-form expression of its guesswork. While in general the
complexity of our guesswork-computing algorithm is factorial in the number of
states, our main result consists of showing a more-than-quadratic speedup for
symmetric ensembles, a scenario corresponding to the three-dimensional analog
of the maximization version of the turbine-balancing problem. To find such
symmetries, we provide an algorithm that, upon the input of any point set over
a discrete ring, after finitely many steps outputs its exact symmetries. The
complexity of our symmetries-finding algorithm is polynomial in the number of
points. As examples, we compute the guesswork of regular and quasi-regular sets
of qubit states.
Related papers
- A quantum speedup algorithm for TSP based on quantum dynamic programming with very few qubits [0.0]
We propose a quantum algorithm to generate the uniform superposition state of all N-length Hamiltonian cycles as an initial state within gate complexity.
Compared to some algorithms that theoretically have lower query complexities but lack practical implementation solutions, our algorithm has feasible circuit implementation.
arXiv Detail & Related papers (2025-02-12T23:58:25Z) - Quantum algorithm for approximating the expected value of a random-exist quantified oracle [0.0]
Quantum amplitude amplification and estimation have shown quadratic speedups to unstructured search and estimation tasks.
We show that a coherent combination of these quantum algorithms also provides a quadratic speedup to calculating the expectation value of a random-exist quantified oracle.
arXiv Detail & Related papers (2024-11-30T19:42:08Z) - Halving the Cost of Quantum Algorithms with Randomization [0.138120109831448]
Quantum signal processing (QSP) provides a systematic framework for implementing a transformation of a linear operator.
Recent works have developed randomized compiling, a technique that promotes a unitary gate to a quantum channel.
Our algorithm implements a probabilistic mixture of randomizeds, strategically chosen so that the average evolution converges to that of a target function, with an error quadratically smaller than that of an equivalent individual.
arXiv Detail & Related papers (2024-09-05T17:56:51Z) - 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) - When can you trust feature selection? -- I: A condition-based analysis
of LASSO and generalised hardness of approximation [49.1574468325115]
We show how no (randomised) algorithm can determine the correct support sets (with probability $> 1/2$) of minimisers of LASSO when reading approximate input.
For ill-posed inputs, the algorithm runs forever, hence, it will never produce a wrong answer.
For any algorithm defined on an open set containing a point with infinite condition number, there is an input for which the algorithm will either run forever or produce a wrong answer.
arXiv Detail & Related papers (2023-12-18T18:29:01Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
We design, implement, and evaluate three hybrid quantum k-Means algorithms.
We exploit quantum phenomena to speed up the computation of distances.
We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
arXiv Detail & Related papers (2022-12-13T16:04:16Z) - 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) - Using Shor's algorithm on near term Quantum computers: a reduced version [0.0]
We introduce a reduced version of Shor's algorithm that proposes a step forward in increasing the range of numbers that can be factorized on noisy Quantum devices.
In particular, we have found noteworthy results in most cases, often being able to factor the given number with only one of the proposed algorithm.
arXiv Detail & Related papers (2021-12-23T15:36:59Z) - Polynomial T-depth Quantum Solvability of Noisy Binary Linear Problem:
From Quantum-Sample Preparation to Main Computation [0.0]
We present a complete analysis of the quantum solvability of the noisy binary linear problem (NBLP)
We show that the cost of solving the NBLP can be in the problem size, at the expense of an exponentially increasing logical qubits.
arXiv Detail & Related papers (2021-09-23T07:46:20Z) - Random quantum circuits anti-concentrate in log depth [118.18170052022323]
We study the number of gates needed for the distribution over measurement outcomes for typical circuit instances to be anti-concentrated.
Our definition of anti-concentration is that the expected collision probability is only a constant factor larger than if the distribution were uniform.
In both the case where the gates are nearest-neighbor on a 1D ring and the case where gates are long-range, we show $O(n log(n)) gates are also sufficient.
arXiv Detail & Related papers (2020-11-24T18:44:57Z)
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.