<p>I hope the following partially answers your question. I've never seen this  observation published anywhere (please correct me if I'm wrong).</p>

<p>First of all, FQMA - a quantum analog of FNP - was defined: <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:F#fqma" rel="nofollow">https://complexityzoo.uwaterloo.ca/Complexity_Zoo:F#fqma</a> </p>

<p>One of the compelling reasons to define the complexity class NP is that there is a decision to search reduction: polynomial access to an oracle that solves NP-Complete problems allows you to search for a solution of any problem in FNP in polynomial time. </p>

<p>A decision to search reduction is not known between QMA and FQMA . For example, access to an oracle for the Local Hamiltonian problem is not known to be sufficient to efficiently construct a ground state.</p>

<p>Another related (although, not directly related to your question) reduction which is known for many classical NP problems, but not for QMA problems is downward self reducibility:
A language L is downward self reducible if there is a cook reduction from L to itself such that the queries are shorter than the original input. For example, given a Local Hamiltonian H with m terms, decide whether its minimal energy is below a or above b (where b-a>1/poly) by asking questions regarding Hamiltonians which have m-1 terms or less. Many decision to search reductions have this additional property.</p>

CC BY-SA 3.0
2015-05-13T23:08:48.420Z
2015-05-13T23:08:48.420Z
Or Sattath
<p>Is there any analog of the computational classes $FP$ and $FNP$ with probabilistic or quantum Turing machines? If so, what are the relation with other computational classes?</p>

