Quantum Algorithm for Identifying Hidden Graphs: Spectral Theory and Numerical Evidence

Pawel Wocjan

We give a quantum algorithm for a novel type of black-box problem: identifying a hidden $d$-regular base graph $G$ on $n$ vertices from oracle access to an obfuscated version of it…