Guesswork of a quantum ensemble
- URL: http://arxiv.org/abs/2012.09350v2
- Date: Fri, 28 Jan 2022 12:23:52 GMT
- Title: Guesswork of a quantum ensemble
- Authors: Michele Dall'Arno, Francesco Buscemi, Takeshi Koshiba
- Abstract summary: We derive analytical solutions of the guesswork problem subject to a finite set of conditions.
As explicit examples, we compute the guesswork for any qubit regular polygonal and polyhedral ensemble.
- Score: 3.867363075280544
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The guesswork of a quantum ensemble quantifies the minimum number of guesses
needed in average to correctly guess the state of the ensemble, when only one
state can be queried at a time. Here, we derive analytical solutions of the
guesswork problem subject to a finite set of conditions, including the
analytical solution for any qubit ensemble with uniform probability
distribution. As explicit examples, we compute the guesswork for any qubit
regular polygonal and polyhedral ensemble.
Related papers
- An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
We analyse the ability of quantum D-Wave annealers to find the maximum clique on a graph, expressed as a QUBO problem.
We propose a decomposition algorithm for the complementary maximum independent set problem, and a graph generation algorithm to control the number of nodes, the number of cliques, the density, the connectivity indices and the ratio of the solution size to the number of other nodes.
arXiv Detail & Related papers (2024-06-11T04:40:05Z) - Approximation Algorithms for Quantum Max-$d$-Cut [42.248442410060946]
The Quantum Max-$d$-Cut problem involves finding a quantum state that maximizes the expected energy associated with the projector onto the antisymmetric subspace of two, $d$-dimensional qudits over all local interactions.
We develop an algorithm that finds product-state solutions of mixed states with bounded purity that achieve non-trivial performance guarantees.
arXiv Detail & Related papers (2023-09-19T22:53:17Z) - On the Measurement attaining the Quantum Guesswork [2.900810893770134]
The guesswork quantifies the minimum cost incurred in guessing the state of an ensemble, when only one state can be queried at a time.
In the classical case, the optimal strategy trivially consists of querying the states in their non-increasing order of posterior probability.
In the quantum case, the most general strategy to obtain the optimal ordering in which to perform the queries consist of a quantum measurement.
arXiv Detail & Related papers (2023-02-14T01:58:57Z) - Sparse random Hamiltonians are quantumly easy [105.6788971265845]
A candidate application for quantum computers is to simulate the low-temperature properties of quantum systems.
This paper shows that, for most random Hamiltonians, the maximally mixed state is a sufficiently good trial state.
Phase estimation efficiently prepares states with energy arbitrarily close to the ground energy.
arXiv Detail & Related papers (2023-02-07T10:57:36Z) - Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
We analyze and optimize an improved quantum algorithm for topological data analysis.
We show that super-quadratic quantum speedups are only possible when targeting a multiplicative error approximation.
We argue that quantum circuits with tens of billions of Toffoli can solve seemingly classically intractable instances.
arXiv Detail & Related papers (2022-09-27T17:56:15Z) - Cycle Index Polynomials and Generalized Quantum Separability Tests [3.481985817302898]
The mixedness of one share of a pure bipartite state determines whether the overall state is a separable, unentangled state.
We derive a family of quantum separability tests, each of which is generated by a finite group.
For all such algorithms, we show that the acceptance probability is determined by the cycle index of the group.
arXiv Detail & Related papers (2022-08-31T02:13:16Z) - Quantum supremacy with spin squeezed atomic ensembles [0.0]
We propose a method to achieve quantum supremacy using ensembles of qubits.
Each ensemble is assumed to be controllable only with its total spin.
We show that the probability distribution of the final measurements quickly approaches a Porter-Thomas distribution.
arXiv Detail & Related papers (2022-04-25T16:42:37Z) - Computing the quantum guesswork: a quadratic assignment problem [6.445605125467573]
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.
arXiv Detail & Related papers (2021-12-03T01:24:57Z) - Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
We consider the populationimation barycenter problem for random probability measures supported on a finite set of points and generated by an online stream of data.
We employ the structure of the problem and obtain a convex-concave saddle-point reformulation of this problem.
In the setting when the distribution of random probability measures is discrete, we propose an optimization algorithm and estimate its complexity.
arXiv Detail & Related papers (2020-06-11T19:40:38Z) - Guesswork with Quantum Side Information [12.043574473965318]
We show that a general guessing strategy is equivalent to performing a single measurement and choosing a guessing strategy.
We evaluate the guesswork for a simple example involving the BB84 states, both numerically and analytically.
arXiv Detail & Related papers (2020-01-10T18:25:37Z) - A refinement of Reznick's Positivstellensatz with applications to
quantum information theory [72.8349503901712]
In Hilbert's 17th problem Artin showed that any positive definite in several variables can be written as the quotient of two sums of squares.
Reznick showed that the denominator in Artin's result can always be chosen as an $N$-th power of the squared norm of the variables.
arXiv Detail & Related papers (2019-09-04T11:46:26Z)
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.