A Meta-Complexity Characterization of Minimal Quantum Cryptography
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_ | 1866912638469931008 |
|---|---|
| author | Cavalar, Bruno Chen, Boyang Coladangelo, Andrea Gray, Matthew Hu, Zihan Ji, Zhengfeng Li, Xingjian |
| author_facet | Cavalar, Bruno Chen, Boyang Coladangelo, Andrea Gray, Matthew Hu, Zihan Ji, Zhengfeng Li, Xingjian |
| contents | We give a meta-complexity characterization of EFI pairs, which are considered the "minimal" primitive in quantum cryptography (and are equivalent to quantum commitments). More precisely, we show that the existence of EFI pairs is equivalent to the following: there exists a non-uniformly samplable distribution over pure states such that the problem of estimating a certain Kolmogorov-like complexity measure is hard given a single copy.
A key technical step in our proof, which may be of independent interest, is to show that the existence of EFI pairs is equivalent to the existence of non-uniform single-copy secure pseudorandom state generators (nu 1-PRS). As a corollary, we get an alternative, arguably simpler, construction of a universal EFI pair. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_07859 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Meta-Complexity Characterization of Minimal Quantum Cryptography Cavalar, Bruno Chen, Boyang Coladangelo, Andrea Gray, Matthew Hu, Zihan Ji, Zhengfeng Li, Xingjian Quantum Physics We give a meta-complexity characterization of EFI pairs, which are considered the "minimal" primitive in quantum cryptography (and are equivalent to quantum commitments). More precisely, we show that the existence of EFI pairs is equivalent to the following: there exists a non-uniformly samplable distribution over pure states such that the problem of estimating a certain Kolmogorov-like complexity measure is hard given a single copy. A key technical step in our proof, which may be of independent interest, is to show that the existence of EFI pairs is equivalent to the existence of non-uniform single-copy secure pseudorandom state generators (nu 1-PRS). As a corollary, we get an alternative, arguably simpler, construction of a universal EFI pair. |
| title | A Meta-Complexity Characterization of Minimal Quantum Cryptography |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2510.07859 |