<p>I think that what you want to know about is quantum analogs of classes of function problems.  (Thanks to Peter Shor for pointing out this concise description in a comment.)</p>

<p>An abstract process which takes a quantum state of fixed size as the input and produces a quantum state of fixed size as the output is called a <em>quantum channel</em>.  In your situation, we do not want to fix the input size or the output size, and therefore we naturally consider a family of quantum channels as the quantum analog of functions from classical strings to classical strings.</p>

<p>It is clearly possible to define the class of families of quantum channels which can be implemented/approximated by families of efficient quantum circuits (with suitable notions of efficiency, uniformity, and approximation).  I do not know if this class has any standard name (but see Peter Shor’s comment for a suggestion).</p>

<p>In my speculation, classes of quantum channels are not often studied because one of the reason to consider complexity classes is in order to compare the powers of different computational models, and classes of quantum channels cannot be used to compare classical and quantum computational models.  However, it is perfectly fine to define and talk about such classes if anything interesting can be proved about them.</p>

CC BY-SA 3.0
2011-11-26T20:35:18.733Z
These are quantum analogs of function classes. You name function classes by prefixing an F to the name; e.g., NP is the decision class, and FNP is the corresponding function class. Presumably, you should name quantum function classes by prefixing a QF to the name, yielding QFBQP for the class you want (which would be distinguished from FBQP, the class of classical functions you can compute in polynomial time with bounded error on a quantum computer).
Peter Shor 
CC BY-SA 3.0
2011-11-26T22:07:01.163Z
@Peter: Thanks for the comment.  “Quantum analogs of function classes” is a very good way to summarize what I am talking about in this answer, and I updated the answer using that description.  Hope you do not mind.
Tsuyoshi Ito
CC BY-SA 3.0
2011-11-26T23:53:42.593Z
I don't mind at all.
Peter Shor 
CC BY-SA 3.0
2011-11-26T15:08:11.933Z
2011-11-26T22:05:10.413Z
2011-11-26T22:05:10.413Z
Tsuyoshi Ito
<p>Something you might be interested in is the notion of <em>quantum oracle</em> introduced by Aaronson and Kuperberg in <a href="http://arxiv.org/abs/quant-ph/0604056">arXiv:quant-ph/0604056</a>.
Quoting from their paper:</p>

<blockquote>
  <p>Just as a classical oracle models a subroutine to which
  an algorithm has black-box access, so a quantum oracle models a quantum subroutine, which can take quantum input
  and produce quantum output.</p>
</blockquote>

<p>This doesn't directly answer your question about a definition of a complexity class that represents the model you describe.
Still, the notion of quantum oracle has relevance in complexity theory: in their paper Aaronson and Kuperberg use a quantum oracle to give a separation between <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aQ#qma">QMA</a> and <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aQ#qcma">QCMA</a>.</p>

CC BY-SA 3.0
2011-11-26T17:05:25.760Z
2011-11-26T17:11:24.760Z
2011-11-26T17:11:24.760Z
Alessandro Cosentino
<p>I think that a complexity class for <em>decision problems</em>, taking quantum states as input is likely to have a fragile definition. For promise problems, either the definition will be sensitive to numerical choices, or it will essentially solve classical decision/promise problems encoded in some efficiently-decodable basis of quantum states.</p>

<p>Tsuyoshi's answer describes what I would consider the correct generalization of function problems. If what you want is a generalization of decision problems, you could specialize to families of channels $\Phi_n: \mathrm L(\mathcal H_2^{\otimes n}) \to \mathrm L(\mathcal H_2)$ from <em>n</em>-qubit states to single qubit states. Of course, a quantum circuit is a perfectly good channel; if we are going to speak of performing specific channels which are comp&shy;u&shy;ta&shy;tion&shy;ally bounded, we may as well just speak of uniform quantum circuit families (or for that matter, any uniform way of  implementing a CPTP map). For good measure, the circuit should end with a standard basis measurement, if we want to retain the semantics of <em>deciding</em> something with bounded probability.</p>

<p>Suppose we define a "quantum language" $\mathcal L$ to consist of subsets of the density operators on <em>n</em>&nbsp;qubits, ranging over all <em>n</em>. In defining some quantum-input, bounded error quantum polytime class <strong>QBQP</strong>, we cannot hope to perform a crisp division between states in the language and states outside of the language, and at the same time bound the probability of acceptance for NO instances away from those of YES instances as we do for <strong>BQP</strong> and <strong>BPP</strong>; any state $\rho&#39;$ which is very close to a state $\rho \in \mathcal L$ (either having high overlap or low trace-distance) is going to yield an acceptance probability very close to that of $\rho$, whether or not $\rho&#39;$ is in the $\mathcal L$. So it seems to me that a class <strong>QBQP</strong> would only contain "quantum promise problems", in which the input is promised to belong to a class of YES instances or of NO instances which do not exhaust the space of all possible states. (A quantum-language decision class with <em>unbounded</em> error, a sort of <strong>QPQP</strong> class, may not be restricted to a promise-problem formulation to be meaningful.)</p>

