{"id":1258,"date":"2022-03-02T10:04:10","date_gmt":"2022-03-02T08:04:10","guid":{"rendered":"https:\/\/webs.uab.cat\/giq\/seminar\/topological-obstructions-to-implementing-basic-tasks\/"},"modified":"2022-03-02T10:04:10","modified_gmt":"2022-03-02T08:04:10","slug":"topological-obstructions-to-implementing-basic-tasks","status":"publish","type":"seminar","link":"https:\/\/webs.uab.cat\/giq\/seminar\/topological-obstructions-to-implementing-basic-tasks\/","title":{"rendered":"Topological obstructions to implementing basic tasks"},"content":{"rendered":"<p>&nbsp;(<a href=\"https:\/\/us02web.zoom.us\/j\/87205372932?pwd=NFluMkxpMGgwWnBIRytib1BTZ3Z6UT09\">Zoom link<\/a>)<\/p>\n<p>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&#8217;s complexity to any finite number of copies or oracle queries does not help \u2014 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.<\/p>\n<p>The talk summarises the following results (please note that I will put newer versions on arxiv soon):<\/p>\n<ul>\n<li>Gavorova, Seidel, Touati. Topological obstructions to implementing controlled unknown unitaries.&nbsp;<a href=\"https:\/\/arxiv.org\/abs\/2011.10031\" target=\"_blank\" rel=\"noopener\">https:\/\/arxiv.org\/abs\/2011.10031<\/a>&nbsp;(QIP21 talk:&nbsp;<a href=\"https:\/\/www.youtube.com\/watch?v=nhApgVGaczU\" target=\"_blank\" rel=\"noopener\">https:\/\/www.youtube.com\/watch?v=nhApgVGaczU<\/a>)<\/li>\n<li>Gavorova. Notes on distinguishability of postselected computations.&nbsp;<a href=\"https:\/\/arxiv.org\/abs\/2011.08487\" target=\"_blank\" rel=\"noopener\">https:\/\/arxiv.org\/abs\/2011.08487<\/a><\/li>\n<li>Gavorova. Topologically-driven impossibility of superposing unknown states.&nbsp;<a href=\"https:\/\/arxiv.org\/abs\/2111.02391\" target=\"_blank\" rel=\"noopener\">https:\/\/arxiv.org\/abs\/2111.02391<\/a><\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>&nbsp;(Zoom link) 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). [&hellip;]<\/p>\n","protected":false},"author":20,"featured_media":0,"template":"","class_list":["post-1258","seminar","type-seminar","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/webs.uab.cat\/giq\/wp-json\/wp\/v2\/seminar\/1258","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/webs.uab.cat\/giq\/wp-json\/wp\/v2\/seminar"}],"about":[{"href":"https:\/\/webs.uab.cat\/giq\/wp-json\/wp\/v2\/types\/seminar"}],"author":[{"embeddable":true,"href":"https:\/\/webs.uab.cat\/giq\/wp-json\/wp\/v2\/users\/20"}],"wp:attachment":[{"href":"https:\/\/webs.uab.cat\/giq\/wp-json\/wp\/v2\/media?parent=1258"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}