QLunch: Zuzana Gavorova

Speaker: Zuzana Gavorova, The Hebrew University of Jerusalem

Title: Topological obstructions to implementing basic tasks

Abstract: 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 the 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 two results (please note that I will put newer versions on arxiv soon):