<p>In addition to this, it seems likely &mdash; because the no-cloning theorem prevents you from making copies of your input state &mdash; that you can't amplify the success probability. So any definition of <strong>QBQP</strong> which involved some constant success probability bounded away from 1/2 would probably depend critically on just what that probability was. To avoid this, as with the function classes <strong>FBPP</strong> and <strong>FBQP</strong>, we would in practise probably define <strong>QBQP</strong> so that for an input state in $\mathcal L$ in <strong>QBQP</strong>, any state in $\mathcal L$ yields the outcome <em>1</em> (from the final measurement) with probability 1&nbsp;&minus;&nbsp;<em>o</em>(1), that is a probability which is closer to certainty as the input size grows &mdash; and similarly, the probability of rejection of any state that the decision routine is <em>able</em> to reject should also converge to zero.</p>

<p>The quantum-promise problems that a <strong>QBQP</strong> circuit (for inputs of size <em>n</em>) would be able to distinguish would then be </p>

<ul>
<li>For YES instances: some set of pure states in some subspace of $\mathcal H_2^{\otimes n}$, and any mixtures allowed by the promise;</li>
<li>For NO instances, mixtures of pure states which are <em>orthogonal</em> to that subspace (or at least, all of the orthocomplementary states allowed by the promise).</li>
</ul>

<p>On top of these classes of states may be a miasma of nearby states which are allowed by the promise, and are very close to states belonging to one of the two classes above; but asymptotically, the classes of states satisfied by the promise would converge to these two classes as <em>n</em> grows. The circuit involved in the decision procedure would then essentially correspond to a circuit which maps some basis of pure states in $\mathcal L$ &mdash; together with a basis for the "ortho&shy;comple&shy;men&shy;tary quantum language" (so to speak) $\mathcal L^\bot$ &mdash; to the standard basis, and decides which of those com&shy;pu&shy;ta&shy;tional basis states correspond to states in the quantum language. In short, it would solve a <em>classical</em> decision or promise problem, encoded in quantum states, with error converging to zero.</p>

CC BY-SA 3.0
2011-11-28T14:53:08.130Z
I would use the promise problem formulation to define the quantum analogs of classes of decision problems because of the bounded-error issue which you pointed out in this answer.
Tsuyoshi Ito
CC BY-SA 3.0
2011-11-28T15:11:57.923Z
@TsuyoshiIto: good point, the concept essentially is a promise problem restriction. I've edited the answer to accomodate this concept.
Niel de Beaudrap
CC BY-SA 3.0
2011-11-28T18:25:44.657Z
In case it was not clear, I do not agree with the first paragraph in your answer if we consider promise problems.
Tsuyoshi Ito
CC BY-SA 3.0
2011-11-29T00:30:14.913Z
@TsuyoshiIto: you're right to point out that I didn't mention promise problems in the first paragraph; as for whether the original was still accurate for promise problems, I suppose this depends on whether you interpret 'fragile' to mean sensitive to numerical choices. In any case, I've revised that paragraph to better reflect the answer (including a description of the sensitivity which persists for promise problems).
Niel de Beaudrap
CC BY-SA 3.0
2011-11-28T14:36:18.590Z
2011-11-29T00:28:26.587Z
2011-11-29T00:28:26.587Z
Niel de Beaudrap
<p>Correct me if I am wrong, but it seems to me that you are interested in the class <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo:B#bqpqpoly" rel="nofollow noreferrer">BQP/qpoly</a>. Definition from Complexity Zoo: "The class of problems solvable by a BQP machine that receives a quantum state ψn as advice, which depends only on the input length n."</p>

<p>If it is that one, in the website you can find relationships of this class to other complexity classes. If it is not, this website also contains information about what happens to BQP when you use different types of advice.</p>

<p>There is also  a relatively recent work about the "<a href="http://arxiv.org/abs/1004.0377" rel="nofollow noreferrer">characterisation of quantum advice</a>" where you can find the following hierarchy:</p>

<p><img src="https://i.sstatic.net/daMHQ.png" alt="Complexity classes related to quantum proofs and advice"></p>

