Questions tagged [quantum-algorithms]

For questions about quantum algorithms, that is, sequences of quantum gates, operations, and measurements, whose purpose which achieve some goal. Standard examples are Shor's and Grover's algorithms.

Filter by
Sorted by
Tagged with
45 votes
2 answers
9k views

How is the oracle in Grover's search algorithm implemented?

Grover's search algorithm provides a provable quadratic speed-up for unsorted database search. The algorithm is usually expressed by the following quantum circuit: In most representations, a crucial ...
glS's user avatar
  • 24.8k
43 votes
4 answers
7k views

Is there any general statement about what kinds of problems can be solved more efficiently using a quantum computer?

Is there a general statement about what kinds of problems can be solved more efficiently using quantum computers (quantum gate model only)? Do the problems for which an algorithm is known today have a ...
hiro protagonist's user avatar
43 votes
1 answer
2k views

Quantum machine learning after Ewin Tang

Recently, a series of research papers have been released (this, this and this, also this) that provide classical algorithms with the same runtime as quantum machine learning algorithms for the same ...
Alex's user avatar
  • 543
41 votes
3 answers
14k views

The algorithm of the new quantum factoring record 1,099,551,473,989

According to the New Scientist News, the Zapata team is able to factor 1,099,551,473,989 into its factors 1,048,589 and 1,048,601. According to the New Scientist: A quantum computing start-up company ...
kelalaka's user avatar
  • 709
38 votes
4 answers
14k views

Is there a layman's explanation for why Grover's algorithm works?

This blogpost by Scott Aaronson is a very useful and simple explanation of Shor's algorithm. I'm wondering if there is such an explanation for the second most famous quantum algorithm: Grover's ...
Discrete lizard's user avatar
36 votes
5 answers
4k views

Introductory material for quantum machine learning

In the past few days, I have been trying to collect material (mostly research papers) related to Quantum machine learning and its applications, for a summer project. Here are a few which I found ...
Sanchayan Dutta's user avatar
30 votes
3 answers
3k views

What could be the possible future applications for HHL algorithm?

Note on the vocabulary: the word "hamiltonian" is used in this question to speak about hermitian matrices. The HHL algorithm seems to be an active subject of research in the field of quantum ...
Adrien Suau's user avatar
  • 4,927
27 votes
2 answers
6k views

Circuit construction for Hamiltonian simulation

I would like to know how to design a quantum circuit that given a Hermitian matrix $\hat{H}$ and time $t$, maps $|\psi\rangle$ to $e^{i\hat{H}t} |\psi\rangle$. Thank you for your answer.
Tam'si Ley's user avatar
25 votes
5 answers
6k views

How would I implement the quantum oracle in Deutsch's algorithm?

I am trying to simulate Deutsch's algorithm (elementary case of Deutsch-Jozsa algorithm), and I am not entirely sure how I would go about implementing the quantum oracle necessary for the algorithm to ...
Jack Ceroni's user avatar
25 votes
1 answer
2k views

What are examples of Hamiltonian simulation problems that are BQP-complete?

Many papers assert that Hamiltonian simulation is BQP-complete (e.g., Hamiltonian simulation with nearly optimal dependence on all parameters and Hamiltonian Simulation by Qubitization). It is easy ...
groupsgroupsgroups's user avatar
24 votes
3 answers
3k views

Is quantum cryptography safer than classical cryptography?

Quantum computing allows us to encrypt information in a different way compared to what we use today, but quantum computers are much more powerful than today's computers. So if we manage to build ...
Archil Zhvania's user avatar
24 votes
2 answers
7k views

How does the Grover diffusion operator work and why is it optimal?

In this answer, Grover's algorithm is explained. The explanation indicates that the algorithm relies heavily on the Grover Diffusion Operator, but does not give details on the inner workings of this ...
Discrete lizard's user avatar
23 votes
4 answers
2k views

Why can the Discrete Fourier Transform be implemented efficiently as a quantum circuit?

