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
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
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
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
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
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
7 votes
1 answer
2k views

How is Grover's operator represented as a rotation matrix?

I have seen that it is possible to represent the Grover iterator as a rotation matrix $G$. My question is, how can you do that exactly? So we say that $|\psi\rangle$ is a superposition of the states ...
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
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
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
8 votes
3 answers
2k views

What exactly makes quantum computers faster than classical computers?

What feature of a quantum algorithm makes it better than its classical counterpart? Are quantum computers faster than classical ones in all respects?
Tobias Fritzn's user avatar
10 votes
1 answer
1k views

Preparing a quantum state from a classical probability distribution

Suppose I have a black-box unitary $U_p$ which is described as follows: given a finite probability distribution $p:\{1,\ldots,n\}\rightarrow \mathbb{R}_{\geq0}$, where $\sum_{x=1}^n p(x)=1$, the ...
Condo's user avatar
  • 2,008
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
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
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
10 votes
3 answers
1k views

Does the oracle in Grover's algorithm need to contain information about the entirety of the database?

Grover's algorithm is often described as a way to search a database in $O(\sqrt{N})$ time. For using it we need an oracle gate that represents some function $f$ such that $f^{-1}(1)$ is the answer. ...
Norrius's user avatar
  • 657
7 votes
1 answer
2k views

How to interpret a 4 qubit quantum circuit as a matrix?

This is part of Simon Algorithm (Initial state + some Oracle function) There is a post that explains how to interpret circuits (How to interpret a quantum circuit as a matrix?), but I'm not sure how ...
Felipe Rojo Amadeo'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
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
10 votes
3 answers
866 views

What is the simplest algorithm to demonstrate intuitively 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 ...
Steven Sagona's user avatar
10 votes
1 answer
498 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 ...
user820789's user avatar
  • 3,302
8 votes
4 answers
2k views

Grover algorithm for a database search: where is the quantum advantage?

I have been trying to understand what could be the advantage of using Grover algorithm for searching in an arbitrary unordered database D(key, value) with N values instead of a classical search. I ...
Foxhole's user avatar
  • 183
7 votes
2 answers
655 views

Significance of the term "diffusion" in Grover's diffusion operator

In the context of Grover's algorithm, the diffusion operator is defined as $U_s = 2|s\rangle \langle s| - I$ with $|s\rangle\equiv |+\rangle^{\otimes n}$. What is the significance of the term "...
Sanchayan Dutta's user avatar
5 votes
1 answer
488 views

How do you build a circuit to make an equal superposition of $n$ outcomes?

Suppose we start with $|00...0\rangle$. We want to build an equal superposition over $|0\rangle + ... + |n-1\rangle$. When $n=2^m$ for some $m$, I know I can do this using $H^{\otimes m}$. What is the ...
George Li'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
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
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
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
11 votes
2 answers
943 views

Grover's algorithm: what to input to Oracle?

I am confused about what to input to Oracle in Grover's algorithm. Don't we need to input what we are looking for and where to find what we are looking for to Oracle, in addition to the ...
Bick's user avatar
  • 842
11 votes
2 answers
586 views

Review paper on depth, qubits and $T$ gates number on Clifford+T decomposition for various "typical" algorithms

My question I am looking for some review paper, or a list of different papers providing concrete numbers about the depth, number of qubits and number of $T$ gates required on the Clifford+T basis for ...
Marco Fellous-Asiani's user avatar
8 votes
1 answer
1k views

Practical implementation of Hamiltonian Evolution

Following from this question, I tried to look at the cited article in order to simulate and solve that same problem... without success. Mainly, I still fail to understand how the authors managed to ...
FSic's user avatar
  • 859
6 votes
2 answers
504 views

Is it true that for a quantum algorithm to be efficient it must feature a highly entangled state at some point?

I'm wrapping my head around how and why quantum computers can provide advantage over classical. A basic and naive argument is that the dimension of the Hilbert space of $n$ qubits grows as $2^n$. ...
Nikita Nemkov's user avatar
5 votes
2 answers
1k views

Quantum computing in finance - list of articles

I am trying to find application of a quantum computing in finance. So far I found these papers: Quantum computing for finance: Overview and prospects Quantum computational finance: quantum algorithm ...
Martin Vesely's user avatar
5 votes
1 answer
754 views

How to compute the error threshold for the $9$-qubit Shor code?

I was trying to calculate the threshold of $9$-qubit Shor's code. The error channel is $$E=(1-p)I+p/3X+p/3Y+p/3Z.$$ But I got the threshold is equal to 1. How can I get the right threshold (I believe ...
QuantumDots's user avatar
4 votes
2 answers
608 views

In Grover's Algorithm, does the exact solution need to be given to the oracle?

From my understanding, the oracle function in Grover's algorithm is used as a way to check for the desired outcome. I have looked at this example which implements the Exactly-1 3-SAT problem and the ...
desirooo's user avatar
  • 117
4 votes
1 answer
225 views

Quantum XOR Cipher Construction

After getting help here with XNOR, RCA & XOR linked lists, I am now curious about quantum XOR ciphers (Google returns "no results"). In cryptography, the simple XOR cipher is a type of ...
user820789's user avatar
  • 3,302
2 votes
1 answer
3k views

Grover algorithm for more than one element

I am currently working on the Grover algorithm again. In many lectures and documents, as well as books, I noticed that there is always talk of looking for a single element of $N$ elements. Now I read ...
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
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
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
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
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
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
11 votes
1 answer
1k 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 ...
Sanchayan Dutta's user avatar
10 votes
2 answers
3k 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 ...
Aman's user avatar
  • 483
8 votes
1 answer
1k views

Efficiently performing controlled rotations in HHL

This question builds off of this question. In the HHL algorithm, how do you efficiently do the $\tilde{\lambda}_k$-controlled rotations on the ancilla qubit? It seems to me that since you don't know ...
Paradox's user avatar
  • 337
8 votes
1 answer
868 views

Quantum algorithm for linear systems of equations (HHL09): Step 1 - Number of qubits needed

This is a continuation of Quantum algorithm for linear systems of equations (HHL09): Step 1 - Confusion regarding the usage of phase estimation algorithm Questions (contd.): Part 2: I'm not exactly ...
Sanchayan Dutta's user avatar
8 votes
1 answer
2k views

How exactly does Simon's algorithm solve the Simon's problem?

Problem Statement: We are given a $2-1$ function $f:\{0,1\}^{n}\to\{0,1\}^{n}$ such that: there is a secret string $s\in\{0,1\}^{n}$ such that: $f(x)=f(x\oplus s)$. Challenge: find $s$. Simon's ...
Sanchayan Dutta's user avatar
6 votes
1 answer
1k views

Why is this implementation of the order finding algorithm not working?

I asked a question about this earlier, but I am still coming across problems in my algorithm implementation. I am trying to implement the order finding algorithm on Cirq finding the minimal positive $...
Jack Ceroni's user avatar
5 votes
1 answer
2k views

Quantum Circuit To Compute Any Inner Product

I'm currently reading the paper Classification with Quantum Neural Networks on Near Term Processors It shows a method to determine the following quantity: Where U is a unitary operator acting on $|z,...
Rehaan Ahmad's user avatar
5 votes
1 answer
1k views

What to do when the amount of solutions is not known before applying Grovers Algorithm?

When running Grovers Algorithm one has to know how many solutions there are right? When the number of solutions are not known is then what do you do then?
Hannah's user avatar
  • 529

1
2 3 4 5