Search

The standard circuit model for quantum computation presumes the ability to directly perform gates between arbitrary pairs of qubits, which is unlikely to be practical for large-scale experiments. Power-law interactions with strength decaying as $1/r^\alpha$ in the distance $r$ provide an experimentally realizable resource for information processing, whilst still retaining long-range connectivity. We leverage the power of these interactions to implement a fast quantum fanout gate with an arbitrary number of targets. Our implementation allows the quantum Fourier transform (QFT) and Shor's algorithm to be performed on a $D$-dimensional lattice in time logarithmic in the number of qubits for interactions with $\alpha \le D$. As a corollary, we show that power-law systems with $\alpha \le D$ are difficult to simulate classically even for short times, under a standard assumption that factoring is classically intractable. Complementarily, we develop a new technique to give a general lower bound, linear in the size of the system, on the time required to implement the QFT and the fanout gate in systems that are constrained by a linear light cone. This allows us to prove an asymptotically tighter lower bound for long-range systems than is possible with previously available techniques., Comment: 6 pages, 1 figure

In this thesis, we focus on the questions of how quantum entanglement can be generated between two or more spatially separated systems and, once generated, how it can be applied in quantum technology. First we will discuss a protocol, which we conjecture to be optimal in some regimes, that quickly creates entangled states across long distances in systems with power-law interactions. We will discuss how this protocol compares with currently known bounds on entangled state generation and how it might be implemented in a three-dimensional lattice of Rydberg atoms. Next, we will turn our attention to more general questions of how the Lieb-Robinson bound and other limitations on entanglement can be used to inform the design of quantum computers. Quantum computers will be required to create entanglement if they are to realize significant advantages over classical computers, meaning that the generation of entanglement is an important question. First, we will discuss the implications of the Lieb-Robinson bound on graph descriptions of quantum computer architectures, and how the relevant graph parameter (diameter) compares to likely cost functions for architectures, such as maximum graph degree and total number of necessary connections. We will present a proposed graph architecture, the hierarchical product, which we believe provides excellent balance between these considerations. We will then introduce new methods of evaluating graphs that allow us to include quantum architectures capable of measurement and feedback operations. After doing so, we will show that the generation of entanglement entropy becomes a limit on computation. We will show that, for several possible physical models of computation, the generation of entanglement can be bounded by simple graph properties. We demonstrate a connection between worst-case scenarios for entanglement generation and a graph quantity called the Cheeger constant or isoperimetric number, which we evaluate for several proposed quant