CC BY-SA 3.0
2015-02-13T17:22:42.073Z
A series of comments before the experts show up: One natural variant is the class of promise problems, prBPP. Goldreich's paper "In a world of P=BPP" also defines "BPP search problems", I believe. Also I see that [FBQP is defined at the complexity zoo](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:F#fbqp) but only one reference. Finally, notice that at least if we don't require the machine's answer to be checkable, then a probabilistic machine can solve impossible-deterministic problems, i.e. "given $n$, produce a string of Kolmogorov complexity at least $n$" (with prob >= 2/3).
usul
CC BY-SA 3.0
2015-02-13T18:43:50.887Z
What's the motivation for considering the functional variants of these classes?
Huck Bennett
CC BY-SA 3.0
2015-02-13T21:54:51.807Z
@usul - Thanks for pointing out the reference in the complexity zoo. Nevertheless, the only relation I found there is an oracle separation between FBQP (quantum analog of FP) and the polynomial local search (PLS).
neophyte
CC BY-SA 3.0
2015-02-13T21:58:56.393Z
@Huck Bennett - Do we need motivations for such a natural generalisation of function problem classes? A function problem is a very natural and well-known notion in computational complexity. It is thus very straightforward to ask what are the function problems solved by probabilistic or quantum Turing machines. If we ask similar questions for decision problems, why not for function problems?
neophyte
CC BY-SA 3.0
2015-02-13T23:02:35.683Z
Well, usually decision problems are simpler and capture the complexity properties that we want to study. Also, your question has an easy answer for decision problems: BPP and MA are the probabilistic analogs of P and NP respectively, while BQP and QMA are the quantum analogs of P and NP respectively. I don't see why you care about sticking an "F" in front of any of these classes.
Huck Bennett
CC BY-SA 3.0
2015-02-14T06:19:34.790Z
@usul: if you require your algorithm to actually compute a *function* (as opposed to a relation) with bounded error, notice that simply generating a random string is disallowed.
Niel de Beaudrap
CC BY-SA 3.0
2015-02-14T08:52:19.373Z
@Huck Bennett - I don't understand your criticism: computing functions is usual in everyday math, and indeed your laptop not only decides problems but does also compute functions. Considering only decision problems limits our view. On the other hand, if men had had considered only simplest things, we wouldn't have had computers and not even wheels.
neophyte
CC BY-SA 3.0
2015-02-14T14:20:48.227Z
@neophyte: I think he's hinting that the answer can be obtained by putting an 'F' in front of the decision class names — and that given this is the case and given that randomised and quantum computation are fairly transparent models if computing (comparatively, contrasting with eg. $\mathrm{Mod}_k \mathrm L$ for $k$ not a prime power), it isn't clear why you might be asking the question. Perhaps you should rephrase your question to ask whether any relations hold which don't follow from those for **BPP** or **BQP**.
Niel de Beaudrap
CC BY-SA 3.0
2015-02-14T22:30:33.680Z
@HuckBennett: functional variants of complexity classes are implicitly used all the time in many-one reductions (e.g. Karp reductions are FP).  I am extremely far from being an expert, so I have no idea how useful it is, but if one ever wants to speak of quantum polytime reductions, one has to define FBQP.  Whether this is immediate or not is not the point, as it is not the point that for most complexity purposes functions reduce to problems.  Besides, it may be my category-theoretical bias but I agree with the OP that functions (which are composable) are much more natural than problems.
Damiano Mazza
CC BY-SA 3.0
2015-02-15T03:05:00.480Z
@DamianoMazza I think you and the others are missing Huck's point. It is just not clear what new complexity issues arise from looking at relation problems (FP and FNP are relation classes btw): does this raise any questions about nondeterminism, randomness, and quantum computation that are not already apparent from looking at decision problems? There are various ways to reduce back and forth between search and decision and often that makes it enough to look at the decision classes.
Sasho Nikolov
CC BY-SA 3.0
2015-02-15T03:09:29.980Z
That being said I think there actually are questions that only become apparent when looking at functions. The example I have in mind are what Gat and Goldwasser called Bellagio algorithms: efficient randomized algorithms that produce a unique answer for every input. Check this http://eccc.hpi-web.de/report/2011/136/
Sasho Nikolov
CC BY-SA 3.0
2015-02-15T09:34:32.163Z
@SashoNikolov: actually, I was trying to say that Huck's point (and your first comment) was not the point :-)  Huck asked for a motivation to consider functions instead of problems.  I gave one: reductions.  You say that "there are various ways to reduce back and forth between search and decision", but none of that would make sense if we were not able to define complexity-bounded *functions* (reductions).  That FP doesn't add anything to P in terms of separation/equality issues seems to me to be beside the point.  Maybe FP is not interesting as a class but some of its inhabitants are!
Damiano Mazza
CC BY-SA 3.0
2015-05-14T02:48:36.197Z
@SashoNikolov: I think Bellagio algorithms should be added as an answer.
Joshua Grochow
CC BY-SA 3.0
2015-05-14T02:49:13.227Z
@neophyte: For finer distinctions within FNP, look up NPSV and NPMV (and their variants).
Joshua Grochow
<quantum-computing><probabilistic-computation>
Probabilistic and quantum analog of $FP$ and $FNP$?
neophyte
# Probabilistic and quantum analog of $FP$ and $FNP$?

(Asked by: username_0 on 2015-02-13)

Is there any analog of the computational classes $FP$ and $FNP$ with probabilistic or quantum Turing machines? If so, what are the relation with other computational classes?

**Tags:** quantum-computing, probabilistic-computation