<p>I do not know how much of this info is already in Complexity Zoo. If you are interested in the paper, the authors have also given a <a href="http://www.google.com/url?sa=t&amp;rct=j&amp;q=&amp;esrc=s&amp;source=web&amp;cd=3&amp;sqi=2&amp;ved=0CDoQFjAC&amp;url=http://www.scottaaronson.com/talks/advqip.ppt&amp;ei=ntbQTuPdEcPUsgbRg9zdDA&amp;usg=AFQjCNEvP_cONVOXZgpFWmhSVz9ILSFonw&amp;sig2=2XS_mlFcYz1p5VBQ5BSlUQ" rel="nofollow noreferrer">talk</a> about it.</p>

<p><strong>Edit</strong>
I wonder if by "arbitrary" you mean a state generated by a more general quantum process that 'unitary evolution acting on computational basis states' like dissipative evolution. In this specific latter case you do not have more computational power than BQP as it is shown in <a href="http://arxiv.org/abs/1105.3986" rel="nofollow noreferrer">this article</a>.</p>

CC BY-SA 3.0
2011-11-26T15:10:29.980Z
I think that the asker mentioned quantum advice in the question to clarify that what he wants to know about is different from quantum advice.
Tsuyoshi Ito
CC BY-SA 3.0
2011-11-26T15:45:55.027Z
Yes, that's why I had doubts. It is not clear to me how much "arbitrary" the state can be in the question.
>What is the complexity class for polynomial time quantum subroutines taking in arbitrary quantum states as inputs.

I understand here that the "arbitrary" initial state has to be given to you by someone, but maybe the asker is interested in more realistic setups.
Juan Bermejo Vega
CC BY-SA 3.0
2011-11-26T12:14:32.350Z
2011-11-27T11:55:27.867Z
2011-11-27T11:55:27.867Z
Juan Bermejo Vega
<p>Here are some references on quantum languages, i.e., decision problems with quantum inputs.  There are probably many more.  </p>

<ol>
<li><a href="http://arxiv.org/abs/quant-ph/0308125" rel="nofollow"><strong>Quantum NP and a Quantum Hierarchy</strong></a> -Tomoyuki Yamakami  </li>
<li><a href="http://arxiv.org/pdf/quant-ph/0404062v1" rel="nofollow"><strong>On the Complexity of Quantum Languages</strong></a> -Elham Kashefi, Carolina Moura Alves  </li>
<li><strong>An efficient test for product states, with applications to quantum Merlin-Arthur games</strong> -Aram Harrow, Ashley Montanaro, DOI: 10.1109/FOCS.2010.66, Abstract: arxiv.org/abs/1001.0017v3  </li>
</ol>

CC BY-SA 3.0
2011-11-28T15:33:26.470Z
2011-12-05T09:19:59.443Z
2011-12-05T09:19:59.443Z
Anonymous
<p>The complexity class BQP corresponds to polynomial time quantum subroutines taking in classical inputs and spitting out a probabilistic classical output. Quantum advice modifies that to include copies of some predetermined quantum advice states but with classical inputs as usual. What is the complexity class for polynomial time quantum subroutines taking in arbitrary quantum states as inputs, with one copy only due to no cloning, and spitting out quantum states as an output?</p>

CC BY-SA 3.0
2011-11-27T11:48:08.100Z
Could you specify how arbitrary your state can be? 'anything in the Hilbert space', 'something generated by a certain family of realistic quantum channels', etc
Juan Bermejo Vega
<cc.complexity-theory><complexity-classes><quantum-computing>
What is the complexity class for quantum subroutines taking in arbitrary quantum states as inputs?
Timmy
# What is the complexity class for quantum subroutines taking in arbitrary quantum states as inputs?

(Asked by: username_0 on 2011-11-26)

The complexity class BQP corresponds to polynomial time quantum subroutines taking in classical inputs and spitting out a probabilistic classical output. Quantum advice modifies that to include copies of some predetermined quantum advice states but with classical inputs as usual. What is the complexity class for polynomial time quantum subroutines taking in arbitrary quantum states as inputs, with one copy only due to no cloning, and spitting out quantum states as an output?

**Tags:** cc.complexity-theory, complexity-classes, quantum-computing
> **Comments:**
> **username_1**: Could you specify how arbitrary your state can be? 'anything in the Hilbert space', 'something generated by a certain family of realistic quantum channels', etc  

---

## 5 answers

### Answer by username_2 on 2011-11-26. Score: 13

I think that what you want to know about is quantum analogs of classes of function problems. (Thanks to Peter Shor for pointing out this concise description in a comment.)

