Quantum Pseudoentanglement
- URL: http://arxiv.org/abs/2211.00747v2
- Date: Fri, 7 Apr 2023 18:00:03 GMT
- Title: Quantum Pseudoentanglement
- Authors: Scott Aaronson, Adam Bouland, Bill Fefferman, Soumik Ghosh, Umesh
Vazirani, Chenyi Zhang and Zixin Zhou
- Abstract summary: Entanglement is a quantum resource, in some ways analogous to randomness in classical computation.
We give a construction of pseudoentangled states with entanglement entropy arbitrarily close to $log n$ across every cut.
We discuss applications of this result to Matrix Product State testing, entanglement distillation, and the complexity of the AdS/CFT correspondence.
- Score: 4.3053817709507
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Entanglement is a quantum resource, in some ways analogous to randomness in
classical computation. Inspired by recent work of Gheorghiu and Hoban, we
define the notion of "pseudoentanglement'', a property exhibited by ensembles
of efficiently constructible quantum states which are indistinguishable from
quantum states with maximal entanglement. Our construction relies on the notion
of quantum pseudorandom states -- first defined by Ji, Liu and Song -- which
are efficiently constructible states indistinguishable from (maximally
entangled) Haar-random states. Specifically, we give a construction of
pseudoentangled states with entanglement entropy arbitrarily close to $\log n$
across every cut, a tight bound providing an exponential separation between
computational vs information theoretic quantum pseudorandomness. We discuss
applications of this result to Matrix Product State testing, entanglement
distillation, and the complexity of the AdS/CFT correspondence. As compared
with a previous version of this manuscript (arXiv:2211.00747v1) this version
introduces a new pseudorandom state construction, has a simpler proof of
correctness, and achieves a technically stronger result of low entanglement
across all cuts simultaneously.
Related papers
- Uncloneable Quantum Advice [1.1970409518725493]
We show for the first time unkeyed quantum uncloneablity, via the study of a complexity-theoretic tool that enables a computation.
We show the unconditional existence of promise problems admitting uncloneable quantum advice, and the existence of languages with uncloneable advice.
arXiv Detail & Related papers (2023-09-10T22:09:05Z) - Pseudorandom Strings from Pseudorandom Quantum States [6.79244006793321]
We study the relationship between notions of pseudorandomness in the quantum and classical worlds.
We show that a natural variant of pseudorandom generators called quantum pseudorandom generators (QPRGs) can be based on the existence of logarithmic output length PRSGs.
We also study the relationship between other notions, namely, pseudorandom function-like state generators and pseudorandom functions.
arXiv Detail & Related papers (2023-06-09T01:16:58Z) - Calculating the many-body density of states on a digital quantum
computer [58.720142291102135]
We implement a quantum algorithm to perform an estimation of the density of states on a digital quantum computer.
We use our algorithm to estimate the density of states of a non-integrable Hamiltonian on the Quantinuum H1-1 trapped ion chip for a controlled register of 18bits.
arXiv Detail & Related papers (2023-03-23T17:46:28Z) - 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) - Pseudorandom (Function-Like) Quantum State Generators: New Definitions
and Applications [7.2051162210119495]
We explore new definitions, new properties and applications of pseudorandom states.
Pseudorandom quantum states (PRS) are efficiently constructible states that are computationally indistinguishable from being Haar-random.
We show that PRS generators with logarithmic output length imply commitment and encryption schemes with classical communication.
arXiv Detail & Related papers (2022-11-02T19:24:55Z) - 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) - Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees.
Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation.
We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
arXiv Detail & Related papers (2022-03-30T02:02:16Z) - Cryptography from Pseudorandom Quantum States [6.164147034988822]
One-way functions imply the existence of pseudorandom states, but Kretschmer (TQC'20) recently constructed an oracle relative to which there are no one-way functions but pseudorandom states still exist.
We study the intriguing possibility of basing interesting cryptographic tasks on pseudorandom states.
A consequence of (a) is that pseudorandom states are sufficient to construct maliciously secure multiparty protocols in the dishonest majority setting.
arXiv Detail & Related papers (2021-12-18T22:53:16Z) - Depth-efficient proofs of quantumness [77.34726150561087]
A proof of quantumness is a type of challenge-response protocol in which a classical verifier can efficiently certify quantum advantage of an untrusted prover.
In this paper, we give two proof of quantumness constructions in which the prover need only perform constant-depth quantum circuits.
arXiv Detail & Related papers (2021-07-05T17:45:41Z) - 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 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)
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.