> **Comments:**
> **username_1**: A series of comments before the experts show up: One natural variant is the class of promise problems, prBPP. Goldreich's paper "In a world of P=BPP" also defines "BPP search problems", I believe. Also I see that [FBQP is defined at the complexity zoo](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:F#fbqp) but only one reference. Finally, notice that at least if we don't require the machine's answer to be checkable, then a probabilistic machine can solve impossible-deterministic problems, i.e. "given $n$, produce a string of Kolmogorov complexity at least $n$" (with prob >= 2/3).  
> **username_2**: What's the motivation for considering the functional variants of these classes?  
> **username_0**: @username_1 - Thanks for pointing out the reference in the complexity zoo. Nevertheless, the only relation I found there is an oracle separation between FBQP (quantum analog of FP) and the polynomial local search (PLS).  
> **username_0**: @username_2 - Do we need motivations for such a natural generalisation of function problem classes? A function problem is a very natural and well-known notion in computational complexity. It is thus very straightforward to ask what are the function problems solved by probabilistic or quantum Turing machines. If we ask similar questions for decision problems, why not for function problems?  
> **username_2**: Well, usually decision problems are simpler and capture the complexity properties that we want to study. Also, your question has an easy answer for decision problems: BPP and MA are the probabilistic analogs of P and NP respectively, while BQP and QMA are the quantum analogs of P and NP respectively. I don't see why you care about sticking an "F" in front of any of these classes.  
> **username_3**: @username_1: if you require your algorithm to actually compute a *function* (as opposed to a relation) with bounded error, notice that simply generating a random string is disallowed.  
> **username_0**: @username_2 - I don't understand your criticism: computing functions is usual in everyday math, and indeed your laptop not only decides problems but does also compute functions. Considering only decision problems limits our view. On the other hand, if men had had considered only simplest things, we wouldn't have had computers and not even wheels.  
> **username_3**: @username_0: I think he's hinting that the answer can be obtained by putting an 'F' in front of the decision class names — and that given this is the case and given that randomised and quantum computation are fairly transparent models if computing (comparatively, contrasting with eg. $\mathrm{Mod}_k \mathrm L$ for $k$ not a prime power), it isn't clear why you might be asking the question. Perhaps you should rephrase your question to ask whether any relations hold which don't follow from those for **BPP** or **BQP**.  
> **username_4**: @HuckBennett: functional variants of complexity classes are implicitly used all the time in many-one reductions (e.g. Karp reductions are FP).  I am extremely far from being an expert, so I have no idea how useful it is, but if one ever wants to speak of quantum polytime reductions, one has to define FBQP.  Whether this is immediate or not is not the point, as it is not the point that for most complexity purposes functions reduce to problems.  Besides, it may be my category-theoretical bias but I agree with the OP that functions (which are composable) are much more natural than problems.  
> **username_5**: @DamianoMazza I think you and the others are missing Huck's point. It is just not clear what new complexity issues arise from looking at relation problems (FP and FNP are relation classes btw): does this raise any questions about nondeterminism, randomness, and quantum computation that are not already apparent from looking at decision problems? There are various ways to reduce back and forth between search and decision and often that makes it enough to look at the decision classes.  
> **username_5**: That being said I think there actually are questions that only become apparent when looking at functions. The example I have in mind are what Gat and Goldwasser called Bellagio algorithms: efficient randomized algorithms that produce a unique answer for every input. Check this http://eccc.hpi-web.de/report/2011/136/  
> **username_4**: @SashoNikolov: actually, I was trying to say that Huck's point (and your first comment) was not the point :-)  Huck asked for a motivation to consider functions instead of problems.  I gave one: reductions.  You say that "there are various ways to reduce back and forth between search and decision", but none of that would make sense if we were not able to define complexity-bounded *functions* (reductions).  That FP doesn't add anything to P in terms of separation/equality issues seems to me to be beside the point.  Maybe FP is not interesting as a class but some of its inhabitants are!  
> **username_6**: @SashoNikolov: I think Bellagio algorithms should be added as an answer.  
> **username_6**: @username_0: For finer distinctions within FNP, look up NPSV and NPMV (and their variants).  

---

## 1 answers

### Answer by username_7 on 2015-05-13. Score: 2

I hope the following partially answers your question. I've never seen this observation published anywhere (please correct me if I'm wrong).

First of all, FQMA - a quantum analog of FNP - was defined: <https://complexityzoo.uwaterloo.ca/Complexity_Zoo:F#fqma>

One of the compelling reasons to define the complexity class NP is that there is a decision to search reduction: polynomial access to an oracle that solves NP-Complete problems allows you to search for a solution of any problem in FNP in polynomial time.

A decision to search reduction is not known between QMA and FQMA . For example, access to an oracle for the Local Hamiltonian problem is not known to be sufficient to efficiently construct a ground state.

Another related (although, not directly related to your question) reduction which is known for many classical NP problems, but not for QMA problems is downward self reducibility:
A language L is downward self reducible if there is a cook reduction from L to itself such that the queries are shorter than the original input. For example, given a Local Hamiltonian H with m terms, decide whether its minimal energy is below a or above b (where b-a>1/poly) by asking questions regarding Hamiltonians which have m-1 terms or less. Many decision to search reductions have this additional property.


---

