Quantum algorithmic randomness

• URL: http://arxiv.org/abs/2008.03584v2
• Date: Wed, 20 Jan 2021 18:59:49 GMT
• Title: Quantum algorithmic randomness
• Authors: Tejas Bhojraj
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum Martin-L\"of randomness (q-MLR) for infinite qubit sequences was introduced by Nies and Scholz. We define a notion of quantum Solovay randomness which is equivalent to q-MLR. The proof of this goes through a purely linear algebraic result about approximating density matrices by subspaces. We then show that random states form a convex set. Martin-L\"of absolute continuity is shown to be a special case of q-MLR. Quantum Schnorr randomness is introduced. A quantum analogue of the law of large numbers is shown to hold for quantum Schnorr random states.

Related papers

• Polynomial-depth quantum algorithm for computing matrix determinant [46.13392585104221]
  We propose an algorithm for calculating the determinant of a square matrix, and construct a quantum circuit realizing it. Each row of the matrix is encoded as a pure state of some quantum system. The admitted matrix is therefore arbitrary up to the normalization of quantum states of those systems.
  arXiv  Detail & Related papers  (2024-01-29T23:23:27Z)
• Derandomization of quantum algorithm for triangle finding [0.0]
  Derandomization is the process of taking a randomized algorithm and turning it into a deterministic algorithm. In quantum computing, it is challenging and intriguing to derandomize quantum algorithms, due to the inherent randomness of quantum mechanics. We show that when the graph is promised to contain at most one target triangle, there exists a deterministic quantum algorithm that either finds the triangle if it exists or outputs no triangle'' if none exists.
  arXiv  Detail & Related papers  (2023-09-23T05:24:59Z)
• Cutoff phenomenon and entropic uncertainty for random quantum circuits [0.0]
  How fast a state of a system converges to a stationary state is one of the fundamental questions in science. Some Markov chains and random walks on finite groups are known to exhibit the non-asymptotic convergence to a stationary distribution. We show how quickly a random quantum circuit could transform a quantum state to a Haar-measure random quantum state.
  arXiv  Detail & Related papers  (2023-05-20T03:33:48Z)
• 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)
• Why we should interpret density matrices as moment matrices: the case of (in)distinguishable particles and the emergence of classical reality [69.62715388742298]
  We introduce a formulation of quantum theory (QT) as a general probabilistic theory but expressed via quasi-expectation operators (QEOs) We will show that QT for both distinguishable and indistinguishable particles can be formulated in this way. We will show that finitely exchangeable probabilities for a classical dice are as weird as QT.
  arXiv  Detail & Related papers  (2022-03-08T14:47:39Z)
• Random Matrices and Quantum Hamilton-Jacobi Method [0.0]
  We show that the underlying complex pole evolution of the Schr"odinger equation is described by the quantum action in terms of a random matrix. The wave function is given by the random matrix probability distribution function.
  arXiv  Detail & Related papers  (2021-07-14T05:45:44Z)
• 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)
• 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 Random Number Generation using a Solid-State Single-Photon Source [89.24951036534168]
  Quantum random number generation (QRNG) harnesses the intrinsic randomness of quantum mechanical phenomena. We demonstrate QRNG with a quantum emitter in hexagonal boron nitride. Our results open a new avenue to the fabrication of on-chip deterministic random number generators.
  arXiv  Detail & Related papers  (2020-01-28T22:47:43Z)

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.