Linear gate bounds against natural functions for position-verification
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...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften
2025-01-01
|
| Series: | Quantum |
| Online Access: | https://quantum-journal.org/papers/q-2025-01-21-1604/pdf/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832592071181991936 |
|---|---|
| author | Vahid Asadi Richard Cleve Eric Culf Alex May |
| author_facet | Vahid Asadi Richard Cleve Eric Culf Alex May |
| author_sort | Vahid Asadi |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-74d461b507f849b2940833d8ab27c8f9 |
| institution | Kabale University |
| issn | 2521-327X |
| language | English |
| publishDate | 2025-01-01 |
| publisher | Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften |
| record_format | Article |
| series | Quantum |
| spelling | doaj-art-74d461b507f849b2940833d8ab27c8f92025-01-21T17:47:45ZengVerein zur Förderung des Open Access Publizierens in den QuantenwissenschaftenQuantum2521-327X2025-01-019160410.22331/q-2025-01-21-160410.22331/q-2025-01-21-1604Linear gate bounds against natural functions for position-verificationVahid AsadiRichard CleveEric CulfAlex MayA 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.https://quantum-journal.org/papers/q-2025-01-21-1604/pdf/ |
| spellingShingle | Vahid Asadi Richard Cleve Eric Culf Alex May Linear gate bounds against natural functions for position-verification Quantum |
| title | Linear gate bounds against natural functions for position-verification |
| title_full | Linear gate bounds against natural functions for position-verification |
| title_fullStr | Linear gate bounds against natural functions for position-verification |
| title_full_unstemmed | Linear gate bounds against natural functions for position-verification |
| title_short | Linear gate bounds against natural functions for position-verification |
| title_sort | linear gate bounds against natural functions for position verification |
| url | https://quantum-journal.org/papers/q-2025-01-21-1604/pdf/ |
| work_keys_str_mv | AT vahidasadi lineargateboundsagainstnaturalfunctionsforpositionverification AT richardcleve lineargateboundsagainstnaturalfunctionsforpositionverification AT ericculf lineargateboundsagainstnaturalfunctionsforpositionverification AT alexmay lineargateboundsagainstnaturalfunctionsforpositionverification |