Uncloneable Quantum Advice
- URL: http://arxiv.org/abs/2309.05155v1
- Date: Sun, 10 Sep 2023 22:09:05 GMT
- Title: Uncloneable Quantum Advice
- Authors: Anne Broadbent, Martti Karvonen, S\'ebastien Lord
- Abstract summary: 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.
- Score: 1.1970409518725493
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The famous no-cloning principle has been shown recently to enable a number of
uncloneable functionalities. Here we address for the first time unkeyed quantum
uncloneablity, via the study of a complexity-theoretic tool that enables a
computation, but that is natively unkeyed: quantum advice. Remarkably, this is
an application of the no-cloning principle in a context where the quantum
states of interest are not chosen by a random process. We show the
unconditional existence of promise problems admitting uncloneable quantum
advice, and the existence of languages with uncloneable advice, assuming the
feasibility of quantum copy-protecting certain functions. Along the way, we
note that state complexity classes, introduced by Rosenthal and Yuen (ITCS
2022) - which concern the computational difficulty of synthesizing sequences of
quantum states - can be naturally generalized to obtain state cloning
complexity classes. We make initial observations on these classes, notably
obtaining a result analogous to the existence of undecidable problems.
Our proof technique establishes the existence of ingenerable sequences of
finite bit strings - essentially meaning that they cannot be generated by any
uniform circuit family. We then prove a generic result showing that the
difficulty of accomplishing a computational task on uniformly random inputs
implies its difficulty on any fixed, ingenerable sequence. We use this result
to derandomize quantum cryptographic games that relate to cloning, and then
incorporate a result of Kundu and Tan (arXiv 2022) to obtain uncloneable
advice. Applying this two-step process to a monogamy-of-entanglement game
yields a promise problem with uncloneable advice, and applying it to the
quantum copy-protection of pseudorandom functions with super-logarithmic output
lengths yields a language with uncloneable advice.
Related papers
- 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) - Commitments from Quantum One-Wayness [0.0]
This work studies one-way state generators, a natural quantum relaxation of one-way functions.
A fundamental question is whether this type of quantum one-wayness suffices to realize quantum cryptography.
We prove that one-way state generators with pure state outputs imply quantum bit commitments and secure multiparty computation.
arXiv Detail & Related papers (2023-10-17T18:48:22Z) - Quantum Query Complexity of Boolean Functions under Indefinite Causal
Order [0.9208007322096533]
We study the query complexity of Boolean functions under general higher order quantum computations.
We show that the recently introduced class of quantum circuits with quantum control of causal order cannot lead to any reduction in query complexity.
We find some functions for which the minimum error with which they can be computed using two queries is strictly lower when exploiting causally indefinite supermaps.
arXiv Detail & Related papers (2023-07-18T13:12:55Z) - Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
A test of quantumness is a protocol that allows a classical verifier to certify (only) that a prover is not classical.
We show that tests of quantumness that follow a certain template, which captures recent proposals such as (Kalai et al., 2022) can in fact do much more.
Namely, the same protocols can be used for certifying a qubit, a building-block that stands at the heart of applications such as certifiable randomness and classical delegation of quantum computation.
arXiv Detail & Related papers (2023-03-02T14:18:17Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
We study the problem of designing worst-case to average-case reductions for quantum algorithms.
We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
arXiv Detail & Related papers (2022-12-06T22:01:49Z) - 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) - 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) - 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) - Characterization of quantum states based on creation complexity [0.0]
The creation complexity of a quantum state is the minimum number of elementary gates required to create it from a basic initial state.
We show for an entirely general quantum state it is exponentially hard (requires a number of steps that scales exponentially with the number of qubits) to determine if the creation complexity is.
We then show it is possible for a large class of quantum states with creation complexity to have common coefficient features such that given any candidate quantum state we can design an efficient coefficient sampling procedure to determine if it belongs to the class or not with arbitrarily high success probability.
arXiv Detail & Related papers (2020-04-28T21:12:45Z) - 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.