  This paper introduces state polynomials, i.e., polynomials in noncommuting
variables and formal states of their products. A state analog of Artin's
solution to Hilbert's 17th problem is proved showing that state polynomials,
positive over all matrices and matricial states, are sums of squares with
denominators. Somewhat surprisingly, it is also established that a
Krivine-Stengle Positivstellensatz fails to hold in the state polynomial
setting. Further, archimedean Positivstellens\"atze in the spirit of Putinar
and Helton-McCullough are presented leading to a hierarchy of semidefinite
relaxations converging monotonically to the optimum of a state polynomial
subject to state constraints. This hierarchy can be seen as a state analog of
the Lasserre hierarchy for optimization of polynomials, and the
Navascu\'es-Pironio-Ac\'in scheme for optimization of noncommutative
polynomials. The motivation behind this theory arises from the study of
correlations in quantum networks. Determining the maximal quantum violation of
a polynomial Bell inequality for an arbitrary network is reformulated as a
state polynomial optimization problem. Several examples of quadratic Bell
inequalities in the bipartite and the bilocal tripartite scenario are analyzed.
To reduce the size of the constructed SDPs, sparsity, sign symmetry and
conditional expectation of the observables' group structure are exploited. To
obtain the above-mentioned results, techniques from noncommutative algebra,
real algebraic geometry, operator theory, and convex optimization are employed.
