Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

24
votes
2answers
986 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 ...
23
votes
3answers
886 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 ...
21
votes
4answers
2k 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 ...
18
votes
2answers
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 ...
17
votes
1answer
135 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 ...
17
votes
1answer
243 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 ...
16
votes
4answers
472 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 ...
16
votes
2answers
1k 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 ...
14
votes
4answers
485 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 ...
14
votes
1answer
285 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 ...
14
votes
1answer
146 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 ...
13
votes
2answers
717 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 ...
13
votes
3answers
280 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 ...
13
votes
2answers
441 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 ...
12
votes
2answers
571 views

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

As a result from an excellent answer to my question on Quantum bogo sort, I was wondering what is the current state of the art in quantum algorithms for sorting. To be precise, sorting is here ...
12
votes
2answers
474 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 ...
12
votes
2answers
1k 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 ...
12
votes
0answers
177 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 ...
11
votes
4answers
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 ...
11
votes
2answers
301 views

Rigorous security proof for Wiesner's quantum money

In his celebrated paper "Conjugate Coding" (written around 1970), Stephen Wiesner proposed a scheme for quantum money that is unconditionally impossible to counterfeit, assuming that the issuing bank ...
11
votes
2answers
225 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 ...
11
votes
1answer
260 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 ...
11
votes
2answers
310 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)...
11
votes
2answers
222 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. ...
11
votes
1answer
142 views

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

As the name already suggests, this question is a follow-up of this other. I was delighted with the quality of the answers, but I felt it would be immensely interesting if insights regarding ...
11
votes
0answers
142 views

Quantum walk with binary tree

I’m trying to grok quantum walks, and would like to create an example that walks a perfect binary tree to find the one and only marked leaf node. Is this possible? If so, suppose the depth of the tree ...
10
votes
2answers
2k views

Classical Memory enough to store states up to 40 qubits quantum system?

As a part of a discussion with my 'classical' friend, he insisted that making a a state machine for calculating the outcome of quantum computer is possible; so, simply calculate the outcomes of (known)...
10
votes
4answers
495 views

Quantum Computing Journals

Can anyone give me a list of different research journals that has quantum computing articles that I can use.
10
votes
1answer
84 views

Is there any source which tabulates quantum computing algorithms for simulating physical systems?

I was wondering if there is a source (online or review article) which tabulates recent algorithms, and their complexities, used in simulating various physical systems. Something along the lines of: ...
10
votes
2answers
163 views

Does Shor's algorithm end the search for factoring algorithms in the quantum world of computation?

In other words, will factoring research remain solely in the classical world or are there interesting research on-going in the quantum world related to factoring?
10
votes
2answers
214 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 ...
10
votes
1answer
182 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 ...
10
votes
1answer
119 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 ...
10
votes
3answers
201 views

Can one interrogate black boxes for quantum coherence?

This question is based on a scenario that is partly hypothetical and partly based on the experimental features of molecule-based quantum devices, which often present a quantum evolution and have some ...
10
votes
1answer
325 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 ...
9
votes
2answers
3k views

How many operations can a quantum computer perform per second?

I want to know what time complexity is considered efficient/inefficient for quantum computers. For this, I need to know how many operations a quantum computer can perform per second. Can anyone tell ...
9
votes
4answers
300 views

Can we use quantum parallelism to calculate many functions at once?

It is well-known that by utilizing quantum parallelism we can calculate a function $f(x)$ for many different values of $x$ simultaneously. However, some clever manipulations is needed to extract the ...
9
votes
4answers
615 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 ...
9
votes
2answers
399 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 ...
9
votes
2answers
632 views

Is BQP only about time? Is this meaningful?

The complexity class BQP (bounded-error quantum polynomial time) seems to be defined only considering the time factor. Is this always meaningful? Do algorithms exist where computational time scales ...
9
votes
3answers
178 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(|...
9
votes
1answer
197 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 ...
9
votes
3answers
414 views

A sample quantum algorithm, useful for demonstrating languages

I'm looking for a quantum algorithm which I can use to demonstrate the syntax of different quantum-languages. My question is similar to this, however, for me, "good" means: What it does could be ...
9
votes
2answers
616 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) ...
9
votes
1answer
525 views

Is it possible to speed up the generation of the weighting matrix using a quantum algorithm?

In this[1] paper, on page 2, they mention that they are generating the weighting matrix as follows: $$W = \frac{1}{Md}[\sum_{m=1}^{m=M} \mathbf{x}^{(m)}\left(\mathbf{x}^{(m)}\right)^{T}] - \frac{\Bbb ...
9
votes
1answer
170 views

Why is an oracle qubit necessary in Grover's algorithm?

I am a bit confused about the necessity of an oracle qubit in Grover's algorithm. My question is, does it depend on how you implement your oracle whether you need an oracle qubit or not? Or, it there ...
9
votes
1answer
282 views

Quantum Algorithm for God's Number

God's number is the worst case of God's algorithm which is a notion originating in discussions of ways to solve the Rubik's Cube puzzle, but which can also be applied to other combinatorial puzzles ...
9
votes
1answer
279 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 ...
9
votes
2answers
212 views

Composing multiple quantum circuits in single quantum program in QISKit

I was wondering if there is a way to compose a program with multiple quantum circuits without having the register reinitialized at $0$ for each circuit. Specifically, I would like run a second ...
9
votes
0answers
131 views

Quantum Walk: Why the need of adding “tail” nodes to the root?

As stated in the question, I have found in several papers (e.g. 1, 2) that in order to perform a quantum walk on a given tree it is necessary to add some nodes to the root $r$, say $r^{'}$ and $r^{"}$....