Pseudorandom density matrices

• URL: http://arxiv.org/abs/2407.11607v2
• Date: Fri, 31 Jan 2025 05:43:07 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 efficiently distinguished from Haar random states. We introduce PRDMs, ensembles of $n$-qubit states that are computationally indistinguishable from the generalized Hilbert-Schmidt ensemble (GHSE) PRDMs disguise valuable quantum resources, possessing near-maximal entanglement, magic and coherence, while being computationally indistinguishable from resource-free states.
• Score: 0.8204952610951527
• License:
• Abstract: Pseudorandom states (PRSs) are state ensembles that cannot be efficiently distinguished from Haar random states. However, the definition of PRSs has been limited to pure states and lacks robustness against noise. Here, we introduce pseudorandom density matrices (PRDMs), ensembles of $n$-qubit states that are computationally indistinguishable from the generalized Hilbert-Schmidt ensemble (GHSE), which is constructed from $(n+m)$-qubit Haar random states with $m$ qubits traced out. For $m=0$, PRDMs are equivalent to PRSs, whereas for $m=\omega(\log n)$, PRDMs are computationally indistinguishable from the maximally mixed state. PRDMs with $m=\omega(\log n)$ are robust to unital noise channels and separated in terms of security from PRS. PRDMs disguise valuable quantum resources, possessing near-maximal entanglement, magic and coherence, while being computationally indistinguishable from resource-free states. PRDMs exhibit a pseudoresource gap of $\Theta(n)$ vs $0$, surpassing previously found gaps. We also render EFI pairs, a fundamental cryptographic primitive, robust to strong mixed unitary noise. Our work has major implications on quantum resource theory: We show that entanglement, magic and coherence cannot be efficiently tested, and 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, as well as noise-robust quantum money. 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)
• Quantum Pseudorandomness Cannot Be Shrunk In a Black-Box Way [0.0]
  Pseudorandom Quantum States (PRS) were introduced by Ji, Liu and Song as quantum analogous to Pseudorandom Generators. Short-PRSs, that is PRSs with logarithmic size output, have been introduced in literature along with cryptographic applications. Here we show that it is not possible to shrink the output of a PRS from 2021 to logarithmic qubit length while still preserving the pseudorandomness property.
  arXiv  Detail & Related papers  (2024-02-20T19:02:43Z)
• 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)
• Pseudorandom unitaries are neither real nor sparse nor noise-robust [0.0]
  Pseudorandom quantum states (PRSs) and pseudorandom unitaries (PRUs) possess the dual nature of being efficiently constructible while appearing completely random to any efficient quantum algorithm. We show that PRSs and PRUs exist only when the probability that an error occurs is negligible, ruling out their generation on noisy intermediate-scale and early fault-tolerant quantum computers.
  arXiv  Detail & Related papers  (2023-06-20T16:54:27Z)
• 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)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• 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)
• 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)
• 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.