New answers tagged complexity-theory
2
I guess a similar argument used
in $\big[$ Marriot, Watrous $\big] $ [1]
to prove QMA$_{log}$ $\subseteq$ BQP
and
in $\big[$ Fefferman, Lin $\big]$ [2]
to prove QMA$_{exp}$ $\subseteq$ PSPACE
does not carry over since for L $\in $ QMA$_{exp}$ = PreciseQMA you get
$ x \in $ L $ \implies \text{tr}[Q_x] \geq c $
$ x \notin $ L $ \implies \text{tr}[Q_x] \...
1
I can't answer all your questions and I certainly am not an expert, but I have something to say about your first point. According to the first paper linked in my comment (by Aaronson and Chen), the hardness assumptions of BosonSampling hinges on the assumption that there is no $\text{BPP}^{\text{NP}}$ (this is BPP relative to an NP oracle) algorithm for ...
1
I have been doing some work on understanding the thermodynamics of quantum algorithms for my undergraduate thesis.
Where is the Heat coming from?
The first thing you want to think about is, where is the thermodynamics going to come into play? I am choosing to focus on entanglement. Firstly because it's a natural place to build off of from a Landauer's ...
4
The Deutsch-Josza problem provides an oracle separation between $\mathsf{EQP}$ (exact quantum-polynomial time) and $\mathsf{P}$, but there's no preclusion against adding randomization to get an efficient classical algorithm.
For example, the Deutsch-Josza problem is trivially in $\mathsf{BPP}$. One could just make a small number of calls to the oracle; if ...
2
As you've written it, yes. The implication of what you've written is that $|E_0\rangle$ is prepared exactly. Since it has been done efficiently, we know that you must have used only a number of qubits that's polynomial in $n$. Thus, I can measure those poly($n$) qubits and exactly determine the value of $E_0$. Once I have an exact classical value, it's no ...
2
Let $ p_i = |\langle i | \phi \rangle|^2 \sim Dir(a_1, .., a_{2^n}) = Dir(1, .., 1) $ and $ m_i $ the occurences of outcome $ |i\rangle $ on samples $z_1, .. z_k$.
Since the Dirichlet distribution is the conjugate prior of the categorical (see here), meaning
$ \bf{p} $ $| Z, (1, .. 1), $ $\bf{m} $ $ \sim Dir(2^n, $ $\bf{m} + 1$)
and using the formula for the ...
1
Grover's Algorithm uses 2 simple tricks to search an unordered database (like a phonebook that contains names and phone numbers but not in alphabetical order). It inputs an equal superposition of all possible entries and searches the database in one operation. When it finds the matching entry, it marks it by flipping the sign of the wavefunction of this ...
Top 50 recent answers are included
