# Questions tagged [algorithm]

For questions on quantum algorithms. That is, algorithms which in theory can be executed by quantum computers, usually the computers providing 'universal' quantum computation.

70 questions
1k 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 ...
292 views

### Time Entangled Quantum Blockchain

This answer cites a paper[$\dagger$] which purposes a quantum blockchain using entanglement in time. "The weakness is that the research only presents a conceptual design." - QComp2018 How could a ...
384 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 ...
416 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 ...
211 views

682 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) ...
363 views

### Simplest algorithm for intuitively demonstrating quantum speed-up?

What's the simplest algorithm (like Deutsch's algorithm and Grover's Algorithm) for intuitively demonstrating quantum speed-up? And can this algorithm be explained intuitively? Ideally this would be ...
1k 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 ...
525 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 ...
805 views

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

I am trying to simulate Deutsch's algorithm (elementary case of Deutsch-Josza algorithm), and I am not entirely sure how I would go about implementing the quantum oracle necessary for the algorithm to ...
638 views

### How can I calculate the inner product of two quantum registers of different sizes?

I found an algorithm that can compute the distance of two quantum states. It is based on a subroutine known as swap test (a fidelity estimator or inner product of two state, btw I don't understand ...
301 views

### How to benchmark a quantum computer?

Using a simple puzzle game to benchmark quantum computers is the most clever approach I have seen so far. The author of the aforementioned article, James, makes a nice analogy to buying a laptop ("...
106 views

### Expected repetitions of the quantum part of Shor's algorithm

Shor's algorithm to factor a number $N$ goes as follows: Pick a random value $b \in (0, N)$. Use a specific quantum computation to a sample a value $v$ that should be close to $2^{m} k/p$ where $m$ ...
192 views

### How to create a quantum algorithm that produces 2 n-bit sequences with equal number of 1-bits?

I am interested in a quantum algorithm that has the following characteristics: output = 2n bits OR 2 sets of n bits (e.g. 2 x 3 bits) the number of 1-bits in the first set of n-bits must be equal to ...
336 views

### HHL algorithm — controlled-by-eigenvalues rotations

All the references in this question refer to Quantum algorithm for solving linear systems of equations (Harrow, Hassidim & Lloyd, 2009). The question I have is about the step where they apply ...
89 views

I recently found out about shadowgraphy and was wondering if a technique like this could be used to: Visually show entanglement Suffice as a measure (e.g. continous partial trace) Most useful ...
1k 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 ...
2k 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 ...
577 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?
322 views

### Hamiltonian simulation is 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 ...
303 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 ...
274 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 ...
536 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 ...
133 views

### Advantage of simulating sparse Hamiltonians

In @DaftWullie's answer to this question he showed how to represent in terms of quantum gates the matrix used as example in this article. However, I believe it to be unlikely to have such well ...
210 views

### How is Grover's algorithm used to estimate the mean and median of a set of numbers?

On the Wikipedia page for Grover's algorithm, it is mentioned that: "Grover's algorithm can also be used for estimating the mean and median of a set of numbers" So far I only knew how it can be ...