Algorithmic Randomness and Kolmogorov Complexity for Qubits

• URL: http://arxiv.org/abs/2106.14280v1
• Date: Sun, 27 Jun 2021 16:52:56 GMT
• Title: Algorithmic Randomness and Kolmogorov Complexity for Qubits
• Authors: Tejas Bhojraj
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Nies and Scholz defined quantum Martin-L\"of randomness (q-MLR) for states (infinite qubitstrings). We define a notion of quantum Solovay randomness and show it to be equivalent to q-MLR using purely linear algebraic methods. Quantum Schnorr randomness is then introduced. A quantum analogue of the law of large numbers is shown to hold for quantum Schnorr random states. We introduce quantum-K, ($QK$) a measure of the descriptive complexity of density matrices using classical prefix-free Turing machines and show that the initial segments of weak Solovay random and quantum Schnorr random states are incompressible in the sense of $QK$. Several connections between Solovay randomness and $K$ carry over to those between weak Solovay randomness and $QK$. We then define $QK_C$, using computable measure machines and connect it to quantum Schnorr randomness. We then explore a notion of `measuring' a state. We formalize how `measurement' of a state induces a probability measure on the space of infinite bitstrings. 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. I.e., measuring a $mR$ state produces a Martin-L\"of random bitstring almost surely. While quantum-Martin-L\"of random states are $mR$, the converse fails: there is a $mR$ state, $\rho$ which is not quantum-Martin-L\"of random. In fact, something stronger is true. While $\rho$ is computable and can be easily constructed, measuring it in any computable basis yields an arithmetically random sequence with probability one. So, classical randomness can be generated from a computable state which is not quantum random. We conclude by studying the asymptotic von Neumann entropy of computable states.

Related papers

• Slow Mixing of Quantum Gibbs Samplers [47.373245682678515]
  We present a quantum generalization of these tools through a generic bottleneck lemma. This lemma focuses on quantum measures of distance, analogous to the classical Hamming distance but rooted in uniquely quantum principles. Even with sublinear barriers, we use Feynman-Kac techniques to lift classical to quantum ones establishing tight lower bound $T_mathrmmix = 2Omega(nalpha)$.
  arXiv  Detail & Related papers  (2024-11-06T22:51:27Z)
• 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)
• The role of shared randomness in quantum state certification with unentangled measurements [36.19846254657676]
  We study quantum state certification using unentangled quantum measurements. $Theta(d2/varepsilon2)$ copies are necessary and sufficient for state certification. We develop a unified lower bound framework for both fixed and randomized measurements.
  arXiv  Detail & Related papers  (2024-01-17T23:44:52Z)
• On the average-case complexity of learning output distributions of quantum circuits [55.37943886895049]
  We show that learning the output distributions of brickwork random quantum circuits is average-case hard in the statistical query model. This learning model is widely used as an abstract computational model for most generic learning algorithms.
  arXiv  Detail & Related papers  (2023-05-09T20:53:27Z)
• 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)
• 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)
• Quantum Pseudorandomness and Classical Complexity [0.08158530638728499]
  We show that cryptographic pseudorandom quantum states and pseudorandom unitary transformations exist. We discuss implications of these results for cryptography, complexity theory, and quantum tomography.
  arXiv  Detail & Related papers  (2021-03-16T20:54:12Z)
• 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)
• Generating Randomness from a Computable, Non-random Sequence of Qubits [0.0]
  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.
  arXiv  Detail & Related papers  (2020-05-01T04:09:49Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)
• Quantum Coupon Collector [62.58209964224025]
  We study how efficiently a $k$-element set $Ssubseteq[n]$ can be learned from a uniform superposition $|Srangle of its elements. We give tight bounds on the number of quantum samples needed for every $k$ and $n$, and we give efficient quantum learning algorithms.
  arXiv  Detail & Related papers  (2020-02-18T16:14:55Z)

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.