Rank lower bounds on non-local quantum computation

• URL: http://arxiv.org/abs/2402.18647v2
• Date: Fri, 5 Apr 2024 14:33:36 GMT
• Title: Rank lower bounds on non-local quantum computation
• Authors: Vahid Asadi, Eric Culf, Alex May,
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A non-local quantum computation (NLQC) replaces an interaction between two quantum systems with a single simultaneous 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. We give the first non-trivial lower bounds on entanglement in both settings, but are restricted to lower bounding protocols with perfect correctness. Within this setting, we give a lower bound on the Schmidt rank of any entangled state that completes these tasks for a given function $f(x,y)$ in terms of the rank of a matrix $g(x,y)$ whose entries are zero when $f(x,y)=0$, and strictly positive otherwise. This also leads to a lower bound on the Schmidt rank in terms of the non-deterministic quantum communication complexity of $f(x,y)$. Because of a relationship between $f$-routing and the conditional disclosure of secrets (CDS) primitive studied in information theoretic cryptography, we obtain a new technique for lower bounding the randomness complexity of CDS.

Related papers

• Linear gate bounds against natural functions for position-verification [0.0]
  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.
  arXiv  Detail & Related papers  (2024-02-28T19:00:10Z)
• 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)
• Relating non-local quantum computation to information theoretic cryptography [0.0]
  Non-local quantum computation (NLQC) is a cheating strategy for position-verification schemes, and has appeared in the context of the AdS/CFT correspondence. We show one special case of NLQC, known as $f$-routing, is equivalent to the quantum analogue of the conditional disclosure of secrets primitives. By relating position-verification to these cryptographic primitives, a number of results in the cryptography literature give new implications for NLQC.
  arXiv  Detail & Related papers  (2023-06-28T18:00:05Z)
• Quantum Lower Bounds for Finding Stationary Points of Nonconvex Functions [8.495749905129278]
  Despite progress in classical lower bounds for non optimization, these bounds are still widely open. Omegabig(frac-1+ppp)$ regarding the first setting. Omegano()$ regarding the second setting. Omega()$ if gradient function is meand smooth. Omega()$ if gradient function is meand smooth. Omega()$ if gradient function is meand smooth. Omega()$ if gradient function is meand smooth.
  arXiv  Detail & Related papers  (2022-12-07T19:02:36Z)
• 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)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation. We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
  arXiv  Detail & Related papers  (2022-01-31T22:19:49Z)
• Towards Tight Communication Lower Bounds for Distributed Optimisation [30.134447658488057]
  We consider a standard distributed optimisation setting where $N$ machines aim to jointly minimise the sum of the functions $sum_i = 1N f_i (x)$. Our main result provides the first fully unconditional bounds on total number of bits which need to be sent and received by the $N$ machines. We show that $Omega( Nd log d / Nvarepsilon)$ total bits need to be communicated between the machines to find an additive $epsilon$-approximation to the minimum of $sum_i = 1N
  arXiv  Detail & Related papers  (2020-10-16T08:10:02Z)
• Quantum Communication Complexity of Distribution Testing [114.31181206328276]
  Two players each receive $t$ samples from one distribution over $[n]$. The goal is to decide whether their two distributions are equal, or are $epsilon$-far apart. We show that the quantum communication complexity of this problem is $tildeO$(tepsilon2))$ qubits when distributions have low $l$-norm.
  arXiv  Detail & Related papers  (2020-06-26T09:05:58Z)
• Quasi-polynomial time algorithms for free quantum games in bounded dimension [11.56707165033]
  We give a semidefinite program of size $exp(mathcalObig(T12(log2(AT)+log(Q)log(AT))/epsilon2big)) to compute additive $epsilon$-approximations on the values of two-player free games. We make a connection to the quantum separability problem and employ improved multipartite quantum de Finetti theorems with linear constraints.
  arXiv  Detail & Related papers  (2020-05-18T16:55:08Z)
• 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)
• 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.