Questions tagged [complexity-theory]
For questions regarding complexity analysis of quantum algorithms and comparisons with complexities of classical algorithms.
256
questions
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
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
3
votes
1
answer
206
views
Grover's algorithm and Battleship solution
I have read that quantum computers are not known to be able to solve NP-complete problems in polynomial time. However, if you consider a game of Battleship with grid size $X, Y$ and represent this by ...
- 439
1
vote
1
answer
840
views
Clarification needed for the N&C proof that BQP ⊆ PSPACE
In QCQI by Chuang and Nielsen (page 201), they prove that $\mathsf{BQP} \subseteq \mathsf{PSPACE}$. I can't understand what they say.
They write "Supposing the quantum circuit starts in the state $...
- 841
6
votes
1
answer
397
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
2
votes
1
answer
391
views
Is there a polynomial quantum algorithm for graph coloring?
Is there a polynomial time and polynomial space quantum algorithm for finding a 4 colouring of any loopless planar graph?
- 306
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
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
3
votes
0
answers
131
views
Does strong error reduction for PostQMA exist?
$\mathsf{PostQMA}$ can be defined as the following (see Morimae-Nishimura and Usher-Hoban-Browne):
A promise problem $\mathcal{L}=(\mathcal{L_{yes},L_{no}})$ is in $\mathsf{PostQMA(c,s)}$ if there ...
- 488
5
votes
2
answers
332
views
Quantum proof for the group non-membership problem
Group non-membership problem:
Input: Group elements $g_1,..., g_k$ and $h$ of $G$.
Yes: $h \not\in \langle g_1, ..., g_k\rangle$
No: $h\in \langle g_1, ..., g_k\rangle$
Notation: $\langle g_1, ..., ...
- 16.9k
6
votes
1
answer
197
views
How to construct a quantum circuit (QIP system) for the graph non-isomorphism problem?
I'm having some trouble understanding quantum interactive proof systems (QIP systems) and the related circuit constructions. Interactive proof systems model these type of situations:
Interactive ...
- 16.9k
5
votes
1
answer
438
views
Query lower bound for Majority function using the quantum adversary method
Using the quantum adversary lower bound technique, how can one calculate lower bound for Majority function $f:\{0,1\}^n \to \{0,1\}$ such that $f(x)=0$ if $|x|\leq n/2$ else $f(x)=1$, $|x|$ is the ...
- 51
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
4
votes
1
answer
1k
views
Intuitive Proof: BQP ⊆ PP
Promise Problem : It is a pair
$$\mathcal{A}=\{\mathcal{A}_{\text{yes}},\mathcal{A}_{\text{no}}\}$$
where $\mathcal{A}_{\text{yes}}$ and $\mathcal{A}_{\text{no}}$ are disjoint sets of inputs (yes ...
- 16.9k
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
6
votes
3
answers
1k
views
Classical complexity for Simon's problem
Simon's problem is that you are given a function $f : \{0,1\}^n \to \{0,1\}^n$ such that $f(x)=f(y)$ if and only if $x \bigoplus y$ is either $0^n$ or some unknown $s$. The problem is to find $s$. If $...
- 583
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
5
votes
1
answer
92
views
What's the notion of input size for Quantum Verification?
I've been looking into $\mathsf{QPIP}_\tau$ as a complexity class. The following will be a summary of definition 3.12 in Classical Verification of Quantum Computations by Urmila Mahadev.
A language ...
- 171
4
votes
2
answers
347
views
Has any research been done on quantum Zeno machines?
Zeno machines (abbreviated ZM, and also called accelerated Turing machine, ATM) are a hypothetical computational model related to Turing machines that allows a countably infinite number of algorithmic ...
- 3,272
6
votes
2
answers
177
views
Clarification needed: "Simulation" of $e^{-iHt}$ and its time complexity
On page 3 here it is mentioned that:
However, building on prior works [32, 36, 38] recently it has been
shown in [39] that to simulate $e^{−iHt}$ for an $s$-sparse Hamiltonian
requires only $\...
- 16.9k
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
4
votes
0
answers
110
views
Why is there no $N$ in the time complexity of the QLSP algorithm by Childs et al.?
The paper Quantum linear systems algorithms: a primer by Dervovic et al has this table on page 3:
I'm not sure why there's no $N$ in the time complexity of the algorithm by Childs et al. i.e. $\...
- 16.9k
6
votes
1
answer
248
views
Can we use quantum machines to reduce space complexity of deterministic turing machines?
Can we convert every algorithm in $\text{P}$ (polynomial time complexity for deterministic machines) into a quantum algorithm with polynomial time and $O(\log n)$ quantum bit?
- 201
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
7
votes
1
answer
150
views
Relation between $\mathrm{QMA}$ and $\mathrm{P^{QMA}}$
What is the relation between $\mathrm{QMA}$ and $\mathrm{P^{QMA}}$ and how do we prove it? Are these classes equal?
- 73
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
3
votes
2
answers
287
views
Hilbert space to accurately represent 3x3 Rubik's Cube
What Hilbert space of dimension greater than 4.3e19 would be most convenient for working with the Rubik's Cube verse one qudit?
The cardinality of the Rubik's Cube group is given by:
Examples
66 ...
- 3,272
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
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
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
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
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
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
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 $$...
5
votes
0
answers
66
views
Is PostBQP experimentally relevant? [duplicate]
Far from my expertise, but sheer curiosity. I've read that PostBQP ("a complexity class consisting of all of the computational problems solvable in polynomial time on a quantum Turing machine with ...
- 3,747
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 ...
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
7
votes
2
answers
229
views
Upper Bounds for QMA Quantum Merlin Arthur, and QMA(k)
QMA (Quantum Merlin Arthur), is the quantum analog of NP, and QMA(k) is the class with $k$ Merlins. These are important classes when studying Quantum Complexity theory. QMA(k) is QMA with $k$ ...
- 755
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
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
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
7
votes
0
answers
130
views
Empirical Algorithmics for Near-Term Quantum Computing
In Empirical Algorithmics, researchers aim to understand the performance of algorithms through analyzing their empirical performance. This is quite common in machine learning and optimization. Right ...
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
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
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
5
votes
1
answer
614
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 ...
- 183
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
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
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