# Tag Info

16

The term quantum supremacy doesn't necessarily mean that one can run algorithms, as such, on a quantum computer that are impractical to run on a classical computer. It just means that a quantum computer can do something that a classical computer will find difficult to simulate. You might ask (and rightly so) what I might possibly mean by talking about ...

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

15

First, let me note that quantum annealing, or more precisely the adiabatic quantum computation model is polynomially equivalent to the conventional gate-based quantum computation model. Second, the general traveling salesman problem is NP complete. Third, it is generally believed that the with gate-based quantum computation one cannot solve in polinomial ...

15

14

From a pseudo-foundational standpoint, the reason why BQP is a differently powerful (to coin a phrase) class than NP, is that quantum computers can be considered as making use of destructive interference. Many different complexity classes can be described in terms of (more or less complicated properties of) the number of accepting branches of an NTM. Given ...

14

The time to solution (tts) is highly dependent on the Hamiltonian of the problem one would like to solve. The D-Wave uses a spin-glass-like Hamiltonian which can be in the NP-Complete complexity class. Due to having to run the annealing process multiple times, tts measures are typically quantified by how long it takes to find the ground state some percent ...

13

This is not a very enlightening concept, because most interesting quantum algorithms, such as Shor's algorithm, involve some classical computations as well. While you can always shoehorn a classical computation into a quantum computer, it would be at unnecessarily exorbitant cost. We don't yet know, of course, exactly what problems will be hard to solve ...

12

Not sure if this is strictly what you're looking for; and I don't know that I'd qualify this as "exponential" (I'm also not a computer scientist so my ability to do algorithm analysis is more or less nonexistent...), but a recent result by Bravyi et. al presented a class of '2D Hidden Linear Function problems' that provably use fewer resources on a quantum ...

12


12

Introduction to the Classical Discrete Fourier transform: The DFT transforms a sequence of $N$ complex numbers $\{\mathbf{x}_n\}:=x_0,x_1,x_2,...,x_{N-1}$ into another sequence of complex numbers $\{\mathbf{X}_k\}:=X_0,X_1,X_2,...$ which is defined by $$X_k=\sum_{n=0}^{N-1}x_n.e^{\pm\frac{2\pi i k n}{N}}$$ We might multiply by suitable normalization ...

11

TL;DR: No, we do not have any precise "general" statement about exactly which type of problems quantum computers can solve, in complexity theory terms. However, we do have a rough idea. According to Wikipedia's sub-article on Relation to to computational complexity theory The class of problems that can be efficiently solved by quantum computers is ...

9

Suppose a function $f\colon {\mathbb F_2}^n \to {\mathbb F_2}^n$ has the following curious property: There exists $s \in \{0,1\}^n$ such that $f(x) = f(y)$ if and only if $x + y = s$. If $s = 0$ is the only solution, this means $f$ is 1-to-1; otherwise there is a nonzero $s$ such that $f(x) = f(x + s)$ for all $x$, which, because $2 = 0$, means $f$ is 2-to-...

9

