We propose an efficient method for simultaneously optimizing both the structureand parameter values of quantum circuits with only a small computational overhead.Shallow circuits that use structure optimization perform significantly better than cir-cuits that use parameter updates alone, making this method particularly suitable fornoisy intermediate-scale quantum computers. We demonstrate the method for optimiz-ing a variational quantum eigensolver for finding the ground states of Lithium Hydrideand the Heisenberg model in simulation, and for finding the ground state of Hydrogengas on the IBM Melbourne quantum computer.