10
collaborators
2003–2023
years active
Contributions
QIP QCrypt TQC talk poster presenter award · △program ◇steering ○organizing · filled = chair
6 Talks
| Title | Conference | Type | Co-authors |
|---|---|---|---|
| Breaking the cubic barrier in the Solovay-Kitaev algorithm | QIP 2023 | regular ▸ presenter | — |
| The Hidden Subgroup Problem for Infinite Groups | QIP 2021 | regular | — |
Abstract We consider the hidden subgroup problem (HSP) for infinite groups, beyond the celebrated original cases established by Shor and Kitaev. We prove that HSP is NP-hard in the rational numbers ℚ under addition, as well as for normal subgroups of a non-abelian free group F_k. We can show that HSP in the lattice ℤ^k is uSVP-hard with unary encoding of vectors. On the other hand, HSP in ℤ^k with standard binary encoding of vectors can be solved in BQP, uniformly in the dimension, generalizing the Shor-Kitaev algorithm to infinite-index hidden subgroups. HSP in any fixed, finitely generated, virtually abelian subgroup can also be solved in subexponential time using established quantum algorithms for the abelian hidden shift problem. |
|||
|
On the power of a unique quantum witness ↗
|
QIP 2010 | regular | Rahul Jain, Iordanis Kerenidis, Miklos Santha, Or Sattath, Shengyu Zhang |
|
Quantum computation with Turaev-Viro codes ↗
|
QIP 2010 | regular | Robert König, Ben Reichardt |
| A subexponential-time quantum algorithm for the dihedral hidden subgroup problem | QIP 2004 | invited | — |
| The capacity of hybrid quantum memory | QIP 2003 | regular ▸ presenter | — |
1 Poster
| Title | Conference | Co-authors |
|---|---|---|
| The Computational Complexity of Ball Permutations | QIP 2017 | Scott Aaronson, Adam Bouland, Saeed Mehraban |
Collaborators
| Co-author | Joint talks |
|---|---|
| Adam Bouland | 1 |
| Ben Reichardt | 1 |
| Iordanis Kerenidis | 1 |
| Miklos Santha | 1 |
| Or Sattath | 1 |
| Rahul Jain | 1 |
| Robert König | 1 |
| Saeed Mehraban | 1 |
| Scott Aaronson | 1 |
| Shengyu Zhang | 1 |