In this question, I am trying to understand the equivalence between the following two definitions of the complexity class QMA.

In Quantum Computational Complexity, John Watrous defines the class QMA as follows.

Let $A = (A_{yes}, A_{no})$ be a promise problem, let $p$ be a polynomial-bounded function, and let $a, b: \mathbb{N} \to [0, 1]$ be functions. Then $A \in \text{QMA}_p (a, b)$ if and only if there exists a polynomial-time generated family of circuits $Q = \left\{Q_n : n \in \mathbb{N}\right\}$, where each circuit $Q_n$ takes $n + p (n)$ input qubits and produces one output qubit, with the following properties:

  1. Completeness. For all $x \in A_{yes}$, there exists a $p (|x|)$-qubit quantum state $\rho$ such that $Pr[Q \text{ accepts } (x, \rho)] \ge a (|x|)$.
  2. Soundness. For all $x \in A_{no}$ and all $p(|x|)$-qubit quantum states $\rho$ it holds that $Pr[Q \text{ accepts } (x, \rho)] \le b(|x|)$.

Also define $\text{QMA} = \bigcup_p \text{QMA}_p (2/3, 1/3)$, where the union is over all polynomial-bounded functions $p$.

In Classical and Quantum Computation, Kitaev et al defined the same class (named as BQNP) as follows.

A function $F:\mathbb{B}^n \to \left\{0, 1, \text{"undefined"}\right\}$ belongs to the class BQNP if there exits a polynomial class algorithm that computes a function $x \mapsto Z(x)$, where $Z(x)$ is a description of a quantum circuit, realizing an operator $U_x : \mathcal{B}^{\otimes N_x} \to \mathcal{B}^{\otimes N_x}$ such that

$$ F(x) = 1 \Longrightarrow \exists |\xi\rangle \in \mathcal{B}^{\otimes m_x} \mathbf{P} \left(U_x |\xi\rangle \otimes |0^{N_x - m_x}\rangle, \mathcal{M}\right) \ge p_1,\\ F(x) = 0 \Longrightarrow \forall |\xi\rangle \in \mathcal{B}^{\otimes m_x} \mathbf{P} \left(U_x |\xi\rangle \otimes |0^{N_x - m_x}\rangle, \mathcal{M}\right) \le p_0. $$

Here $\mathcal{M} = \mathbb{C}\left(|1\rangle\right) \otimes \mathcal{B}^{\otimes (N_x - 1)}$, and $p_0, p_1$ satisfy the condition $p_1 - p_0 \ge \Omega (n^{-\alpha})$ for some constant $\alpha > 0$. The quantifiers of $|\xi\rangle$ include only vectors of unit length. The quantum probability $\mathbf{P}(\cdot, \cdot)$ is defined as follows.

For a quantum state given by a density matrix $\rho$ and a subspace $\mathcal{M}$, the probability of the event $\mathcal{M}$ equals $\mathbf{P}(\rho, \mathcal{M}) = Tr(\rho\Pi_\mathcal{M})$. Here, $\Pi_{\mathcal{M}}$ denotes the operator of orthogonal projection onto the subspace $\mathcal{M}$.

My question:

With $F:\mathbb{B}^n \to \left\{0, 1, \text{"undefined"}\right\}$ i.e. not having a promise problem, do Kitaev et al define a broader class of problems?

  • 4
    $\begingroup$ The second definition is the same as the first by defining the function to be undefined outside the promised set. In other words F(x) = "undefined" according to the second definition if and only if x is not contained in $A_\mathrm{yes} \cup A_\mathrm{no}$. Notice that in the second definition there is no condition on the algorithm when x is undefined. $\endgroup$ – Robin Kothari Jul 31 '16 at 21:53
  • $\begingroup$ @RobinKothari, makes sense. $\endgroup$ – Omar Shehab Jul 31 '16 at 21:55

Your Answer


Browse other questions tagged or ask your own question.