An abstract process which takes a quantum state of fixed size as the input and produces a quantum state of fixed size as the output is called a *quantum channel*. In your situation, we do not want to fix the input size or the output size, and therefore we naturally consider a family of quantum channels as the quantum analog of functions from classical strings to classical strings.

It is clearly possible to define the class of families of quantum channels which can be implemented/approximated by families of efficient quantum circuits (with suitable notions of efficiency, uniformity, and approximation). I do not know if this class has any standard name (but see Peter Shor’s comment for a suggestion).

In my speculation, classes of quantum channels are not often studied because one of the reason to consider complexity classes is in order to compare the powers of different computational models, and classes of quantum channels cannot be used to compare classical and quantum computational models. However, it is perfectly fine to define and talk about such classes if anything interesting can be proved about them.

> **Comments:**
> **username_3**: These are quantum analogs of function classes. You name function classes by prefixing an F to the name; e.g., NP is the decision class, and FNP is the corresponding function class. Presumably, you should name quantum function classes by prefixing a QF to the name, yielding QFBQP for the class you want (which would be distinguished from FBQP, the class of classical functions you can compute in polynomial time with bounded error on a quantum computer).  
> **username_2**: @Peter: Thanks for the comment.  “Quantum analogs of function classes” is a very good way to summarize what I am talking about in this answer, and I updated the answer using that description.  Hope you do not mind.  
> **username_3**: I don't mind at all.  

---

### Answer by username_4 on 2011-11-26. Score: 7

