Generating Randomness from a Computable, Non-random Sequence of Qubits
- URL: http://arxiv.org/abs/2005.00207v1
- Date: Fri, 1 May 2020 04:09:49 GMT
- Title: Generating Randomness from a Computable, Non-random Sequence of Qubits
- Authors: Tejas Bhojraj (Department of Mathematics, University of
Wisconsin-Madison)
- Abstract summary: Nies and Scholz introduced the notion of a state to describe an infinite sequence of qubits.
We formalize how'measurement' of a state in a basis induces a probability measure on Cantor space.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Nies and Scholz introduced the notion of a state to describe an infinite
sequence of qubits and defined quantum-Martin-Lof randomness for states,
analogously to the well known concept of Martin-L\"of randomness for elements
of Cantor space (the space of infinite sequences of bits). We formalize how
'measurement' of a state in a basis induces a probability measure on Cantor
space. A state is 'measurement random' (mR) if the measure induced by it, under
any computable basis, assigns probability one to the set of Martin-L\"of
randoms. Equivalently, a state is mR if and only if measuring it in any
computable basis yields a Martin-L\"of random with probability one. While
quantum-Martin-L\"of random states are mR, the converse fails: there is a mR
state, x which is not quantum-Martin-L\"of random. In fact, something stronger
is true. While x is computable and can be easily constructed, measuring it in
any computable basis yields an arithmetically random sequence with probability
one. I.e., classical arithmetic randomness can be generated from a computable,
non-quantum random sequence of qubits.
Related papers
- Verifying randomness in sets of quantum states via observables [4.289151408389622]
We show that Haar-randomness is connected to the Dirichlet distribution, and provide a closed-form expression, and simple bounds of the statistical moments.
We generalize this metric to permutation- and unitary-equivalent observables, ensuring that if the extended average randomness is compatible with a Haar-random distribution, then the set of states is approximately Haar-random.
arXiv Detail & Related papers (2024-04-24T21:11:58Z) - Quantifying the intrinsic randomness in sequential measurements [6.606799868136239]
In this paper, we define quantum intrinsic randomness in sequential measurements.
We quantify randomness in the Collins-Gisin-Linden-Massar-Popescu (CGLMP) inequality sequential scenario.
arXiv Detail & Related papers (2024-01-12T09:44:17Z) - Pseudorandom and Pseudoentangled States from Subset States [49.74460522523316]
A subset state with respect to $S$, a subset of the computational basis, is [ frac1sqrt|S|sum_iin S |irangle.
We show that for any fixed subset size $|S|=s$ such that $s = 2n/omega(mathrmpoly(n))$ and $s=omega(mathrmpoly(n))$, a random subset state is information-theoretically indistinguishable from a Haar random state even provided
arXiv Detail & Related papers (2023-12-23T15:52:46Z) - Indistinguishability between quantum randomness and pseudo-randomness
under efficiently calculable randomness measures [6.201566048090889]
We present a no-go theorem for the distinguishability between quantum random numbers (i.e., random numbers generated quantum mechanically) and pseudo-random numbers (i.e., random numbers generated algorithmically)
The theorem states that one cannot distinguish these two types of random numbers if the quantum random numbers are efficiently classically simulatable and the randomness measure used for the distinction is efficiently computable.
arXiv Detail & Related papers (2023-09-20T07:50:30Z) - Quantum Conformal Prediction for Reliable Uncertainty Quantification in
Quantum Machine Learning [47.991114317813555]
Quantum models implement implicit probabilistic predictors that produce multiple random decisions for each input through measurement shots.
This paper proposes to leverage such randomness to define prediction sets for both classification and regression that provably capture the uncertainty of the model.
arXiv Detail & Related papers (2023-04-06T22:05:21Z) - 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) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime.
For local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_textnoisy$ of a generic noisy circuit instance shrink exponentially.
If the noise is incoherent, the output distribution approaches the uniform distribution $p_textunif$ at precisely the same rate.
arXiv Detail & Related papers (2021-11-29T19:26:28Z) - Algorithmic Randomness and Kolmogorov Complexity for Qubits [0.0]
Nies and Scholz defined quantum Martin-L"of randomness (q-MLR) for states ( qubitstrings)
We define a notion of quantum Solovay randomness and show it to be equivalent to q-MLR using purely linear algebraic methods.
A quantum analogue of the law of large numbers is shown to hold for quantum Schnorr random states.
arXiv Detail & Related papers (2021-06-27T16:52:56Z) - The principle of majorization: application to random quantum circuits [68.8204255655161]
Three classes of circuits were considered: (i) universal, (ii) classically simulatable, and (iii) neither universal nor classically simulatable.
We verified that all the families of circuits satisfy on average the principle of majorization.
Clear differences appear in the fluctuations of the Lorenz curves associated to states.
arXiv Detail & Related papers (2021-02-19T16:07:09Z) - 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) - Quantum algorithmic randomness [0.0]
We define a notion of quantum Solovay randomness which is equivalent to q-MLR.
A quantum analogue of the law of large numbers is shown to hold for quantum Schnorr random states.
arXiv Detail & Related papers (2020-08-08T19:28:01Z)
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.