Despite extensive research efforts, few quantum algorithms for classical optimization demonstrate realizable advantage. The utility of many quantum algorithms is limited by high requisite circuit depth and nonconvex optimization landscapes. We tackle
these challenges to quantum advantage with two new variational quantum algorithms, which utilize multi-basis graph encodings and nonlinear activation functions to outperform existing methods with shallow quantum circuits. Additionally, both algorithms provide a polynomial reduction in measurement complexity and either a factor of two speedup textit{or} a factor of two reduction in quantum resources. Typically, the classical simulation of such algorithms with many qubits is impossible due to the exponential scaling of traditional quantum formalism and the limitations of tensor networks. Nonetheless, the shallow circuits and moderate entanglement of our algorithms, combined with efficient tensor method-based simulation, enable us to successfully optimize the MaxCut of high-connectivity graphs with up to $512$ nodes (qubits) on a single GPU.
Hybrid quantum-classical variational algorithms are one of the most propitious implementations of quantum computing on near-term devices, offering classical machine learning support to quantum scale solution spaces. However, numerous studies have dem
onstrated that the rate at which this space grows in qubit number could preclude learning in deep quantum circuits, a phenomenon known as barren plateaus. In this work, we implicate random entanglement as the source of barren plateaus and characterize them in terms of many-body entanglement dynamics, detailing their formation as a function of system size, circuit depth, and circuit connectivity. Using this comprehension of entanglement, we propose and demonstrate a number of barren plateau ameliorating techniques, including: initial partitioning of cost function and non-cost function registers, meta-learning of low-entanglement circuit initializations, selective inter-register interaction, entanglement regularization, the addition of Langevin noise, and rotation into preferred cost function eigenbases. We find that entanglement limiting, both automatic and engineered, is a hallmark of high-accuracy training, and emphasize that as learning is an iterative organization process while barren plateaus are a consequence of randomization, they are not necessarily unavoidable or inescapable. Our work forms both a theoretical characterization and a practical toolbox; first defining barren plateaus in terms of random entanglement and then employing this expertise to strategically combat them.
We investigate two-dimensional atomic arrays as a platform to modify the electromagnetic environment of individual quantum emitters. Specifically, we demonstrate that control over emission linewidths, resonant frequency shifts, and local enhancement
of driving fields is possible due to strong dipole-dipole interactions within ordered, subwavelength atom configurations. We demonstrate that these effects can be used to dramatically enhance coherent dipole-dipole interactions between distant quantum emitters within an atom array. Possible experimental realizations and potential applications are discussed.
