We consider discrete analogues of fractional Radon transforms involving integration over paraboloids defined by positive definite quadratic forms. We prove sharp results for this class of discrete operators in all dimensions, providing necessary and sufficient conditions for them to extend to bounded operators from l p to l q. The method involves an intricate spectral decomposition according to major and minor arcs, motivated by ideas from the circle method of Hardy and Littlewood. Techniques from harmonic analysis, in particular Fourier transform methods and oscillatory integrals, as well as the number theoretic structure of quadratic forms, exponential sums, and theta functions, play key roles in the proof.