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

• Complement Sampling: Provable, Verifiable and NISQable Quantum Advantage in Sample Complexity [0.0]
  We give a simple quantum algorithm that uses only a single quantum sample -- a single copy of the uniform superposition over elements of the subset. In a sample-to-sample setting, quantum computation can achieve the largest possible separation over classical computation.
  arXiv  Detail & Related papers  (2025-02-12T19:00:10Z)
• Conditional Distribution Quantization in Machine Learning [83.54039134248231]
  Conditional expectation mathbbE(Y mid X) often fails to capture the complexity of multimodal conditional distributions mathcalL(Y mid X) We propose using n-point conditional quantizations--functional mappings of X that are learnable via gradient descent--to approximate mathcalL(Y mid X)
  arXiv  Detail & Related papers  (2025-02-11T00:28:24Z)
• Reducing the sampling complexity of energy estimation in quantum many-body systems using empirical variance information [45.18582668677648]
  We consider the problem of estimating the energy of a quantum state preparation for a given Hamiltonian in Pauli decomposition. We construct an adaptive estimator using the state's actual variance.
  arXiv  Detail & Related papers  (2025-02-03T19:00:01Z)
• Single-Timescale Multi-Sequence Stochastic Approximation Without Fixed Point Smoothness: Theories and Applications [33.21958331056391]
  Multi-sequence approximation (SA) that involves multiple coupled sequences, known as multiple-sequence SA (MSSA), finds diverse applications in the fields of signal processing and machine learning. This paper establishes tighter single-timescale analysis for MSSA, without assuming smoothness of the fixed points. Applying these theoretical findings to bilevel optimization and communication-efficient distributed learning offers relaxed assumptions and/or simpler algorithms with performance guarantees.
  arXiv  Detail & Related papers  (2024-10-17T16:39:53Z)
• Absolute dimensionality of quantum ensembles [41.94295877935867]
  The dimension of a quantum state is traditionally seen as the number of superposed distinguishable states in a given basis. We propose an absolute, i.e.basis-independent, notion of dimensionality for ensembles of quantum states.
  arXiv  Detail & Related papers  (2024-09-03T09:54:15Z)
• 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)
• 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)
• 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.