CS Seminar by Pei Yuan, Tencent
Title: Does qubit connectivity impact quantum circuit complexity?
Date/Time: 08-Feb, 04:00PM
Venue: Via Zoom
Abstract: Some physical implementation schemes of quantum computing -- such as those based on superconducting qubits, quantum dots, and cold atoms -- can apply two-qubit gates only on certain pairs of qubits. Other schemes -- such as those based on trapped ions and photonics -- are not subject to such constraints. These qubit connectivity constraints are commonly viewed as a disadvantage; for example, compiling an unrestricted n-qubit quantum circuit to one with poor qubit connectivity, such as a 1D chain, usually results in a blowup of depth by O(n2) and size by O(n). It is appealing to conjecture that this overhead is unavoidable -- a random circuit on n qubits has Θ(n) 2-qubit gates in each layer and a constant fraction of them act on qubits separated by distance Θ(n).
While it is known that almost all n-qubit unitaries need quantum circuits of Ω(4n/n) depth and Ω(4n) size to realize, in this paper, we show that all n-qubit unitaries can be implemented by circuits of O(4n/n) depth and O(4n) size even under 1D chain qubit connectivity constraints.
We extend this result and investigate qubit connectivity along three directions. First, we consider more general connectivity graphs, and show that the size can always be made O(4n) as long as the graph is connected. For depth, we study d-dimensional grids, complete d-ary trees and expander graphs, and show results similar to the 1D chain. Second, we consider the case when ancillae are available. We show that, with ancillae, the depth can be made polynomial, and the space-depth trade-off is not impaired by the qubit connectivity constraint unless we have exponentially many ancillae. Third, we consider special unitaries, including diagonal unitaries and quantum state preparation, the last being a fundamental task used in many quantum algorithms for machine learning and linear algebra problems.
Join Zoom Meeting: https://nus-sg.zoom.us/j/85687992658?pwd=NTRTc0RiT3d4Z1pTMzA4QXhYRTJ1Zz09