Linear gate bounds against natural functions for position-verification
- URL: http://arxiv.org/abs/2402.18648v1
- Date: Wed, 28 Feb 2024 19:00:10 GMT
- Title: Linear gate bounds against natural functions for position-verification
- Authors: Vahid Asadi, Richard Cleve, Eric Culf, Alex May
- Abstract summary: A quantum position-verification scheme attempts to verify the spatial location of a prover.
We consider two well-studied position-verification schemes known as $f$-routing and $f-BB84.
Our proof uses a reduction to simultaneous message passing with classical communication and shared entanglement.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A quantum position-verification scheme attempts to verify the spatial
location of a prover. The prover is issued a challenge with quantum and
classical inputs and must respond with appropriate timings. We consider two
well-studied position-verification schemes known as $f$-routing and $f$-BB84.
Both schemes require an honest prover to locally compute a classical function
$f$ of inputs of length $n$, and manipulate $O(1)$ size quantum systems. Taking
$f(x,y)=\sum_i x_i y_i$ to be the inner product function, we prove that a
dishonest prover must execute $\Omega(n)$ quantum gates or single qubit
measurements. Our proof uses a reduction to simultaneous message passing with
classical communication and shared entanglement. The scheme is feasible for a
prover with polynomial classical resources and $O(1)$ quantum resources, and
secure against sub-linear quantum resources.
Related papers
- A Novel Quantum-Classical Hybrid Algorithm for Determining Eigenstate Energies in Quantum Systems [1.9714447272714082]
We introduce a novel quantum XZ24 algorithm, designed for efficiently computing the eigen-energy spectra of any quantum systems.
Compared to existing quantum methods, the new algorithm stands out for its remarkably low measurement cost.
We anticipate that the new algorithm will drive significant progress in quantum system simulation and offer promising applications in quantum computing and quantum information processing.
arXiv Detail & Related papers (2024-06-01T04:31:43Z) - 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) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$.
We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM)
Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
arXiv Detail & Related papers (2022-06-07T18:00:01Z) - Efficient Bipartite Entanglement Detection Scheme with a Quantum
Adversarial Solver [89.80359585967642]
Proposal reformulates the bipartite entanglement detection as a two-player zero-sum game completed by parameterized quantum circuits.
We experimentally implement our protocol on a linear optical network and exhibit its effectiveness to accomplish the bipartite entanglement detection for 5-qubit quantum pure states and 2-qubit quantum mixed states.
arXiv Detail & Related papers (2022-03-15T09:46:45Z) - Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
We consider the setting where the two parties (a classical Alice and a quantum Bob) can communicate only via a classical channel.
We show that it is in general impossible to realize a two-party quantum functionality with black-box simulation in the case of malicious quantum adversaries.
We provide a compiler that takes as input a classical proof of quantum knowledge (PoQK) protocol for a QMA relation R and outputs a zero-knowledge PoQK for R that can be verified by classical parties.
arXiv Detail & Related papers (2020-10-15T17:55:31Z) - Quantum copy-protection of compute-and-compare programs in the quantum random oracle model [48.94443749859216]
We introduce a quantum copy-protection scheme for a class of evasive functions known as " compute-and-compare programs"
We prove that our scheme achieves non-trivial security against fully malicious adversaries in the quantum random oracle model (QROM)
As a complementary result, we show that the same scheme fulfils a weaker notion of software protection, called "secure software leasing"
arXiv Detail & Related papers (2020-09-29T08:41:53Z) - Quantum advantage for computations with limited space [6.327095331866255]
We consider space-restricted computations, where input is a read-only memory and only one (qu)bit can be computed on.
We experimentally demonstrate computations of $3$-, $4$-, $5$-, and $6$- by quantum circuits, leveraging custom two-qubit gates.
arXiv Detail & Related papers (2020-08-14T17:31:12Z) - Implementing a Fast Unbounded Quantum Fanout Gate Using Power-Law
Interactions [0.9634136878988853]
Power-law interactions with strength decaying as $1/ralpha$ in the distance provide an experimentally realizable resource for information processing.
We leverage the power of these interactions to implement a fast quantum fanout gate with an arbitrary number of targets.
We show that power-law systems with $alpha le D$ are difficult to simulate classically even for short times, under a standard assumption that factoring is classically intractable.
arXiv Detail & Related papers (2020-07-01T18:00:00Z) - 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) - Computational advantage from quantum superposition of multiple temporal
orders of photonic gates [0.0]
A control quantum system can coherently determine the order in which a target quantum system undergoes $N$ gate operations.
We experimentally demonstrate the quantum $N$-switch with $N=4$ gates acting on a photonic-polarization qubit.
This is the first observation of a quantum superposition of more than $N=2$ temporal orders.
arXiv Detail & Related papers (2020-02-18T19:00:01Z)
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.