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
5 votes
1 answer
630 views

How to compare a quantum algorithm with its classical version? [closed]

The Quantum Algorithm Zoo includes a host of algorithms for which Quantum Computing offers speedups (exponential, polynomial, etc). However, those speedups are based on asymptotic computational ...
Aritra's user avatar
  • 313
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
8 votes
1 answer
298 views

Does quantum computing provide any speedup in evaluation of transcendental functions?

With the integer factorisation problem, Shor's algorithm is known to provide a substantial (exponential?) speedup compared to classical algorithms. Are there similar results regarding more basic maths,...
Norrius's user avatar
  • 657
9 votes
1 answer
152 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: ...
jman's user avatar
  • 443
2 votes
0 answers
55 views

Are there numerical differences between classical and quantum solutions of problems such as the Born-Jordan quantization? [closed]

Consider an implementation of the Born-Jordan quantization or an arbitrary Cohen class time-frequency analysis algorithm. Are there any numerical differences between classical and quantum solutions? ...
noumenal's user avatar
  • 121
11 votes
2 answers
1k 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 ...
Didix's user avatar
  • 785
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
9 votes
2 answers
708 views

How do quantum computers prevent "quantum noise"?

On the Wikipedia page for Shor's algorithm, it is stated that Shor's algorithm is not currently feasible to use to factor RSA-sized numbers, because a quantum computer has not been built with enough ...
ack's user avatar
  • 193
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
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
6 votes
2 answers
579 views

Can classical algorithms be improved by using quantum simulation as an intermediary step?

I'm wondering whether even if we cannot create a fast quantum computer, simulating quantum algorithms can be a reasonable method for classical algorithms. In particular, I'd like to see any results ...
Discrete lizard'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
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
11 votes
2 answers
11k 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 ...
Discrete lizard's user avatar
8 votes
1 answer
240 views

New algorithm for faster QC simulation by IBM

This new algorithm for QC calculation was introduced recently (2017 4Q) by IBM/ Pednault et al. to great fanfare. The paper seems more couched in the language of physics. Are there any basic ...
vzn's user avatar
  • 255
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
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
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

1
20 21 22 23
24