Quantum Pseudorandomness and Classical Complexity
- URL: http://arxiv.org/abs/2103.09320v4
- Date: Mon, 26 Feb 2024 16:11:01 GMT
- Title: Quantum Pseudorandomness and Classical Complexity
- Authors: William Kretschmer
- Abstract summary: 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.
- Score: 0.08158530638728499
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We construct a quantum oracle relative to which $\mathsf{BQP} = \mathsf{QMA}$
but cryptographic pseudorandom quantum states and pseudorandom unitary
transformations exist, a counterintuitive result in light of the fact that
pseudorandom states can be "broken" by quantum Merlin-Arthur adversaries. We
explain how this nuance arises as the result of a distinction between
algorithms that operate on quantum and classical inputs. On the other hand, we
show that some computational complexity assumption is needed to construct
pseudorandom states, by proving that pseudorandom states do not exist if
$\mathsf{BQP} = \mathsf{PP}$. We discuss implications of these results for
cryptography, complexity theory, and quantum tomography.
Related papers
- A Quantum "Lifting Theorem" for Constructions of Pseudorandom Generators from Random Oracles [7.454028086083526]
We study the (quantum) security of pseudorandom generators (PRGs) constructed from random oracles.
We prove a "lifting theorem" showing, roughly, that if such a PRG is unconditionally secure against classical adversaries making unboundedly many queries to the random oracle, then it is also (unconditionally) secure against quantum adversaries in the same sense.
arXiv Detail & Related papers (2024-01-25T17:13:51Z) - Taming Quantum Time Complexity [50.10645865330582]
We show how to achieve both exactness and thriftiness in the setting of time complexity.
We employ a novel approach to the design of quantum algorithms based on what we call transducers.
arXiv Detail & Related papers (2023-11-27T14:45:19Z) - 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) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
We design, implement, and evaluate three hybrid quantum k-Means algorithms.
We exploit quantum phenomena to speed up the computation of distances.
We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
arXiv Detail & Related papers (2022-12-13T16:04:16Z) - Quantum Cryptography in Algorithmica [0.7524721345903025]
We show that in a black-box setting, quantum cryptography based on pseudorandom states is possible even if one-way functions do not exist.
We also introduce a conjecture that would generalize our results to multi-copy secure pseudorandom states.
arXiv Detail & Related papers (2022-12-01T21:33:38Z) - Quantum Pseudoentanglement [4.3053817709507]
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.
arXiv Detail & Related papers (2022-11-01T21:04:49Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation.
For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
arXiv Detail & Related papers (2022-10-12T17:54:02Z) - 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) - 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 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.