Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

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.

351 questions
Filter by
Sorted by
Tagged with
2k 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

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 ...
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 ...
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 ...
2k 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 ...
276 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 ...
657 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 ...
216 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 ...
365 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 ...
532 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 ...
389 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 ...
998 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 ...
163 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 ...
2k 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 ...
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 ...
981 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 ...
391 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 ...
796 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 ...
451 views

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(|... 3answers 647 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 ... 2answers 845 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 ... 2answers 325 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 ... 2answers 571 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)... 2answers 4k 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 ... 2answers 413 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 ... 2answers 235 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 ... 1answer 277 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 ... 1answer 317 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 ... 2answers 874 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) ... 2answers 261 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. ... 1answer 165 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 ... 0answers 174 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 ... 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)... 5answers 1k 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 ... 2answers 483 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 ... 4answers 730 views Quantum Computing Journals Can anyone give me a list of different research journals that has quantum computing articles that I can use. 3answers 228 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? 1answer 283 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 ... 1answer 97 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: ... 3answers 217 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 ... 1answer 522 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 ... 1answer 197 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 ... 1answer 239 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 ... 2answers 316 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 ... 4answers 371 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 ... 2answers 650 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 ... 2answers 361 views Quantum algorithm for linear systems of equations (HHL09): Step 2 - What is$|\Psi_0\rangle\$?

This is a sequel to Quantum algorithm for linear systems of equations (HHL09): Step 1 - Confusion regarding the usage of phase estimation algorithm and Quantum algorithm for linear systems of ...
3k views

What can we learn from 'quantum bogosort'?

Recently, I've read about 'quantum bogosort' on some wiki. The basic idea is, that like bogosort, we just shuffle our array and hope it gets sorted 'by accident' and retry on failure. The ...