Methods for Reducing Ancilla-Overhead in Block Encodings
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916958692179968 |
|---|---|
| author | Vasconcelos, Francisca Gilyén, András |
| author_facet | Vasconcelos, Francisca Gilyén, András |
| contents | Block encodings are a fundamental primitive in quantum algorithms, but can often have large ancilla overhead. In this work, we introduce novel techniques for reducing this overhead in two distinct ways. In Part I, we prove the existence of a "space-time tradeoff" by deriving an algorithm that, for any block encoding, approximately uncomputes all but one of its ancilla (freeing up those ancillae for reuse in later parts of a quantum algorithm). In Part II, we evaluate the minimum number of ancillae required to perform coherent multiplication of block encodings and introduce a "space-accuracy tradeoff". Specfically, we prove that logarithmic ancillae is optimal for exact multiplication of block encodings, but show that (in certain block encoding regimes) approximate multiplication of block encodings can be achieved to high-precision with just one ancilla. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_07900 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Methods for Reducing Ancilla-Overhead in Block Encodings Vasconcelos, Francisca Gilyén, András Quantum Physics Block encodings are a fundamental primitive in quantum algorithms, but can often have large ancilla overhead. In this work, we introduce novel techniques for reducing this overhead in two distinct ways. In Part I, we prove the existence of a "space-time tradeoff" by deriving an algorithm that, for any block encoding, approximately uncomputes all but one of its ancilla (freeing up those ancillae for reuse in later parts of a quantum algorithm). In Part II, we evaluate the minimum number of ancillae required to perform coherent multiplication of block encodings and introduce a "space-accuracy tradeoff". Specfically, we prove that logarithmic ancillae is optimal for exact multiplication of block encodings, but show that (in certain block encoding regimes) approximate multiplication of block encodings can be achieved to high-precision with just one ancilla. |
| title | Methods for Reducing Ancilla-Overhead in Block Encodings |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2507.07900 |