What is the complexity class for quantum subroutines taking in arbitrary quantum states as inputs?

Question

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?

Answer 1

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.

Answer 2

Something you might be interested in is the notion of quantum oracle introduced by Aaronson and Kuperberg in arXiv: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 and QCMA.

Answer 3

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.

Answer 4

Correct me if I am wrong, but it seems to me that you are interested in the class BQP/qpoly. 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" where you can find the following hierarchy:

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 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.

Answer 5

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 -Tomoyuki Yamakami
2. On the Complexity of Quantum Languages -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