<p>In <a href="https://arxiv.org/abs/1011.3245" rel="nofollow noreferrer">this paper</a>, Aaronson and Arkhipov formulate the <span class="math-container">$GPE_\times$</span> problem as follows: given an <span class="math-container">$n \times n$</span> matrix <span class="math-container">$X$</span> of i.i.d. Gaussian random numbers, find the permanent of <span class="math-container">$X$</span> up to multiplicative error <span class="math-container">$\varepsilon$</span> with success probability over <span class="math-container">$X$</span> at least <span class="math-container">$(1-\delta)$</span>, in polynomial time over <span class="math-container">$n, 1/\varepsilon$</span>, and <span class="math-container">$1/\delta$</span>.</p>
<p>They also formulate the permanent of Gaussians conjecture: if <span class="math-container">$\mathcal{O}$</span> is an oracle for the <span class="math-container">$GPE_\times$</span> problem, then <span class="math-container">$P^{\#P} \subseteq BPP^{\mathcal{O}}$</span>.</p>
<p>I'm trying to understand how an oracle is defined for this problem. To my understanding, normally an oracle is a device that takes the description of a problem instance and returns its solution in one time step. I get how a particular oracle can have approximation error <span class="math-container">$\varepsilon$</span> and success probability <span class="math-container">$1 - \delta$</span> (the latter depends on <span class="math-container">$X$</span>, so the oracle doesn't necessarily have to take any random inputs), but the time requirement puzzles me. How does the poly-time requirement included in the formulation of the problem affect the oracle? Does it mean that we treat queries to such oracles as taking polynomial time, or something else entirely?</p>
<p>In perhaps simpler terms, what is the difference between an oracle for the problem &quot;given <span class="math-container">$X$</span>, find <span class="math-container">$f(X)$</span>&quot; and an oracle for the problem &quot;given <span class="math-container">$X$</span>, find <span class="math-container">$f(X)$</span> <em>in polynomial time over</em> <span class="math-container">$|X|$</span>?</p>

CC BY-SA 4.0
2023-06-07T15:08:53.673Z
One way of handling this is to think of the oracle as a subroutine. It will have an expected time to return an answer and an expected success probability. The only difference is that for an oracle, there is no code to implement it. Is this the way that Aaronson and Arkhipov were thinking of handling it? If the answer isn't given in the paper, maybe you should ask them.
Peter Shor 
CC BY-SA 4.0
2023-06-09T11:06:26.410Z
@PeterShor Good suggestion, I'll take another look at how it is used in the paper and contact them if I don't get it. So far I have a feeling that the poly-time part is used in other context, but is irrelevant for the oracles.
Alexey Uvarov
<cc.complexity-theory><quantum-computing><oracles>
Oracle for the permanent-of-gaussians problem
Alexey Uvarov
# Oracle for the permanent-of-gaussians problem

(Asked by: username_0 on 2023-05-19)

In [this paper](https://arxiv.org/abs/1011.3245), Aaronson and Arkhipov formulate the $GPE\_\times$ problem as follows: given an $n \times n$ matrix $X$ of i.i.d. Gaussian random numbers, find the permanent of $X$ up to multiplicative error $\varepsilon$ with success probability over $X$ at least $(1-\delta)$, in polynomial time over $n, 1/\varepsilon$, and $1/\delta$.

They also formulate the permanent of Gaussians conjecture: if $\mathcal{O}$ is an oracle for the $GPE\_\times$ problem, then $P^{\#P} \subseteq BPP^{\mathcal{O}}$.

I'm trying to understand how an oracle is defined for this problem. To my understanding, normally an oracle is a device that takes the description of a problem instance and returns its solution in one time step. I get how a particular oracle can have approximation error $\varepsilon$ and success probability $1 - \delta$ (the latter depends on $X$, so the oracle doesn't necessarily have to take any random inputs), but the time requirement puzzles me. How does the poly-time requirement included in the formulation of the problem affect the oracle? Does it mean that we treat queries to such oracles as taking polynomial time, or something else entirely?

In perhaps simpler terms, what is the difference between an oracle for the problem "given $X$, find $f(X)$" and an oracle for the problem "given $X$, find $f(X)$ *in polynomial time over* $|X|$?

**Tags:** cc.complexity-theory, quantum-computing, oracles

> **Comments:**
> **username_1**: One way of handling this is to think of the oracle as a subroutine. It will have an expected time to return an answer and an expected success probability. The only difference is that for an oracle, there is no code to implement it. Is this the way that Aaronson and Arkhipov were thinking of handling it? If the answer isn't given in the paper, maybe you should ask them.  
> **username_0**: @PeterShor Good suggestion, I'll take another look at how it is used in the paper and contact them if I don't get it. So far I have a feeling that the poly-time part is used in other context, but is irrelevant for the oracles.  

---

## 0 answers

