Guesswork with Quantum Side Information
- URL: http://arxiv.org/abs/2001.03598v3
- Date: Fri, 24 Dec 2021 00:19:22 GMT
- Title: Guesswork with Quantum Side Information
- Authors: Eric P. Hanson, Vishal Katariya, Nilanjana Datta, Mark M. Wilde
- Abstract summary: 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.
- Score: 12.043574473965318
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: What is the minimum number of guesses needed on average to correctly guess a
realization of a random variable? The answer to this question led to the
introduction of the notion of a quantity called guesswork by Massey in 1994,
which can be viewed as an alternate security criterion to entropy. In this
paper, we consider the guesswork in the presence of quantum side information,
and show that a general sequential guessing strategy is equivalent to
performing a single measurement and choosing a guessing strategy from the
outcome. We use this result to deduce entropic one-shot and asymptotic bounds
on the guesswork in the presence of quantum side information, and to formulate
a semi-definite program (SDP) to calculate the quantity. We evaluate the
guesswork for a simple example involving the BB84 states, both numerically and
analytically, and prove a continuity result that certifies the security of
slightly imperfect key states when the guesswork is used as the security
criterion.
Related papers
- How much secure randomness is in a quantum state? [0.0]
How much cryptographically-secure randomness can be extracted from a quantum state?
We consider a general adversarial model that allows for an adversary who has quantum side-information about both the source and the measurement device.
arXiv Detail & Related papers (2024-10-21T19:16:56Z) - Quantum Non-Identical Mean Estimation: Efficient Algorithms and Fundamental Limits [15.89518426969296]
We investigate quantum algorithms and lower bounds for mean estimation given query access to non-identically distributed samples.
On the one hand, we give quantum mean estimators with quadratic quantum speed-up given samples from different bounded or sub-Gaussian random variables.
On the other hand, we prove that, in general, it is impossible for any quantum algorithm to achieve quadratic speed-up over the number of classical samples needed.
arXiv Detail & Related papers (2024-05-21T14:42:39Z) - 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) - Testing randomness of series generated in Bell's experiment [62.997667081978825]
We use a toy fiber optic based setup to generate binary series, and evaluate their level of randomness according to Ville principle.
Series are tested with a battery of standard statistical indicators, Hurst, Kolmogorov complexity, minimum entropy, Takensarity dimension of embedding, and Augmented Dickey Fuller and Kwiatkowski Phillips Schmidt Shin to check station exponent.
The level of randomness of series obtained by applying Toeplitz extractor to rejected series is found to be indistinguishable from the level of non-rejected raw ones.
arXiv Detail & Related papers (2022-08-31T17:39:29Z) - 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) - Tight Exponential Analysis for Smoothing the Max-Relative Entropy and
for Quantum Privacy Amplification [56.61325554836984]
The max-relative entropy together with its smoothed version is a basic tool in quantum information theory.
We derive the exact exponent for the decay of the small modification of the quantum state in smoothing the max-relative entropy based on purified distance.
arXiv Detail & Related papers (2021-11-01T16:35:41Z) - About the description of physical reality of Bell's experiment [91.3755431537592]
A hidden variables model complying with the simplest form of Local Realism was recently introduced.
It reproduces Quantum Mechanics' predictions for an even ideally perfect Bell's experiment.
A new type of quantum computer does not exist yet, not even in theory.
arXiv Detail & Related papers (2021-09-06T15:55:13Z) - Geometry of Banach spaces: a new route towards Position Based
Cryptography [65.51757376525798]
We study Position Based Quantum Cryptography (PBQC) from the perspective of geometric functional analysis and its connections with quantum games.
The main question we are interested in asks for the optimal amount of entanglement that a coalition of attackers have to share in order to compromise the security of any PBQC protocol.
We show that the understanding of the type properties of some more involved Banach spaces would allow to drop out the assumptions and lead to unconditional lower bounds on the resources used to attack our protocol.
arXiv Detail & Related papers (2021-03-30T13:55:11Z) - Guesswork of a quantum ensemble [3.867363075280544]
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.
arXiv Detail & Related papers (2020-12-17T01:47:18Z) - 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.