A Perfectly Distributable Quantum-Classical Algorithm for Estimating Triangular Balance in a Signed Edge Stream
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917348825366528 |
|---|---|
| author | Kordonowy, Steven Adhikari, Bibhas Leipold, Hannes |
| author_facet | Kordonowy, Steven Adhikari, Bibhas Leipold, Hannes |
| contents | We develop a perfectly distributable quantum-classical streaming algorithm that processes signed edges to efficiently estimate the counts of triangles of diverse signed configurations in the single pass edge stream. Our approach introduces a quantum sketch register for processing the signed edge stream, together with measurement operators for query-pair calls in the quantum estimator, while a complementary classical estimator accounts for triangles not captured by the quantum procedure. This hybrid design yields a polynomial space advantage over purely classical approaches, extending known results from unsigned edge stream data to the signed setting. We quantify the lack of balance on random signed graph instances, showcasing how the classical and hybrid algorithms estimate balance in practice. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_16029 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A Perfectly Distributable Quantum-Classical Algorithm for Estimating Triangular Balance in a Signed Edge Stream Kordonowy, Steven Adhikari, Bibhas Leipold, Hannes Quantum Physics Computational Complexity We develop a perfectly distributable quantum-classical streaming algorithm that processes signed edges to efficiently estimate the counts of triangles of diverse signed configurations in the single pass edge stream. Our approach introduces a quantum sketch register for processing the signed edge stream, together with measurement operators for query-pair calls in the quantum estimator, while a complementary classical estimator accounts for triangles not captured by the quantum procedure. This hybrid design yields a polynomial space advantage over purely classical approaches, extending known results from unsigned edge stream data to the signed setting. We quantify the lack of balance on random signed graph instances, showcasing how the classical and hybrid algorithms estimate balance in practice. |
| title | A Perfectly Distributable Quantum-Classical Algorithm for Estimating Triangular Balance in a Signed Edge Stream |
| topic | Quantum Physics Computational Complexity |
| url | https://arxiv.org/abs/2603.16029 |