Questions tagged [complexity-theory]
For questions regarding complexity analysis of quantum algorithms and comparisons with complexities of classical algorithms.
37
questions
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
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 ...
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
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
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
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
6
votes
3
answers
1k
views
Do there exist problems known to be computationally intractable for quantum computer, but tractable for classical computer?
Or alternatively phrased, is it believed that the complexity class P is a complete subset of BQP?
Consider the following diagram à la MIT OpenCourseWare, which seems to explicitly state as much.
- 195
4
votes
1
answer
1k
views
Simpler implementation of the Toffoli gate on IBM Q for special circumstances
On current quantum hardware, a depth of circuit is constrained because of noise. In some cases, results are totally decoherent and as a result meaningless. This is especially true when Toffoli gates ...
- 13.1k
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
8
votes
1
answer
777
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
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
6
votes
1
answer
195
views
What classical public key cryptography protocols exist for which hacking is QMA complete or QMA hard?
Such a public key cryptosystem would be "quantum safe" in the sense that quantum computers cannot efficiently solve QMA hard problems.
- 12.8k
5
votes
1
answer
419
views
Showing that Matrix Inversion is BQP-complete - HHL Algorithm
I am trying to understand an argument that Matrix Inversion is BQP-complete for certain conditions on the matrix. This is explained here on page 39 (this paper is a primer to the HHL algorithm and ...
- 505
5
votes
2
answers
1k
views
Can quantum computers be used to solve P = NP
The P versus NP problem is a major unsolved problem in computer science. It asks whether every problem whose solution can be quickly verified can also be solved quickly. It is one of the seven ...
- 159
4
votes
2
answers
154
views
How to implement exponentiation of a gate without breaking complexity?
In the application of QFT for quantum phase estimation (QPE) of a unitary $\mathbf{U}$, one has to perform successive controlled operations using powers of $\mathbf{U}$. In order not to break the ...
- 4,603
0
votes
0
answers
45
views
Question about the Grover-Sysoev algorithm [duplicate]
We consider a quantum circuit that takes as input two vectors $\vert x \rangle$ and $\vert y \rangle$. The output of this quantum circuit must contain the reflected vector of $\vert y \rangle$ ...
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
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 $$...
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
10
votes
2
answers
699
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
368
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
2
answers
565
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
9
votes
3
answers
523
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
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 ...
8
votes
1
answer
399
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
7
votes
2
answers
352
views
Why is depth complexity relevant?
Since gate complexity correspond to the number of gate for a given quantum circuit, it seems that depth complexity bring no more information about quantum complexity than gate complexity. So does gate ...
- 95
7
votes
1
answer
338
views
Are almost-Clifford circuits almost easy to simulate?
Circuits consisting entirely of Clifford operations in $\{X, Y, Z, H, S, \text{CNOT} \}$ are "easy" to simulate classically since there is a method that can fully compute such circuits over $...
- 5,715
7
votes
1
answer
538
views
Query regarding BQP belonging to PP
I found the following proof of BQP belonging to PP (the original document is here). There is a part of the proof that I have trouble understanding. First, the structure is given below.
We try to ...
- 1,119
7
votes
1
answer
255
views
Does the GLOA have any advantage over the Solovay-Kitaev algorithm?
The Solvay Kitaev algorithm was discovered long before the Group Leaders Optimization algorithm and it has some nice theoretical properties. As far as I understand, both have exactly the same goals: ...
- 16.9k
6
votes
1
answer
370
views
Quantum Algorithm SAT structure
"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 ...
- 785
6
votes
1
answer
228
views
What is the relationship between the size of the Hilbert space for boson sampling and the complexity of classical simulating it?
My intuition is that the fastest classical algorithm for simulating some kind of noiseless quantum sampling process should scale roughly with the dimension of the Hilbert space: you would need to ...
- 2,347
6
votes
1
answer
396
views
Is quantum computer equivalent to Turing machine with matrix multiplication oracle?
Since quantum computer with $n$ qubits is described by a $2^{n}\times2^{n}$ unitary matrix is it equivalent to an oracle that can do multiplication of large matrix and return $n$ numbers computed ...
- 161
6
votes
1
answer
428
views
What is the complexity of hidden subgroup problems?
It is often stated that some of the "hidden subgroup problems" can be efficiently solved by quantum computers if the group is abelian, while no efficient algorithm is known for the non-...
- 463
5
votes
6
answers
486
views
Good metaphors for n-level quantum systems
It seems that a coin flip game is a decent metaphor for a 2-level system. Until 1 of the 2 players picks heads or tails, even if the coin has already been flipped, the win/loss wave form has not yet ...
- 3,272
4
votes
2
answers
226
views
How exactly is solving the random circuit sampling problem a computation in the Church-Turing thesis sense?
Note: This has been cross-posted to CS Theory SE.
If we assume $\mathsf{BQP} \neq \mathsf{BPP}$, then we can say with reasonable certainty that Google's random sampling experiment falsifies the ...
- 16.9k
1
vote
1
answer
37
views
How precise are BQP measurements?
Let's say I am given a Hamiltonian $H$, whose ground state is efficiently preparable. We know that $||H|| \leq 1$. Let that ground state be $|\psi_{0}\rangle$, with energy $E_{0}$. We also know that ...
- 1,119