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

<p>In <a href="https://arxiv.org/abs/0804.3401" rel="nofollow">Quantum Computational Complexity</a>, John Watrous defines the class <strong>QMA</strong> as follows.</p>

<blockquote>
  <p>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:</p>
  
  <ol>
  <li><em>Completeness</em>. 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|)$.</li>
  <li><em>Soundness</em>. 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|)$.</li>
  </ol>
  
  <p>Also define $\text{QMA} = \bigcup_p \text{QMA}_p (2/3, 1/3)$, where
  the union is over all polynomial-bounded functions $p$.</p>
</blockquote>

<p>In <a href="http://rads.stackoverflow.com/amzn/click/0821832298" rel="nofollow">Classical and Quantum Computation</a>, Kitaev et al defined the same class (named as <strong>BQNP</strong>) as follows.</p>

<blockquote>
  <p>A function $F:\mathbb{B}^n \to \left\{0, 1,
 \text{"undefined"}\right\}$ belongs to the class <strong>BQNP</strong> 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</p>
  
  <p>$$ 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. $$</p>
  
  <p>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 &gt; 0$. The quantifiers of $|\xi\rangle$ include only vectors of
  unit length. The <em>quantum probability</em> $\mathbf{P}(\cdot, \cdot)$ is
  defined as follows.</p>
  
  <p>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}$.</p>
</blockquote>

<p><strong>My question:</strong></p>

<p>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?</p>

CC BY-SA 3.0
2016-07-31T21:53:04.423Z
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.
Robin Kothari
CC BY-SA 3.0
2016-07-31T21:55:19.850Z
@RobinKothari, makes sense.
Omar Shehab
<cc.complexity-theory><complexity-classes><quantum-computing><quantum-information><qma>
Two definitions of $QMA$
Omar Shehab
# Two definitions of $QMA$

(Asked by: username_0 on 2016-07-31)

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

In [Quantum Computational Complexity](https://arxiv.org/abs/0804.3401), 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](http://rads.stackoverflow.com/amzn/click/0821832298), 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?

**Tags:** cc.complexity-theory, complexity-classes, quantum-computing, quantum-information, qma

> **Comments:**
> **username_1**: 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.  
> **username_0**: @RobinKothari, makes sense.  

---

## 0 answers

