Linear gate bounds against natural functions for position-verification
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913657213943808 |
|---|---|
| author | Asadi, Vahid Cleve, Richard Culf, Eric May, Alex |
| author_facet | Asadi, Vahid Cleve, Richard Culf, Eric May, Alex |
| contents | 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 $Ω(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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_18648 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Linear gate bounds against natural functions for position-verification Asadi, Vahid Cleve, Richard Culf, Eric May, Alex Quantum Physics 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 $Ω(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. |
| title | Linear gate bounds against natural functions for position-verification |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2402.18648 |