5
collaborators
2026–2026
years active
Contributions
QIP QCrypt TQC talk poster presenter award · △program ◇steering ○organizing · filled = chair
3 Posters
| Title | Conference | Co-authors |
|---|---|---|
| Universal approximation of continuous functions with minimal quantum circuits | QIP 2026 | Adrián Pérez-Salinas, Alice Barthe, Vedran Dunjko |
| Computational complexity of the persistence of homology problem with orientable filtration: MA-completeness | QIP 2026 | ▸Ryu Hayakawa, Casper Gyurik, Vedran Dunjko |
| Computational complexity of the homology problem with orientable filtration: MA-completeness | TQC 2026 | Ryu Hayakawa, Casper Gyurik, Vedran Dunjko |
We show the existence of an MA-complete homology problem for a certain subclass of simplicial complexes. The problem is defined through a new concept of orientability of simplicial complexes that we call a ``uniform orientable filtration'', which is related to sign-problem freeness in homology. The containment in MA is achieved through the design of new, higher-order random walks on simplicial complexes associated with the filtration. For the MA-hardness, we design a new gadget with which we can reduce from an MA-hard stoquastic satisfiability problem. Therefore, our result provides the first natural MA-complete problem for higher-order random walks on simplicial complexes, combining the concepts of topology, persistent homology, and quantum computing. |
||
Collaborators
| Co-author | Joint talks |
|---|---|
| Vedran Dunjko | 3 |
| Casper Gyurik | 2 |
| Ryu Hayakawa | 2 |
| Adrián Pérez-Salinas | 1 |
| Alice Barthe | 1 |