pith. sign in

arxiv: 1001.2314 · v1 · submitted 2010-01-13 · 💻 cs.CC · cs.DM· math.CO· quant-ph

Circuit partitions and #P-complete products of inner products

classification 💻 cs.CC cs.DMmath.COquant-ph
keywords p-completeproductinnerproductsalternatelychosencircuitcomplex
0
0 comments X p. Extension
read the original abstract

We present a simple, natural #P-complete problem. Let G be a directed graph, and let k be a positive integer. We define q(G;k) as follows. At each vertex v, we place a k-dimensional complex vector x_v. We take the product, over all edges (u,v), of the inner product <x_u,x_v>. Finally, q(G;k) is the expectation of this product, where the x_v are chosen uniformly and independently from all vectors of norm 1 (or, alternately, from the Gaussian distribution). We show that q(G;k) is proportional to G's cycle partition polynomial, and therefore that it is #P-complete for any k>1.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.