Some physical implementation schemes of quantum computing can apply two-qubit gates only on certain pairs of qubits. These connectivity constraints are commonly viewed as a significant disadvantage. For example, compiling an unrestricted$n$-qubit quantum circuit to one with poor qubit connectivity, such as a 1-D chain, usually results in a blowup of depth by$O(n^{2})$and size by$O(n)$. It is appealing to conjecture that this overhead is unavoidable—a random circuit on$n$qubits has$\Theta (n)$two-qubit gates in each layer and a constant fraction of them act on qubits separated by distance$\Theta (n)$. While it is known that almost all$n$-qubit unitary operations need quantum circuits of$\Omega (4^{n}/n)$depth and$\Omega (4^{n})$size to realize with all-to-all qubit connectivity, in this article, we show that all$n$-qubit unitary operations can be implemented by quantum circuits of$O(4^{n}/n)$depth and$O(4^{n})$size even under 1-D chain qubit connectivity constraint. We extend this result and investigate qubit connectivity in three directions. First, we consider more general connectivity graphs and show that the circuit size can always be made$O(4^{n})$as long as the graph is connected. For circuit depth, we study$d$-dimensional grids, complete$d$-ary trees and expander graphs, and show results similar to the 1-D chain. Second, we consider the case when ancillary qubits are available. We show that, with ancilla, the circuit depth can be made polynomial, and the space-depth trade-off is not impaired by connectivity constraints unless we have exponentially many ancillary qubits. Third, we obtain nearly optimal results on special families of unitaries, including diagonal unitaries, 2-by-2 block diagonal unitaries, and quantum state preparation (QSP) unitaries, the last being a fundamental task used in many quantum algorithms for machine learning and linear algebra.

The Quantum State Preparation problem aims to prepare an n-qubit quantum state |ψv=k=02n-1vk|k from the initial state |0n, for a given unit vector v=(v0,v1,v2,v2n-1)TC2n with ||v||2=1. The problem is of fundamental importance in quantum algorithm design, Hamiltonian simulation and quantum machine learning, yet its circuit depth complexity remains open when ancillary qubits are available. In this paper, we study quantum circuits when there are m ancillary qubits available. We construct, for any m, circuits that can prepare |ψvin depth Õ(2nm+n+n) and size O(2n), achieving the optimal value for both measures simultaneously. These results also imply a depth complexity of (4nm+n) for quantum circuits implementing a general n-qubit unitary for any m≤O(2n/n) number of ancillary qubits. This resolves the depth complexity for circuits without ancillary qubits. And for circuits with exponentially many ancillary qubits, our result quadratically improves the currently best upper bound of O(4n) to ˜(2n). Our circuits are deterministic, prepare the state and carry out the unitary precisely, utilize the ancillary qubits tightly and the depths are optimal in a wide parameter regime. The results can be viewed as (optimal) time-space trade-off bounds, which is not only theoretically interesting, but also practically relevant in the current trend that the number of qubits starts to take off, by showing a way to use a large number of qubits to compensate the short qubit lifetime.

Non-negative Matrix Factorization (NMF) asks to decompose a (entry-wise) non-negative matrix into the product of two smaller-sized nonnegative matrices, which has been shown intractable in general. In order to overcome this issue, separability assumption is introduced which assumes all data points are in a conical hull. This assumption makes NMF tractable and widely used in text analysis and image processing, but still impractical for huge-scale datasets. In this paper, inspired by recent development on dequantizing techniques, we propose a new classical algorithm for separable NMF problem. Our new algorithm runs in polynomial time in the rank and logarithmic in the size of input matrices, which achieves an exponential speedup in the low-rank setting.