Density functional theory and quantum computation

We demonstrate the applicability of ground-state and time-dependent density functional theory to quantum computing systems by proving the Hohenberg-Kohn and Runge-Gross theorems for a fermion system representing $N$ qubits. Time-dependent density functional theory is used to determine the minimum energy gap $\Delta (N)$ arising from application of the quantum adiabatic evolution algorithm to the NP-Complete problem MAXCUT. As density functional theory has been used to treat quantum systems with as many as 650 interacting degrees of freedom, this raises the realistic prospect of evaluating the gap $\Delta (N)$ for systems with $N\alt 650$ qubits.