Hot answers tagged

16

Have there been any truly ground breaking algorithms besides Grover's and Shor's? It depends on what you mean by "truly ground breaking". Grover's and Shor's are particularly unique because they were really the first instances that showed particularly valuable types of speed-up with a quantum computer (e.g. the presumed exponential improvement for Shor) ...


3

No. Without entanglement we can always write the system as the product state of individual qbits, and those qbits are just a pair of complex numbers. We can thus simulate the quantum system on a classical computer in polynomial time & space, and would not gain any benefit from execution on a quantum computer. There are methods of analysis by which a ...


2

Similar to Blue's picture, I like this one from Quanta Magazine better, since it seem to visually summarize what we are talking about.


2

A qbit is a two-element vector: $|\psi\rangle = \begin{bmatrix} \alpha \\ \beta \end{bmatrix}$ where $\alpha, \beta \in \mathbb{C}$ and $|\alpha|^2 + |\beta|^2 = 1$, a property called the 2-norm. We have two important qbit values which we associate with the classical bits 0 and 1: $|0\rangle = \begin{bmatrix} 1 \\ 0 \end{bmatrix}$ and $|1\rangle = \begin{...


1

Answering what the "actual mechanism" is, is a very difficult question. I don't think there is any widespread consensus as to exactly which aspect of quantum mechanics leads to quantum speed-ups. Or said differently, the answer to "what is the actual mechanism behind quantum computing" is arguably "quantum mechanics", although this is obviously not a very ...


1

Forrelation might be such a problem. The question is "Is a first Boolean function highly correlated with the Fourier transform of a second Boolean function?" This is solved with $1$ quantum query but Aaronson and Ambainis showed that classically one needs $\Omega(\sqrt N /\log N)$ random queries. See also the Quanta magazine article- by the work of Raz ...


Only top voted, non community-wiki answers of a minimum length are eligible