It is a well known result that the Discrete Fourier Transform (DFT) of $N=2^n$ numbers has complexity $\mathcal O(n2^n)$ with the best known algorithm, while performing the Fourier transform of the ...
glS's user avatar
  • 24.8k
23 votes
1 answer
2k views

Is there a list of accessible open problems in quantum computing from a theoretical computer science perspective?

(Classical) theoretical computer science (TCS) has a number of outstanding open problems that can easily be instantiated in a manner that is accessible to a wider general public. For example, ...
Mark Spinelli's user avatar
22 votes
1 answer
3k views

An impossible quantum adder claimed by a journal article?

In Quantum adder of two states that are themselves superpositions, I asked: I have two states $|a\rangle = \frac{1}{\sqrt N}\sum_{i=0}^{N-1}|i\rangle|a_i\rangle$ and $|b\rangle = \frac{1}{\sqrt N}\...
Paulske's user avatar
  • 457
22 votes
2 answers
4k views

What does Google's claim of "Quantum Supremacy" mean for the question of BQP vs BPP vs NP?

Google recently announced that they have achieved "Quantum Supremacy": "that would be practically impossible for a classical machine." Does this mean that they have definitely proved that BQP ≠ BPP ?...
Alex Kinman's user avatar
21 votes
1 answer
383 views

Quantum Bitcoin Subdivision

Background Recently I was reading the article "Quantum Bitcoin: An Anonymous and Distributed Currency Secured by the No-Cloning Theorem of Quantum Mechanics" which demonstrates how a quantum bitcoin ...
Daniel Burkhart's user avatar
20 votes
1 answer
348 views

Level of advantage provided by annealing for traveling salesman

My understanding is that there seems to be some confidence that quantum annealing will provide a speedup for problems like the traveling salesman, due to the efficiency provided by, ex, quantum ...
auden's user avatar
  • 3,429
19 votes
2 answers
15k views

How do you implement the Toffoli gate using only single-qubit and CNOT gates?

I've been reading through "Quantum Computing: A Gentle Introduction", and I've been struggling with this particular problem. How would you create the circuit diagram, and what kind of reasoning would ...
Lucas Myers's user avatar
19 votes
3 answers
6k views

What is the current state of the art in quantum sorting algorithms?

As a result of an excellent answer to my question on quantum bogosort, I was wondering what is the current state of the art in quantum algorithms for sorting. To be precise, sorting is here defined ...
Discrete lizard's user avatar
19 votes
1 answer
2k views

Quantum phase estimation and HHL algorithm - knowledge of eigenvalues required?

The quantum phase estimation algorithm (QPE) computes an approximation of the eigenvalue associated to a given eigenvector of a quantum gate $U$. Formally, let $\left|\psi\right>$ be an ...
Adrien Suau's user avatar
  • 4,927
18 votes
3 answers
1k views

Can a quantum computer easily determine the mixing time of the Rubik's cube group?

Officials in Rubik's cube tournaments have used two different ways of scrambling a cube. Presently, they break a cube apart and reassemble the cubies in a random order $\pi\in G$ of the Rubik's cube ...
Mark Spinelli's user avatar
18 votes
4 answers
4k views

What applications does Grover's Search Algorithm have?

Grover's Search algorithm is usually talked about in terms of finding a marked entry in an unsorted database. This is a natural formalism that lets it be applied directly to searching for solutions to ...
DaftWullie's user avatar
17 votes
4 answers
4k views

Quantum circuits explain algorithms, why didn't classical circuits?

When explaining a quantum algorithm, many revert to 'circuit-speak' by drawing a diagram of how qubits split off into transformations and measurements, however, rarely if not never would someone ...
develarist's user avatar
17 votes
1 answer
4k views

How can we keep Schrödinger's cat alive?

We know, Schrödinger's cat inside the box is in the equal superposition state of both alive and dead. We can express its state as $$|\text{cat}_\phi\rangle= \frac{|\text{alive}\rangle+e^{i\phi}|\text{...
Syed Emad Uddin's user avatar
17 votes
1 answer
3k views

