15
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Juan Bermejo Vega Nov 27 '11 at 11:48
13
$\begingroup$

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.

$\endgroup$
  • 7
    $\begingroup$ 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). $\endgroup$ – Peter Shor Nov 26 '11 at 20:35
  • $\begingroup$ @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. $\endgroup$ – Tsuyoshi Ito Nov 26 '11 at 22:07
  • $\begingroup$ I don't mind at all. $\endgroup$ – Peter Shor Nov 26 '11 at 23:53
7
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Nov 28 '11 at 14:53
  • $\begingroup$ @TsuyoshiIto: good point, the concept essentially is a promise problem restriction. I've edited the answer to accomodate this concept. $\endgroup$ – Niel de Beaudrap Nov 28 '11 at 15:11
  • $\begingroup$ In case it was not clear, I do not agree with the first paragraph in your answer if we consider promise problems. $\endgroup$ – Tsuyoshi Ito Nov 28 '11 at 18:25
  • $\begingroup$ @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). $\endgroup$ – Niel de Beaudrap Nov 29 '11 at 0:30
4
$\begingroup$

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:

Complexity classes related to quantum proofs and advice

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.

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Nov 26 '11 at 15:10
  • $\begingroup$ 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. $\endgroup$ – Juan Bermejo Vega Nov 26 '11 at 15:45
3
$\begingroup$

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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.