# Tag Info

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}

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 ...

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 “...

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 ...

0

A really well-made resource explaining Grovers algorithm is 'How the quantum search algorithm works' on Quantum Country by Andy Matuschak and Michael Nielsen. I think this fits your question nicely, as it is a fundamental algorithm, the explanation does not assume a lot of prior knowledge and the explanation focuses on a conceptual understanding.

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 ...

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. ...

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 $$\rho \approx \frac{1}{T}\sum_{t=0}^{T-1}\sigma_1^{(t)}\otimes ... \otimes \sigma_n^{(t)}$$ ...

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 ...

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 (...

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 ...

0

If an NP-Complete problem is proven to be part of BQP, the whole industry of cryptography will be turned upside-down since the process of mathematically breaking a crypto-system can be expressed as a boolean-SAT problem. It would become much more difficult to establish secret and secure communication, though not entirely impossible because being able to ...

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 ...

0

You are creating a gate from a manually-inputed unitary, and Qiskit does not know how such unitary can be decomposed out of the box. You can either tell Qiskit transpiler not to decompose your unitary, or extend the Equivalence Library (basically, class that stores information on how gates are decomposed) to know how to decompose your gate. The answer to ...

0

In Quirk, you look at state vectors of qubits using the amplitude display. You can get conditional state vectors, such as the state vector implied by a particular measurement result, by combining the amplitude display with a control on the measurement bit. Here is an example: And another example:

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.

Top 50 recent answers are included