Something you might be interested in is the notion of *quantum oracle* introduced by Aaronson and Kuperberg in [arXiv:quant-ph/0604056](http://arxiv.org/abs/quant-ph/0604056).
Quoting from their paper:

> Just as a classical oracle models a subroutine to which
> an algorithm has black-box access, so a quantum oracle models a quantum subroutine, which can take quantum input
> and produce quantum output.

This doesn't directly answer your question about a definition of a complexity class that represents the model you describe.
Still, the notion of quantum oracle has relevance in complexity theory: in their paper Aaronson and Kuperberg use a quantum oracle to give a separation between [QMA](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aQ#qma) and [QCMA](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aQ#qcma).


---

### Answer by username_5 on 2011-11-28. Score: 5

I think that a complexity class for *decision problems*, taking quantum states as input is likely to have a fragile definition. For promise problems, either the definition will be sensitive to numerical choices, or it will essentially solve classical decision/promise problems encoded in some efficiently-decodable basis of quantum states.

Tsuyoshi's answer describes what I would consider the correct generalization of function problems. If what you want is a generalization of decision problems, you could specialize to families of channels $\Phi\_n: \mathrm L(\mathcal H\_2^{\otimes n}) \to \mathrm L(\mathcal H\_2)$ from *n*-qubit states to single qubit states. Of course, a quantum circuit is a perfectly good channel; if we are going to speak of performing specific channels which are comp­u­ta­tion­ally bounded, we may as well just speak of uniform quantum circuit families (or for that matter, any uniform way of implementing a CPTP map). For good measure, the circuit should end with a standard basis measurement, if we want to retain the semantics of *deciding* something with bounded probability.

Suppose we define a "quantum language" $\mathcal L$ to consist of subsets of the density operators on *n* qubits, ranging over all *n*. In defining some quantum-input, bounded error quantum polytime class **QBQP**, we cannot hope to perform a crisp division between states in the language and states outside of the language, and at the same time bound the probability of acceptance for NO instances away from those of YES instances as we do for **BQP** and **BPP**; any state $\rho'$ which is very close to a state $\rho \in \mathcal L$ (either having high overlap or low trace-distance) is going to yield an acceptance probability very close to that of $\rho$, whether or not $\rho'$ is in the $\mathcal L$. So it seems to me that a class **QBQP** would only contain "quantum promise problems", in which the input is promised to belong to a class of YES instances or of NO instances which do not exhaust the space of all possible states. (A quantum-language decision class with *unbounded* error, a sort of **QPQP** class, may not be restricted to a promise-problem formulation to be meaningful.)

In addition to this, it seems likely — because the no-cloning theorem prevents you from making copies of your input state — that you can't amplify the success probability. So any definition of **QBQP** which involved some constant success probability bounded away from 1/2 would probably depend critically on just what that probability was. To avoid this, as with the function classes **FBPP** and **FBQP**, we would in practise probably define **QBQP** so that for an input state in $\mathcal L$ in **QBQP**, any state in $\mathcal L$ yields the outcome *1* (from the final measurement) with probability 1 − *o*(1), that is a probability which is closer to certainty as the input size grows — and similarly, the probability of rejection of any state that the decision routine is *able* to reject should also converge to zero.

The quantum-promise problems that a **QBQP** circuit (for inputs of size *n*) would be able to distinguish would then be

* For YES instances: some set of pure states in some subspace of $\mathcal H\_2^{\otimes n}$, and any mixtures allowed by the promise;
* For NO instances, mixtures of pure states which are *orthogonal* to that subspace (or at least, all of the orthocomplementary states allowed by the promise).

On top of these classes of states may be a miasma of nearby states which are allowed by the promise, and are very close to states belonging to one of the two classes above; but asymptotically, the classes of states satisfied by the promise would converge to these two classes as *n* grows. The circuit involved in the decision procedure would then essentially correspond to a circuit which maps some basis of pure states in $\mathcal L$ — together with a basis for the "ortho­comple­men­tary quantum language" (so to speak) $\mathcal L^\bot$ — to the standard basis, and decides which of those com­pu­ta­tional basis states correspond to states in the quantum language. In short, it would solve a *classical* decision or promise problem, encoded in quantum states, with error converging to zero.

> **Comments:**
> **username_2**: I would use the promise problem formulation to define the quantum analogs of classes of decision problems because of the bounded-error issue which you pointed out in this answer.  
> **username_5**: @TsuyoshiIto: good point, the concept essentially is a promise problem restriction. I've edited the answer to accomodate this concept.  
> **username_2**: In case it was not clear, I do not agree with the first paragraph in your answer if we consider promise problems.  
> **username_5**: @TsuyoshiIto: you're right to point out that I didn't mention promise problems in the first paragraph; as for whether the original was still accurate for promise problems, I suppose this depends on whether you interpret 'fragile' to mean sensitive to numerical choices. In any case, I've revised that paragraph to better reflect the answer (including a description of the sensitivity which persists for promise problems).  

---

### Answer by username_1 on 2011-11-26. Score: 4

Correct me if I am wrong, but it seems to me that you are interested in the class [BQP/qpoly](http://qwiki.stanford.edu/index.php/Complexity_Zoo:B#bqpqpoly). Definition from Complexity Zoo: "The class of problems solvable by a BQP machine that receives a quantum state ψn as advice, which depends only on the input length n."

If it is that one, in the website you can find relationships of this class to other complexity classes. If it is not, this website also contains information about what happens to BQP when you use different types of advice.

There is also a relatively recent work about the "[characterisation of quantum advice](http://arxiv.org/abs/1004.0377)" where you can find the following hierarchy:

![Complexity classes related to quantum proofs and advice](https://i.sstatic.net/daMHQ.png)

I do not know how much of this info is already in Complexity Zoo. If you are interested in the paper, the authors have also given a [talk](http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=3&sqi=2&ved=0CDoQFjAC&url=http://www.scottaaronson.com/talks/advqip.ppt&ei=ntbQTuPdEcPUsgbRg9zdDA&usg=AFQjCNEvP_cONVOXZgpFWmhSVz9ILSFonw&sig2=2XS_mlFcYz1p5VBQ5BSlUQ) about it.

**Edit**
I wonder if by "arbitrary" you mean a state generated by a more general quantum process that 'unitary evolution acting on computational basis states' like dissipative evolution. In this specific latter case you do not have more computational power than BQP as it is shown in [this article](http://arxiv.org/abs/1105.3986).

> **Comments:**
> **username_2**: I think that the asker mentioned quantum advice in the question to clarify that what he wants to know about is different from quantum advice.  
> **username_1**: Yes, that's why I had doubts. It is not clear to me how much "arbitrary" the state can be in the question. >What is the complexity class for polynomial time quantum subroutines taking in arbitrary quantum states as inputs.  I understand here that the "arbitrary" initial state has to be given to you by someone, but maybe the asker is interested in more realistic setups.  

---

### Answer by username_6 on 2011-11-28. Score: 3

Here are some references on quantum languages, i.e., decision problems with quantum inputs. There are probably many more.

1. [**Quantum NP and a Quantum Hierarchy**](http://arxiv.org/abs/quant-ph/0308125) -Tomoyuki Yamakami
2. [**On the Complexity of Quantum Languages**](http://arxiv.org/pdf/quant-ph/0404062v1) -Elham Kashefi, Carolina Moura Alves
3. **An efficient test for product states, with applications to quantum Merlin-Arthur games** -Aram Harrow, Ashley Montanaro, DOI: 10.1109/FOCS.2010.66, Abstract: arxiv.org/abs/1001.0017v3


---

