Topological obstructions to implementing basic tasks
Seminar author:Zuzana Gavorova
Event date and time:03/24/2022 04:00:pm
Event location:GIQ & Zoom
Event contact:
I will talk about surprising limitations of the quantum circuit model. They concern two tasks that can be seen as quantum versions of classically easy tasks: creating a superposition of any two unknown states of a given dimension (a quantum adder), and implementing controlled-U for any d-dimensional unitary oracle U (a quantum if-clause). Previous works defined the tasks precisely, and showed that quantum circuit fails to superpose two states from one copy of each, or to implement controlled-U from one query to U. I will show that increasing the quantum circuit’s complexity to any finite number of copies or oracle queries does not help — and neither does accepting approximate solutions! The proof method regards a quantum circuit as a continuous function and uses topological arguments to arrive at the impossibility. Compared to the polynomial method, it excludes any finite quantum-circuit complexity. This sharply contrasts the linear-optics complexity of controlled-U, known previously to equal 1. It also reveals an interesting subtlety in state and process tomography. The subtlety suggests a way to circumvent the impossibilities.
The talk summarises the following results (please note that I will put newer versions on arxiv soon):
- Gavorova, Seidel, Touati. Topological obstructions to implementing controlled unknown unitaries. https://arxiv.org/abs/2011.10031 (QIP21 talk: https://www.youtube.com/watch?v=nhApgVGaczU)
- Gavorova. Notes on distinguishability of postselected computations. https://arxiv.org/abs/2011.08487
- Gavorova. Topologically-driven impossibility of superposing unknown states. https://arxiv.org/abs/2111.02391