Skip to main content
5 votes

Is APPROX-QCIRCUIT-PROB a BQP-complete problem?

In BQP-Complete Problems by Zhang (2012) Like many [...] "semantic" complexity classes, BQP is not known to contain complete problems.What people usually study for completeness, in such a ...
Egretta.Thula's user avatar
4 votes

Is APPROX-QCIRCUIT-PROB a BQP-complete problem?

Just to further @Egretta.Thula's answer, a portion of the Wikipedia article on the APPROX-QCIRCUIT-PROB mentions $\alpha$ and $\beta$ and stated: Note that the problem does not specify the behavior ...
Mark Spinelli's user avatar
3 votes
Accepted

Truncated Qumode States and Support

Your guess is correct that this is not possible. A $d\times d$ matrix times an $d\times 1$ column vector gives you another $d\times 1$ column vector, so your truncated unitary cannot take the vector ...
Quantum Mechanic's user avatar
3 votes
Accepted

Quantum compilation algorithm with respect to other Shatten $p$-norm

Yes, you get the same behavior. This is because all norms on finite dimensional spaces are equivalent. That means that for every $p$ there exist constants $c_p, d_p > 0$ such that $$ d_p \|X\|_p \...
Rammus's user avatar
  • 5,968
3 votes
Accepted

Calculation of Trotter-Suzuki error bound

There are two aspects of your question that I will address separately: the computational and analytical. I believe the underlying issue is the same, but I will nonetheless address them separately. ...
Jacob's user avatar
  • 645
3 votes
Accepted

Clifford circuit approximation to a random Clifford circuit

Clifford operations are discrete. They can't approximate arbitrary states. The state may not be close to a state reachable by Clifford operations. There are $O(L^2)$ distinct $L$-qubit states ...
Craig Gidney's user avatar
  • 38.6k
2 votes
Accepted

Bounding operator norm by total variation distance

No you cannot, here's a counterexample. Let $U=I$ be the identity matrix and let $S = \sum_{i} (-1)^{\delta_{0,i}} |i\rangle \langle i|$ where $\delta_{i,j}$ is the Kronecker delta. That is, $S$ is ...
Rammus's user avatar
  • 5,968

Only top scored, non community-wiki answers of a minimum length are eligible