16 citations · 22 across the 2 of their papers we have counts for
3 papers
quant-ph2003★ 16 cited
Commutative version of the k-local Hamiltonian problem and common eigenspace problem
S. Bravyi, M. Vyalyi
We study the complexity of a problem "Common Eigenspace" -- verifying consistency of eigenvalue equations for composite quantum systems. The input of the problem is a family of pai…
cs.CC2003★ 6 cited
Hardness of approximating the weight enumerator of a binary linear code
M. N. Vyalyi
We consider the problem of evaluation of the weight enumerator of a binary linear code. We show that the exact evaluation is hard for polynomial hierarchy. More exactly, if WE is a…
cs.CC2001
A comparison of Zeroes and Ones of a Boolean Polynomial
M. N. Vyalyi
In this paper we consider the computational complexity of the following problem. Let be a Boolean polynomial. What value of , 0 or 1, is taken more frequently? The problem i…