What is the Helstrom measurement?

I have been reading the paper Belief propagation decoding of quantum channels by passing quantum messages by Joseph Renes for decoding Classical-Quantum channels and I have crossed with the concept of ...
Josu Etxezarreta Martinez's user avatar
17 votes
1 answer
3k views

Is VQE a class of algorithms or a specific algorithm?

Is VQE a class of algorithms or a specific algorithm? For example, is QAOA a VQE or is VQE an algorithm distinct from QAOA that solves the same class of problems? If VQE is a specific algorithm, what ...
Malcolm Regan's user avatar
17 votes
1 answer
364 views

Are there results from quantum algorithms or complexity that lead to advances on the P vs NP problem?

On the surface, quantum algorithms have little to do with classical computing and P vs NP in particular: Solving problems from NP with quantum computers tells us nothing about the relations of these ...
Discrete lizard's user avatar
17 votes
1 answer
591 views

Are all quantum algorithms hidden subgroup algorithms?

I am reading the paper "Quantum Hidden Subgroup Algorithms: An Algorithmic Toolkit" by Samuel Lomonaco and Louis Kauffman from the book, "Mathematics of Quantum Computation and Quantum ...
user2521987's user avatar
16 votes
2 answers
3k views

How would a quantum computer be used to solve Partial Differential Equations?

Say you have a PDE you want to solve. What kind of quantum algorithms would you use to solve it? How do we input our problem on a quantum computer? What will be the output and in what form? I know ...
cnada's user avatar
  • 4,754
16 votes
1 answer
3k views

What is the difference between QAOA and Quantum Annealing?

Edward Farhi's paper on the Quantum Approximate Optimization Algorithm introduces a way for gate model quantum computers to solve combinatorial optimization algorithms. However, D-Wave style quantum ...
hopefully coherent's user avatar
15 votes
4 answers
5k views

General construction of $W_n$-state

