A 1.5-Query Lower Bound for the Unitary Synthesis Problem
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908496663937024 |
|---|---|
| author | Huang, Eric |
| author_facet | Huang, Eric |
| contents | We prove a new lower bound for the unitary synthesis problem in the so-called 1.5-query setting. Our analysis establishes that any attempt to implement arbitrary n-qubit unitaries via limited oracle access requires resources that exceed the fractional query threshold. This result extends the one-query lower bound of Lombardi, Ma, and Wright (2023) to the fractional query regime, and introduces a conservative and chaining-based approach to handle intermediate query complexities. As a consequence, we derive cryptographic implications, showing that pseudorandom quantum states remain secure against adversaries restricted to 1.5 queries. Our work provides both conceptual clarification of fractional-query complexity and practical insights into the design of quantum cryptographic protocols. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_13215 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A 1.5-Query Lower Bound for the Unitary Synthesis Problem Huang, Eric Quantum Physics We prove a new lower bound for the unitary synthesis problem in the so-called 1.5-query setting. Our analysis establishes that any attempt to implement arbitrary n-qubit unitaries via limited oracle access requires resources that exceed the fractional query threshold. This result extends the one-query lower bound of Lombardi, Ma, and Wright (2023) to the fractional query regime, and introduces a conservative and chaining-based approach to handle intermediate query complexities. As a consequence, we derive cryptographic implications, showing that pseudorandom quantum states remain secure against adversaries restricted to 1.5 queries. Our work provides both conceptual clarification of fractional-query complexity and practical insights into the design of quantum cryptographic protocols. |
| title | A 1.5-Query Lower Bound for the Unitary Synthesis Problem |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2508.13215 |