Pseudorandom density matrices

• URL: http://arxiv.org/abs/2407.11607v1
• Date: Tue, 16 Jul 2024 11:14:58 GMT
• Title: Pseudorandom density matrices
• Authors: Nikhil Bansal, Wai-Keong Mok, Kishor Bharti, Dax Enshan Koh, Tobias Haug,
• Abstract summary: Pseudorandom states (PRSs) are state ensembles that cannot be distinguished from Haar random states by any efficient quantum algorithm. We introduce PRDMs, ensembles of $n$-qubit states that are computationally indistinguishable from the generalized Hilbert-Schmidt ensemble. PRDMs with $m=omega(log n)$ are robust to unital noise channels and a recently introduced $mathsfPostBQP$ attack. We also introduce memoryless PRSs, a noise-robust notion of PRS which are indistinguishable to Haar random states for efficient
• Score: 0.8204952610951527
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Pseudorandom states (PRSs) are state ensembles that cannot be distinguished from Haar random states by any efficient quantum algorithm. However, the definition of PRSs has been limited to pure states and lacks robustness against noise. In this work, we introduce pseudorandom density matrices (PRDMs), ensembles of $n$-qubit states that are computationally indistinguishable from the generalized Hilbert-Schmidt ensemble, which is constructed from $(n+m)$-qubit Haar random states with $m$ qubits traced out. For a mixedness parameter $m=0$, PRDMs are equivalent to PRSs, whereas for $m=\omega(\log n)$, PRDMs are computationally indistinguishable from the maximally mixed state. In contrast to PRSs, PRDMs with $m=\omega(\log n)$ are robust to unital noise channels and a recently introduced $\mathsf{PostBQP}$ attack. Further, we construct pseudomagic and pseudocoherent state ensembles, which possess near-maximal magic and coherence, but are computationally indistinguishable from states with zero magic and coherence. PRDMs can exhibit a pseudoresource gap of $\Theta(n)$ vs $0$, surpassing previously found gaps. We introduce noise-robust EFI pairs, which are state ensembles that are computationally indistinguishable yet statistically far, even when subject to noise. We show that testing entanglement, magic and coherence is not efficient. Further, we prove that black-box resource distillation requires a superpolynomial number of copies. We also establish lower bounds on the purity needed for efficient testing and black-box distillation. Finally, we introduce memoryless PRSs, a noise-robust notion of PRS which are indistinguishable to Haar random states for efficient algorithms without quantum memory. Our work provides a comprehensive framework of pseudorandomness for mixed states, which yields powerful quantum cryptographic primitives and fundamental bounds on quantum resource theories.

Related papers

• Fast pseudothermalization [5.835366072870476]
  "pseudo-quantum" ensembles with small resources are referred to as "pseudo-quantum" ensembles. We present implementations that only require $omega(log n)cdot O(t[log t]2)$ depth circuits. This is the fastest known for generating pseudorandom states to the best of our knowledge.
  arXiv  Detail & Related papers  (2024-11-06T15:11:55Z)
• 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)
• Concentration bounds for quantum states and limitations on the QAOA from polynomial approximations [17.209060627291315]
  We prove concentration for the following classes of quantum states: (i) output states of shallow quantum circuits, answering an open question from [DPMRF22]; (ii) injective matrix product states, answering an open question from [DPMRF22]; (iii) output states of dense Hamiltonian evolution, i.e. states of the form $eiota H(p) cdots eiota H(1) |psirangle for any $n$-qubit product state $|psirangle$, where each $H(
  arXiv  Detail & Related papers  (2022-09-06T18:00:02Z)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  We prove a Lipschitzness lower bound $Omega(sqrtn/p)$ of robustness of interpolating neural network parameters on arbitrary distributions. We then show the potential benefit of overparametrization for smooth data when $n=mathrmpoly(d)$. We disprove the potential existence of an $O(1)$-Lipschitz robust interpolating function when $n=exp(omega(d))$.
  arXiv  Detail & Related papers  (2022-02-23T16:10:23Z)
• Purity of thermal mixed quantum states [0.0]
  We evaluate the purity of a series of thermal equilibrium states that can be calculated in numerical experiments without knowing the exact form of the quantum state. Canonical typicality guarantees that there are numerous microscopically different expressions of such states, which we call thermal mixed quantum (TMQ) states.
  arXiv  Detail & Related papers  (2022-02-15T05:46:29Z)
• How to simulate quantum measurement without computing marginals [3.222802562733787]
  We describe and analyze algorithms for classically computation measurement of an $n$-qubit quantum state $psi$ in the standard basis. Our algorithms reduce the sampling task to computing poly(n)$ amplitudes of $n$-qubit states.
  arXiv  Detail & Related papers  (2021-12-15T21:44:05Z)
• 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)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  We study the learnability of halfspaces in the presence of Tsybakov noise. We give an algorithm that achieves misclassification error $epsilon$ with respect to the true halfspace.
  arXiv  Detail & Related papers  (2020-06-11T14:25:02Z)
• A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
  Given a discrete probability measure supported on $N$ atoms and a set of $n$ real-valued functions, there exists a probability measure that is supported on a subset of $n+1$ of the original $N$ atoms. We give a simple geometric characterization of barycenters via negative cones and derive a randomized algorithm that computes this new measure by "greedy geometric sampling" We then study its properties, and benchmark it on synthetic and real-world data to show that it can be very beneficial in the $Ngg n$ regime.
  arXiv  Detail & Related papers  (2020-06-02T16:38:36Z)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  We study the efficient learnability of high-dimensional Gaussian mixtures in the adversarial-robust setting. We provide an algorithm that learns the components of an $epsilon$-corrupted $k$-mixture within information theoretically near-optimal error proofs of $tildeO(epsilon)$. Our main technical contribution is a new robust identifiability proof clusters from a Gaussian mixture, which can be captured by the constant-degree Sum of Squares proof system.
  arXiv  Detail & Related papers  (2020-05-13T16:44:12Z)
• Scalable Pseudorandom Quantum States [14.048989759890476]
  In existing constructions of PRS generators, security scales with the number of qubits in the states, i.e. the (statistical) security parameter for an $n$-qubit PRS is roughly $n$. We show that any quantum-secure one-way function implies scalable PRS. We follow the paradigm of first showing a emphstatistically secure construction when given oracle access to a random function, and then replacing the random function with a quantum-secure (classical) pseudorandom function to achieve computational security.
  arXiv  Detail & Related papers  (2020-04-04T17:15:03Z)

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.