One possible answer as to why we can realise the QFT efficiently is down to the structure of its coefficients. To be precise, we can represent it easily as a quadratic form expansion, which is a sum over paths which have phases given by a quadratic function: $$F_{2^n} = \frac{1}{\sqrt{2^n}} \sum_{k,x \in \{0,1\}^n} \exp\bigl(i Q(k,x)\... 8 For comparison-based sorting (and search) bounds seem to fit the ones of classical computers: \Omega(N\log N) for sorting and \Omega(\log N) for search, as shown by Hoyer et al. A couple of quantum sorting algorithms are listed in 'Related work' section of "Quantum sort algorithm based on entanglement qubits {00, 11}". 8 DISCLAIMER: The quantum-bogosort is a joke-algorithm Let me just state the algorithm in brief: Step 1: Using a quantum randomization algorithm, randomize the list/array, such that there is no way of knowing what order the list is in until it is observed. This will divide the universe into O(N!) universes; however, the division has no cost, as it happens ... 8 This is deviating a little from the original question, but I hope gives a little more insight that could be relevant to other problems. One might ask "What is it about order finding that lends itself to efficient implementation on a quantum computer?". Order Finding is the main component of factoring algorithms, and includes the Fourier transform as part of ... 8 Short answer: yes One has to be a little bit more careful setting up the question. Thinking about a circuit as being composed of state preparation, unitaries, and measurements, it is always in principle possible to "hide" anything we want, such as entangling operations, inside the measurement. So, let us be precise. We want to start from a separable state ... 7 I'm not sure it really is true to make such a claim, even though it is one that is often seen. Even so, this statement is common because it does point towards a difference between classical computers and quantum ones. Classical computation is essentially a process that takes a single input bit string and keeps transforming it until you get a single output ... 7 The quantum part of Shor's algorithm is, essentially, a single modular exponentiation done under superposition followed by a Fourier transform and then a measurement. The modular exponentiation is by far the most expensive part. Let us assume that [...] each elementary logical operation of mathematical factorization is equally time-costing in classical ... 6 The term quantum supremacy, as introduced by Preskill in 2012 (1203.5813), can be defined by the following sentence: We therefore hope to hasten the onset of the era of quantum supremacy, when we will be able to perform tasks with controlled quantum systems going beyond what can be achieved with ordinary digital computers. Or, as wikipedia rephrases ... 6 In the context of scalable quantum computing, the polylog scaling needed for magic state distillation should not be a problem. Indeed, it is not the only polylog scaling we need to contend with. Using the S and T gates to approximate a general single qubit rotation can have a similar cost when using the Solvay-Kitaev algorithm (though this is no longer ... 6 The only thing I can think of is the algorithm for finding matrix powers which has superpolynomial speed up. It's from this list of quantum algorithms (it seems to be a bit outdated though). 6 There is a newer result from Robert Beals, Stephen Brierley, Oliver Gray, Aram Harrow, Samuel Kutin, Noah Linden, Dan Shepherd, Mark Stather. They present on Table 2 of Efficient Distributed Quantum Computing the results for bubble sort and insertion sort, it is mainly for "network sorting" but they gave more references about sorting. A quick and very ... 6 Yes. This has been done by Morita and Nishimori in their 2008 publication, "Mathematical Foundations of Quantum Annealing." https://arxiv.org/abs/0806.1859 In Section 5 they derive the convergence conditions from path integral Monte Carlo and Green function Monte Carlo methods. To quote; In Sec. 5 we have derived the convergence condition of QA ... 6 There is no such general statement and it is unlikely there will be one soon. I will explain why this is the case. For a partial answer to your question, looking at the problems in the two complexity classes BQP and PostBQP might help. The complexity classes that come closest to the problems that can be solved efficiently by quantum computers of the quantum ... 6 As I mentioned in the comments, a very precise answer will likely depend on a lot of technical choices which are somewhat arbitrary. It is likely to be more important to obtain an order-of-magnitude estimate, and to account for as much as possible in making it. This answer is intended not as a definitive answer, but as a step in the right direction by ... 6 Sometimes, you might know the eigenvector, and the computational question that you want to answer is what the eigenvalue is. For example, any function evaluation f(x) defined by the action of a U$$ U:|x\rangle|y\rangle\mapsto|x\rangle|y\oplus f(x)\rangle $$for x\in\{0,1\}^n, y\in\{0,1\} has well defined eigenvectors,$$ |x\rangle(|0\rangle\pm|1\...

6

If you don't supply a $|u\rangle$ as an input, there are two possible things you might want to get out: The $\varphi$ for a randomly chosen (but unknown) eigenstate $|u\rangle$; Both $\varphi$ and $|u\rangle$ for one or more eigenstates. Let's first look at 1. Since eigenstates form a complete basis, any input state you use can be interpreted as a ...

6

There are a continuous set of possible states for $n$ qubits, each of which can be expressed as a superposition of the $2^n$ basis states. Mostly of these states are highly entangled, and would require highly complex circuits to create (assuming the standard gate set of single qubit rotations and two or three qubit entangling gates). These circuits would ...

5

The exact answer depends on the exact kind of superposition you want. The answers by pyramids and Niel both give you something like $$A\sum_{t=1}^n |\,\,f_t (x)\,\,\rangle \otimes |F_t\rangle$$ Here I've followed Niel in labelling the different functions $f_1$, $f_2$, etc, with $n$ as the total number of functions you want to superpose. Also I've used $F_t$...

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