Abstract:  Quantum computers are not the perfect devices we usually imagine when designing quantum algorithms. Their architectures impose constraints on what operations can be performed and where. In this talk, we propose circuit transformations that turn higher-level circuits into equivalent lower-level circuits that conform to the constraints imposed by the architecture. A natural subproblem that arises is routing of qubits, i.e. implementing a permutation of qubits. We will consider both "classical" and quantum protocols for solving this problem and exhibit separations between the two. Next, we provide lower bounds on quantum routing. These show that a superpolynomial separation is only possible when the underlying architecture graph has expander properties, unlike the path graphs and grid graphs we find in most architectures. Finally, we provide some empirical results of applying our routing techniques to circuits and consider applications to fault-tolerant quantum computing. 

Please use this link to attend the virtual seminar:

https://bluejeans.com/972203158/4657

Meeting ID: 972 203 158 / Participant Passcode: 4657