Real-time evolution of quantum field theories using classical computers requires resources that scale exponentially with the number of lattice sites. Because of a fundamentally different computational strategy, quantum computers can in principle be used to perform detailed studies of these dynamics from first principles. Before performing such calculations, it is important to ensure that the quantum algorithms used do not have a cost that scales exponentially with the volume. In these proceedings, we present an interesting test case: a formulation of a compact U(1) gauge theory in 2+1 dimensions free of gauge redundancies. A naive implementation onto a quantum circuit has a gate count that scales exponentially with the volume. We discuss how to break this exponential scaling by performing an operator redefinition that reduces the non-locality of the Hamiltonian. While we study only one theory as a test case, it is possible that the exponential gate scaling will persist for formulations of other gauge theories, including non-Abelian theories in higher dimensions.