Two of the most well known entangled states are the GHZ-state $|\psi\rangle = 1/\sqrt{2}\left( |0\rangle^{\otimes n} + |1\rangle^{\otimes n}\right)$ and the $W_n$-state, with $W_3 = 1/\sqrt{3}\left(|...
nippon's user avatar
  • 1,517
15 votes
5 answers
3k views

Will deep learning neural networks run on quantum computers?

Deep Learning (multiple layers of artificial neural networks used in supervised and unsupervised machine learning tasks) is an incredibly powerful tool for many of the most difficult machine learning ...
Bob Swain's user avatar
  • 253
15 votes
4 answers
2k views

How is the Grover-Algorithm applied to a database?

Question I want to use the Grover-Algorithm to search an unsorted database for an element $x$. Now the question arises, how do I initialize index and value of the database with the qubits? Example ...
alex's user avatar
  • 151
15 votes
2 answers
1k views

Does a study guide exist that starts from a "purely CS background" and advances towards "making a new quantum programming language"?

I am from a computer science background and I find it difficult to decide on the resources I should focus on while learning quantum computing, since there is so much to read/watch. My ultimate goal is ...
Kushajveer's user avatar
15 votes
3 answers
1k views

What is the quantum circuit equivalent of a (delayed choice) quantum eraser?

Quantum computers are efficiently able to simulate any other quantum system. Hence there must be some sort of equivalent of a (possibly simulated) quantum eraser setup. I would like to see such an ...
user avatar
15 votes
2 answers
865 views

Jones Polynomial

There are many fairly standard quantum algorithms that can all be understood within a very similar framework, from Deutsch's algorithm Simon's problem, Grover's search, Shor's algorithm and so on. ...
DaftWullie's user avatar
15 votes
4 answers
2k views

Are there any examples of anyone applying quantum algorithms to problems in computational biology?

As the title suggests, I'm searching for published examples of quantum algorithms being applied to problems in computational biology. Clearly the odds are high that practical examples don't exist (yet)...
Greenstick's user avatar
  • 1,076
15 votes
3 answers
736 views

How to permute (reshuffle) an n-bit input?

I am interested in a quantum algorithm that gets as input an n-bit sequence and that produces as output a reshuffled (permuted) version of this n-bit sequence. E.g. if the input is 0,0,1,1 (so n=4 in ...
JanVdA's user avatar
  • 1,148
14 votes
1 answer
6k views

How many logical qubits are needed to run Shor's algorithm efficiently on large integers ($n > 2^{1024}$)?

First, I know there are differences in logical qubits and physical qubits. It takes more physical qubits for each logical qubit due to quantum error. Wikipedia states that it takes quantum gates of ...
LeWoody's user avatar
  • 844
14 votes
2 answers
5k views

How and why does swap test works?

I am having some trouble understanding why a SWAP test would work. I meant I read that and understood the concepts as follows: If the two input states are equal, the output register always results in ...
Hamza's user avatar
  • 291
14 votes
4 answers
936 views

Is the common Computer Science usage of 'ignoring constants' useful when comparing classical computing with quantum computing?

Daniel Sank mentioned in a comment, responding to (my) opinion that the constant speed-up of $10^8$ on a problem admitting a polynomial time algorithm is meager, that Complexity theory is way too ...
Discrete lizard's user avatar
14 votes
2 answers
839 views

What kind of real-world problems (excluding cryptography) can be solved efficiently by a quantum algorithm?

This question is very similar as Is there any general statement about what kinds of problems can be solved more efficiently using a quantum computer? But the answers provided to that questions mainly ...
JanVdA's user avatar
  • 1,148
13 votes
6 answers
2k views

Resources for quantum algorithm basics

I have just started to learn about quantum computing, and I know a little bit about qubits. What is a resource where I can learn a basic quantum algorithm and the concepts behind how it works?
Vashi's user avatar
  • 177
13 votes
2 answers
478 views

Quantum Supremacy: How do we know that a better classical algorithm doesn't exist?

According to the Wikipedia (Which quotes this paper https://arxiv.org/abs/1203.5813 by Preskill) the definition of Quantum Supremacy is Quantum supremacy or quantum advantage is the potential ...
P. C. Spaniel's user avatar
13 votes
2 answers
2k views

What is the minimum integer value to make quantum factorization to be worthwhile?

Let us assume that we have quantum and classical computers such that, experimentally, each elementary logical operation of mathematical factorization is equally time-costing in classical and in ...
SalvaCardona's user avatar
13 votes
1 answer
2k views

How to implement a matrix exponential in a quantum circuit?

Maybe it is a naive question, but I cannot figure out how to actually exponentiate a matrix in a quantum circuit. Assuming to have a generic square matrix A, if I want to obtain its exponential, $e^{A}...
FSic's user avatar
  • 859
13 votes
2 answers
2k views

Quantum algorithm for linear systems of equations (HHL09): Step 1 - Confusion regarding the usage of phase estimation algorithm

I have been trying to get my head around the famous(?) paper Quantum algorithm for linear systems of equations (Harrow, Hassidim & Lloyd, 2009) (more popularly known as the HHL09 algorithm paper) ...
Sanchayan Dutta's user avatar
12 votes
3 answers
2k views

Quantum advantage with only Clifford gates (Gottesman Knill theorem)

Let's say I want to solve a computational task which input can be encoded in $n$ bits of information. The look for a quantum advantage is (usually) asking to find a quantum algorithm in which there ...
Marco Fellous-Asiani's user avatar
12 votes
3 answers
2k views

What is the actual power of Quantum Phase Estimation?

I have some perplexity concerning the concept of phase estimation: by definition, given a unitary operator $U$ and an eigenvector $|u\rangle$ with related eigenvalue $\text{exp}(2\pi i \phi)$, the ...
FSic's user avatar
  • 859

1
2 3 4 5
24