New answers tagged complexity-theory
0
We say that a function $f(n)$ is $O(n)$ if its bounded above by $n$ asymptotically, which is not to be confused with a function $f(n)$ being $\Omega(n)$ which means that $f(n)$ is bounded below by $n$ asymptotically.
Also, there are $2^n$ boolean functions on $\{0,1\}^n$ since each boolean function $f:\{0,1\}^n\rightarrow \{0,1\}$ is in one-to-one ...
1
Oracles in quantum computing are "black boxes" that usually serve as input or help to another larger algorithm. They usually are defined by a function $f: \{0,1\}^n \rightarrow \{0,1\}^m$, which takes an $n$-bit input and produces an $m$-bit output. An important thing to note about oracles is that usually you don't know what is going on inside the ...
2
The IQPE procedure tries to reduce the extra number of ancilla qubits needed to measure the phase and replaces that with the extra number of iterations that we perform to measure our phase.
Imagine you have the phase as $\theta = 0.\theta_{0}\theta_{1}\theta_{2}\theta_{3}$. So, what IQPE does is that in the first iteration, it tries to identify the value of $...
0
OK, my question has some suspicious implicit assumptions. Usually the point of the algorithm is not to prepare a given state $|B\rangle$ from an initial state $|A\rangle$. If $|B\rangle$ encodes the solution to a problem, and if we know $|B\rangle$ right from the start there no need to build an algorithm. Rather, the problem usually is to construct a state $|...
1
A few thoughts:
If you identify a few of the axes of an $n$-qubit state space, those corresponding to bit-strings $|s_1,...,s_n\rangle, s_i\in\{0,1\}$, with "classical states", then it might seem natural to say that "quantum algorithms are allowed to take shortcuts". But I think this picture is actually faulty. When you say this, you are ...
0
A major problem with implementing a hash set on a quantum computer is that, if you are inserting a superposed item, it can go into a superposition of buckets. But if you don't operate on a bucket, you can't possibly have inserted an item into it. Therefore to insert (or query) a superposed item correctly, which goes into a superposition of all the buckets, ...
0
I don't understand all of the details of the protocol, but to provide a tentative answer, in Mahadev's scheme the verifier (Vickey) is always purely classical, and only trades classical information back and forth with the prover (Peggy). Vickey does not do any QMA verification alone, as she is not a QMA machine herself, and doesn't receive any qubits from ...
1
CW from Self-Answer
I asked this question a while ago, and I've learned I think a little bit about many of the outstanding open problems in the field, and more about science communication in general.
Of course I suspect generally most in the QC community want to have the problems that they work on be accessible to a broader audience. And there are, from my ...
Top 50 recent answers are included
