Linear gate bounds against natural functions for position-verification

• URL: http://arxiv.org/abs/2402.18648v2
• Date: Tue, 27 Aug 2024 16:26:04 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.
• 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. We prove the number of quantum gates plus single qubit measurements needed to implement a function $f$ is lower bounded linearly by the communication complexity of $f$ in the simultaneous message passing model with shared entanglement. Taking $f(x,y)=\sum_i x_i y_i$ to be the inner product function, we obtain a $\Omega(n)$ lower bound on quantum gates plus single qubit measurements. The scheme is feasible for a prover with linear classical resources and $O(1)$ quantum resources, and secure against sub-linear quantum resources.

Related papers

• Rank lower bounds on non-local quantum computation [0.0]
  A non-local quantum computation (NLQC) replaces an interaction between two quantum systems with a single round of communication and shared entanglement. We study two classes of NLQC, $f$-routing and $f$-BB84, which are of relevance to classical information theoretic cryptography and quantum position-verification.
  arXiv  Detail & Related papers  (2024-02-28T19:00:09Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• 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)
• Multi-state Swap Test Algorithm [2.709321785404766]
  Estimating the overlap between two states is an important task with several applications in quantum information. We design a quantum circuit to measure overlaps of multiple quantum states.
  arXiv  Detail & Related papers  (2022-05-15T03:31:57Z)
• 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)
• Halving the cost of quantum multiplexed rotations [0.0]
  We improve the number of $T$ gates needed for a $b$-bit approximation of a multiplexed quantum gate with $c$ controls. Our results roughly halve the cost of state-of-art electronic structure simulations based on qubitization of double-factorized or tensor-hypercontracted representations.
  arXiv  Detail & Related papers  (2021-10-26T06:49:44Z)
• Quantum simulation of $\phi^4$ theories in qudit systems [53.122045119395594]
  We discuss the implementation of quantum algorithms for lattice $Phi4$ theory on circuit quantum electrodynamics (cQED) system. The main advantage of qudit systems is that its multi-level characteristic allows the field interaction to be implemented only with diagonal single-qudit gates.
  arXiv  Detail & Related papers  (2021-08-30T16:30:33Z)
• 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)
• Communication Cost of Quantum Processes [49.281159740373326]
  A common scenario in distributed computing involves a client who asks a server to perform a computation on a remote computer. An important problem is to determine the minimum amount of communication needed to specify the desired computation. We analyze the total amount of (classical and quantum) communication needed by a server in order to accurately execute a quantum process chosen by a client.
  arXiv  Detail & Related papers  (2020-02-17T08:51:42Z)

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.