Questions tagged [complexity-theory]
For questions regarding complexity analysis of quantum algorithms and comparisons with complexities of classical algorithms.
256
questions
46
votes
4
answers
3k
views
Is it possible for an encryption method to exist which is impossible to crack, even using quantum computers?
Quantum computers are known to be able to crack in polynomial time a broad range of cryptographic algorithms which were previously thought to be solvable only by resources increasing exponentially ...
- 887
41
votes
2
answers
7k
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♦
- 21.7k
37
votes
4
answers
6k
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 ...
- 473
37
votes
4
answers
13k
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 ...
- 3,074
34
votes
5
answers
2k
views
Are there problems in which quantum computers are known to provide an exponential advantage?
It is generally believed and claimed that quantum computers can outperform classical devices in at least some tasks.
One of the most commonly cited examples of a problem in which quantum computers ...
glS♦
- 21.7k
32
votes
2
answers
2k
views
Why is a quantum computer in some ways more powerful than a nondeterministic Turing machine?
The standard popular-news account of quantum computing is that a quantum computer (QC) would work by splitting into exponentially many noninteracting parallel copies of itself in different universes ...
- 2,357
26
votes
2
answers
5k
views
What is postselection in quantum computing?
A quantum computer can efficiently solve problems lying in the complexity class BQP. I have seen a claim the one can (potentially, because we don't know whether BQP is a proper subset or equal to PP) ...
- 1,274
22
votes
1
answer
1k
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 ...
21
votes
2
answers
4k
views
What does Google's claim of "Quantum Supremacy" mean for the question of BQP vs BPP vs NP?
Google recently announced that they have achieved "Quantum Supremacy": "that would be practically impossible for a classical machine."
Does this mean that they have definitely proved that BQP ≠ BPP ?...
- 655
21
votes
1
answer
2k
views
Is there a list of accessible open problems in quantum computing from a theoretical computer science perspective?
(Classical) theoretical computer science (TCS) has a number of outstanding open problems that can easily be instantiated in a manner that is accessible to a wider general public.
For example, ...
- 9,346
19
votes
3
answers
5k
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 ...
- 3,074
17
votes
1
answer
333
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 ...
- 3,074
15
votes
1
answer
3k
views
Why are non-Clifford gates more complex than Clifford gates?
There are two groups of quantum gates - Clifford gates and non-Clifford gates.
Representatives of Clifford gates are Pauli matrices $I$, $X$, $Y$ and $Z$, Hadamard gate $H$, $S$ gate and $CNOT$ gate. ...
- 13.1k
13
votes
3
answers
2k
views
Are spin-glass problems NP (-complete)?
It is well known that finding ground states for spin-glass systems (Ising, XY...) is NP-hard (at least as hard as the hardest NP-problems) so that they can be efficiently used to solve other NP ...
- 233
13
votes
4
answers
2k
views
Grover's Algorithm and its relation to complexity classes?
I am getting confused about Grover's algorithm and it's connection to complexity classes.
The Grover's algorithm finds and element $k$ in a database of $N=2^n$ (such that $f(k)=1$) of elements with $$...
13
votes
0
answers
418
views
Relation between quantum entanglement and quantum state complexity
Both quantum entanglement and quantum state complexity are important in quantum information processing. They are usually highly correlated, i.e., roughly a state with a higher entanglement corresponds ...
- 323
12
votes
3
answers
2k
views
What is the actual power of Quantum Phase Estimation?
I have some perplexity concerning the concept of phase estimation: by definition, given a unitary operator $U$ and an eigenvector $|u\rangle$ with related eigenvalue $\text{exp}(2\pi i \phi)$, the ...
- 839
12
votes
1
answer
447
views
Separating NP from BQP relative to an oracle
I was looking at this lecture note where the author gives an oracle separation between $\mathsf{BQP}$ and $\mathsf{NP}$. He hints at how "standard diagonalisation techniques can be used to make this ...
- 1,119
11
votes
2
answers
6k
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 ...
- 2,147
11
votes
2
answers
10k
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 ...
- 3,074
11
votes
1
answer
824
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 ...
- 3,272
11
votes
1
answer
314
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 ...
- 744
11
votes
1
answer
314
views
Quantum algorithms for Prolog or automated theorem proving?
Are there quantum algorithms for Prolog (SLD resolution - unification and depth-first-search) or for automated theorem proving in general (negation, resolution, and SAT)?
Usually automated theorem ...
- 403
11
votes
1
answer
265
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^{"}$....
- 839
11
votes
0
answers
228
views
Is HHL still BQP-complete when the matrix entries are only in {0,1}?
I'm studying BQP-completeness proofs of a number of interesting problems of Janzing and Wocjan, and Wocjan and Zhang. Janzing and Wocjan show that estimating entries of matrix powers $(A^m)_{ij}$ with ...
- 9,346
10
votes
3
answers
1k
views
Quantum advantage with only Clifford gates (Gottesman Knill theorem)
Let's say I want to solve a computational task which input can be encoded in $n$ bits of information.
The look for a quantum advantage is (usually) asking to find a quantum algorithm in which there ...
- 1,142
10
votes
2
answers
783
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 ...
- 885
10
votes
2
answers
567
views
Good introductory material on quantum computational complexity classes
I wish to learn more about computational complexity classes in the context of quantum computing.
The medium is not so important; it could be a book, online lecture notes or the like. What matters ...
- 1,865
10
votes
1
answer
294
views
Are there any encryption suites which can be cracked by classical computers but not quantum computers?
Are there any encryption suites that can be cracked by usual computers or super computers, but not quantum computers?
If that's possible, what assumptions will it depend on? (Factorizing big numbers, ...
- 213
10
votes
2
answers
700
views
What is the complexity of determining if a state is entangled?
I have been looking around for an answer to this question but can't really come up with anything. Given some oracle, $U$, that maps $| 0 \rangle$ to $| \psi \rangle$, is there some algorithm that ...
- 373
10
votes
2
answers
369
views
Consequences of SAT ∈ BQP
"Quantum magic won't be enough" (Bennett et al. 1997)
If you throw away the problem structure, and just consider the space of $2^n$ possible solutions, then even a quantum computer needs about $\...
- 785
10
votes
0
answers
298
views
What is stopping FACTORING from being BQP-complete?
Classical complexity theory makes much of the study of so-called intermediate problems - that is, problems that are in $\mathsf{NP}$ but are nonetheless not known to be in $\mathsf{P}$ and further not ...
- 9,346
10
votes
0
answers
90
views
Strong vs weak simulations and the polynomial hierarchy collapse
(Edited to make the argument and the question more precise)
An argument for quantum computational "supremacy" (specifically in Bremner et al. and the Google paper) assumes that there exists a ...
- 201
9
votes
6
answers
2k
views
Resources to study quantum algorithms and quantum complexity
I have a computer science background, and I'm interested in studying 'quantum algorithms' and anything that is related like 'quantum complexity'.
I would like to have all important resources that is ...
- 337
9
votes
2
answers
609
views
Why doesn't Deutsch-Jozsa Algorithm show that P ≠ BQP?
To my understanding, Deutsch-Jozsa algorithm solves a specific problem in constant time, using a fixed circuit depth, compared to a classical deterministic algorithm, which would require time ...
- 612
9
votes
1
answer
1k
views
Can a quantum computer tell whether a program is Turing complete?
I am very new to quantum computing and would like to know if a quantum computer can decide whether a given program is Turing complete.
- 101
9
votes
2
answers
3k
views
Why is quantum Fourier transform required in Shor's algorithm?
I’m currently studying the Shor’s algorithm and am confused about the matter of complexity. From what I have read, the Shor’s algorithm reduces the factorization problem to the order-finding problem ...
9
votes
3
answers
527
views
What is the computational complexity of quantum annealing?
Quantum annealing can be thought of as a black box solver that can find approximate solutions to hard optimization problems. For example, D-Wave quantum annealers can approximately solve quadratic ...
9
votes
1
answer
150
views
Can the analysis or design of quantum algorithms benefit from parameterised algorithmics?
In the last decades, the field of parameterised algorithms, with fixed parameter tractibility (FPT) as its main tool has been provided new methods to analyse old algorithms and design techniques for ...
- 3,074
9
votes
2
answers
299
views
A rigorous definition for an exponential quantum advantage
Let's assume that we have an algorithmic problem to solve. This problem takes an integer $n$ as input to describe it and provides as output a bit string providing the answer we are expecting.
For some ...
- 1,142
9
votes
1
answer
308
views
Quantum algorithms for problems outside NP
What is known about quatum algorithms for problems outside NP (eg NEXP-complete problems), both theoretically like upper & lower speedup bounds and various (im)possibility results, as well as ...
- 331
9
votes
1
answer
617
views
What is recursive Fourier sampling and how does it prove separations between BQP and NP in the black-box model?
Context:
I was going through John Watrous' lecture Quantum Complexity Theory (Part 1) - CSSQI 2012. Around 48 minutes into the lecture, he presents the following:
No relationship is known between $\...
- 16.9k
8
votes
1
answer
401
views
Consequences of $MIP^\ast=RE$ Regarding Quantum Algorithms
The (pending-peer review) proof of $MIP^\ast=RE$ in this pre-print has been hailed as a significant breakthrough. The significance of this result is addressed by Henry Yuen (one of the authors) in ...
- 3,302
8
votes
2
answers
584
views
Why does QAOA achieve quantum supremacy in an algorithmic sense?
In the paper Quantum Supremacy through the Quantum Approximate Optimization Algorithm the authors claim (last sentence of page 15):
"If [...] the QAOA outperforms all known classical algorithms ...
- 415
8
votes
2
answers
6k
views
Will quantum computers be able to solve the game of chess?
Will it be possible to use quantum computing to one day solve the game of chess? If so, any estimate as to how many qubits it would require?
The game of checkers has already been solved through back ...
- 181
8
votes
1
answer
780
views
Classical algorithm with complexity similar to Shor's discovered: Are there more efficient quantum algorithms than Shor's?
In the article Fast Factoring Integers by SVP Algorithms the author claims that he discovered classical algorithm for factoring integers in polynomial time. The Quantum Report mentioned here that it ...
- 13.1k
8
votes
1
answer
174
views
What are the thermodynamic limits of Shor's algorithm
The asymptotic time complexity of Grover's algorithm is the square root of the time of a brute force algorithm. However, according to Perlner and Liu, the thermodynamic behavior (theoretical minimum ...
- 183
8
votes
1
answer
1k
views
What is the complexity of the quantum phase estimation in Grover's algorithm?
Suppose we are using GA (Grover's algorithm) such that we are given it has 2 or more solutions. The search space is of size $N$. We all know Grover's algorithm has, at worst, a time complexity ...
- 306
8
votes
0
answers
147
views
Better "In-Place" Amplification of QMA
$\def\braket#1#2{\langle#1|#2\rangle}\def\bra#1{\langle#1|}\def\ket#1{|#1\rangle}$
In MW05 the authors demonstrate so-called "in-place" amplitude amplification for QMA, exhibiting a method for Arthur ...
- 321
8
votes
0
answers
381
views
Is there a BQP algorithm for each level of the polynomial hierarchy PH?
This question is inspired by thinking about quantum computing power with respect to games, such as chess/checkers/other toy games. Games fit naturally into the polynomial hierarchy $\mathrm{PH}$; I'm ...
- 9,346