4
The number of runs required is arbitrarily close to 1, using the correct post-processing. See "On the success probability of quantum order finding" by Martin Ekerå from Jan 2022:
We prove a lower bound on the probability of Shor's order-finding algorithm successfully recovering the order r in a single run. The bound implies that by performing two ...
4
Yes, the measurements on the ancillary qubits are unnecessary. You can just discard those qubits instead of measuring them.
4
The accuracy of measuring the correct result is given by a sine $\sin^2((r + \frac{1}{2})\theta)$ where $r$ is the number of Grover iterations and $\theta$ is the angle between starting state (before Grover iteration) $|s\rangle$ and $|s'\rangle$. $|s'\rangle$ is a state perpendicular to our winner, desired output state $|\omega\rangle$. $\theta$ is given by ...
4
Copying over from "Are circuits with more than 1000 gates common?". Note that a Toffoli gate is roughly as expensive as 2T gates or 4T gates, depending on your architecture.
According to Table III of https://arxiv.org/abs/2011.03494 , quantum chemistry algorithms looking at properties of the FeMoCo molecule use half a billion Toffoli gates.
...
3
This is not a complete answer but describes a case where knowing polynomially many Pauli expectation values is not sufficient to solve the same problem. Consider that the set of expectation values for all length-$n$ strings containing Pauli-Z operators is related to the set of probabilities for observing computational basis states by a system of linear ...
3
Many many people refer to Grover's algorithm as a "database search" but this is not a very good description of what it does. It's actually an algorithm that searches for a solution that makes an oracle function return True, where an oracle function is a function that, given an input, outputs whether or not the input is the solution to a problem ...
3
The most useful use-case I found for a big fault-tolerant quantum computer, besides Shor, is a simulation of molecules, which are too hard to simulate on classical computers + demand fault-tolerant computers.
Read this article
Generally speaking, you can see the following demand (depending on the accuracy you want):
The approximation that they are doing ...
2
One "dumb" way to speed-up a generic SAT problem would be to use Grover's Algorithm, but that would only give a quadratic speed-up over brute-force. It may the best one can do for some (or many) situations, but this is the most straight-forward thing that comes to mind.
Grover's algorithm is an algorithm that finds the input that makes an oracle ...
2
Boaz Barak has a lovely essay on various hypothetical worlds with quantum computers. In particular, he calls your world where NP$\subseteq$BQP "popscitopia", and provides:
...in popscitopia quantum computers can be built, and NP $\subseteq$ BQP. This is the world that is described by some popular accounts of quantum computers as being able to “...
1
This is because of these lines of code:
# bob reverse the initialization gate
inverse_init_gate = init_gate.gates_to_uncompute()
qc.append(inverse_init_gate, [2])
These two lines add the gates that set $q_2$ back to $|0\rangle$. Just remove them and the output should look like:
{'1 1 1': 266, '1 0 0': 261, '1 1 0': 240, '1 0 1': 257}
1
I think that something that may answer your question is the technique named `classical shadows' (introduced in https://www.nature.com/articles/s41567-020-0932-7).
The key idea is understand that the state $\rho$ can be approximated as
\begin{equation}
\rho \approx \frac{1}{T}\sum_{t=0}^{T-1}\sigma_1^{(t)}\otimes ... \otimes \sigma_n^{(t)}
\end{equation}
...
1
Cirq has a function cirq.sub_state_vector which can extract a single qubit's state from a full state vector.
It doesn't just do the single qubit case, it can do arbitrary subsets of qubits. It will raise an exception if the subset you pick is entangled with other stuff. It's unfortunately a bit picky about error tolerances and input shape.
1
This happens to be the topic I did my master's thesis on and am still invested in as part of my doctoral research. Very few works existed prior to 2016. The one I found most relevant back then was https://journals.aps.org/pre/abstract/10.1103/PhysRevE.62.7532
My research was on both types of quantum accelerated genome sequence reconstruction: ab-initio (...
Only top voted, non community-wiki answers of a minimum length are eligible