Questions tagged [complexity-theory]
For questions regarding complexity analysis of quantum algorithms and comparisons with complexities of classical algorithms.
255
questions
6
votes
2
answers
115
views
State of the art of SAT on a quantum computer
Disclaimer: I don't understand quantum computing.
Given a CNF boolean formula $\phi$ in $n$ variables
and quantum computer with $q$ qubits, what is the
complexity of solving $\phi$ as a function of $...
- 171
4
votes
0
answers
71
views
Is either the adiabatic or the diabatic version of quantum annealing known to be theoretically more powerful than the other?
Quantum annealing can be considered either in the perfectly adiabatic "slow" limit (in which case it's usually referred as "adiabatic quantum computing" (AQC) instead of "...
- 2,347
2
votes
1
answer
45
views
Efficient diagonalisation of low-rank observables
Let $n$ be the number of qubits we're using, and let $$\mathrm H=\sum_{i=1}^T\alpha_i\mathrm U_i|0\rangle\langle0|\mathrm U_i^\dagger$$ be an $n$-qubit hermitian observable where $T=O(\mathrm{poly}(n))...
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
4
votes
1
answer
96
views
Could finding Golomb rulers be in $\mathrm{BQP}$?
The problem of factoring large numbers may be in the so-called "intermediate" regime. These are problems that are in $\mathrm{NP}$, but are neither likely to be easy enough to be in $\mathrm{P}$ nor ...
- 9,332
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$ ...
2
votes
1
answer
38
views
Do we already know some problems, that would be hard to solve for quantum computers, and use them in cryptography? [duplicate]
I was wondering, whether there are any problems that we already know are difficult to solve for a quantum computer, and that we could potentially use in cryptography, just as we do now with e.g. the ...
- 1,019
3
votes
0
answers
115
views
How to find a marked item out of $K < N$ marked items when K is unknown?
I'm wondering about time complexities of variants of the searching problem in Grover's Algorithm. I know that using G.A. the time complexity required to find a market item reduces to $O(\sqrt N)$.
...
- 53
3
votes
1
answer
280
views
Speed up in Bernstein-Vazirani algorithm and Gottesman-Knill theorem
The Bernstein-Vazirani problem:
Let $f$ be a function from bit strings of length $n$ to a single bit,
$$f: \{ 0, 1\}^n \to \{0, 1\} $$
thus all input bit strings $x \in \{0,1\}^n$. There exists a ...
- 13.3k
2
votes
1
answer
125
views
On the complexity of an oracle for a classical function
Let us assume that we have a classical function $f:\{0\,;\,1\}^n\to\{0\,;\,1\}^m$ which is efficiently computable. Then, its oracle is defined with $\mathbf{U}_f\,|x\rangle\,|y\rangle=|x\rangle\,|y\...
- 4,603
3
votes
2
answers
234
views
How to check if a quantum circuit is deterministic?
I'm trying to find a way to check if a given quantum circuit is essentially a classical one (up to changes in phase).
Given a description of a quantum circuit by a list (of size $l$) of ordered ...
- 111
2
votes
1
answer
125
views
Two commuting Hamiltonians
Let's say I have 2 commuting Hamiltonians that are not degenerate, I know it means that they a have a common energy basis, yet does it mean that they also have the same ground state? Or is there any ...
- 21
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
1
vote
0
answers
242
views
Not sure what do Nielsen and Chuang mean by number of operations
I am reading Nielsen and Chuang's "Quantum Computation and Quantum Information". One important concept about algorithms is how the number of operations scales with the length of the input. I realized ...
- 316
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
5
votes
1
answer
289
views
Is Connes' Embedding Problem akin to the word problem for finitely presented groups?
The complexity class $\mathrm{MIP^*}$ includes the set of languages that can be efficiently verified by a classical, polynomially-bounded verifier, engaging with two quantum provers that can share (...
- 9,332
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
3
votes
1
answer
160
views
Probabilistic query complexity lower bound for Bernstein-Vazirani problem
In the Bernstein Vazirani algorithm, the problem is to find $s$ for $f(x) = s \times x $ , $f : \{0,1 \}^n \to \{0 , 1 \} $. The literature says that the classical randomized algorithms also requires $...
- 31
5
votes
1
answer
135
views
How powerful would quantum computers be if we had direct access to the full state vector?
The state vector is exponential in size, so we can manipulate an exponential quantity of information with a linear quantity of gates. However, this doesn't give us general exponential speedup because ...
- 3,978
3
votes
1
answer
263
views
On the probability of preparing of a uniform superposition by performing a controlled-multiplication and post-selecting $0$
I take as a starting point Watrous's celebrated paper defining the Quantum Merlin-Arthur (QMA) class. He provides a protocol for Arthur to test whether an element $h$ is not in a group $\mathcal{H}$ ...
- 9,332
-2
votes
1
answer
57
views
How does number of shots (number of times the computation is repeated) affects time complexity [closed]
I want to know what happens to the time complexity in terms of big O analysis
- 1
6
votes
1
answer
226
views
Self reducibility of QCMA problems
Self reducibility is when search version of the problems in a language reduce to decision versions of the same problems. NP-complete problems are self reducible. Are QCMA complete problems self ...
- 1,119
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
3
votes
0
answers
103
views
Quantum algorithms, combinatorial optimization, and approximation bounds
Recently, I saw this article, Classical and Quantum Bounded Depth Approximation Algorithms where the author discusses the limitations of QAOA relative to classical approaches.
In particular, they ...
- 1,036
5
votes
1
answer
355
views
Marriott-Watrous style amplification with a quantum input
$\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
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
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
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
6
votes
3
answers
269
views
Is quantum complexity basis-invariant?
Quantum computing refers (occasionally implicitly) to a "computational basis".
Some texts posit that such a basis may arise from a physically "natural" choice.
Both mathematics and physics require ...
3
votes
0
answers
46
views
Explicit Construction of Classical Rules in Quantum Turing Machine
I knew that we usually use circuit instead of Turing machine in Quantum computation.
In a deterministic Turing machine one has transition rules,
$$
\delta: Q\times\Gamma\rightarrow Q\times\Gamma\...
- 175
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
2
votes
0
answers
170
views
What is the cost of implementing the Quantum Fourier transform in a classical computer? [closed]
What is the cost of implementing the Quantum Fourier transform (QFT) in a classical computer? We know we require at least $\log{n}$ depth quantum circuits to do a QFT in a quantum computer, with $n$ ...
- 1,119
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
5
votes
2
answers
203
views
Simulating depth-2 circuits
Quantum depth-2 circuits can be efficiently simulated classically, as shown in Proposition 2 of this paper. The following is a quote of the proof.
After the first time step the quantum state of the ...
- 1,119
6
votes
3
answers
860
views
Are there many practical problems for which Grover's algorithm beats the best heuristic classical algorithm?
It's well known that, given an oracle for a function $f$ from a very large set $S$ (of order $N \gg 1$) to $\{0, 1\}$, Grover's algorithm can find an element of $S$ that maps to 1 with $\sim \sqrt{N}$ ...
- 2,347
3
votes
0
answers
57
views
Estimating errors in Hamiltonian Simulation paper
I am looking at the paper: Simulating Hamiltonian dynamics with a truncated Taylor series and I am explicitly interested in Eq (15) and (16). These read
$$ ||PA |0\rangle |\psi \rangle - |0\rangle ...
- 849
5
votes
0
answers
94
views
complexity of classical counting algorithm
Does anyone know the solution of Exercise 6.14 of Nielsen and Cheung:
Prove that any classical counting algorithm with a probability at least
3/4 for estimating $M$ correctly to within an ...
- 103
0
votes
1
answer
69
views
Minimum Multi-Degree Polynomials representing Boolean Functions
In the 10th Anniversary Edition of Nielsen and Chuang Quantum Computation and Quantum Information textbook, Chapter 6.7 talks about Black Box algorithm limits.
It is given:
$f:\{0,1\}^n \...
- 455
4
votes
1
answer
251
views
Quantum State Sanitizing
I was reading these lecture notes from Prof. Aaronson about Watrous's MA protocol for the group non-membership problem. At the end of the description, there's an approach to distinguish if Merlin ...
- 175
12
votes
1
answer
446
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
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
1
answer
146
views
Can we amplify BPP algorithms with a random quantum circuit?
Suppose we are given a (univariate) polynomial $P$ of degree $d$, and we wish to determine if $P$ is identically $0$. A standard way to do this is to use a classical PRG to randomly sample $n$ bits, ...
- 9,332
5
votes
1
answer
51
views
Best query and memory complexity for iterated function
Assume $f(x)$ is n-bit to n-bit function. Let $F(x)$ be defined as $T$ iterations of $f(x)$, i.e. $F(x) = f^T(x)$.
Quantum algorithm relies on $F(x)$; it calls it $R$ times.
What is the best query ...
- 71
4
votes
1
answer
366
views
CTCs and information time travel — what non-trivial insights do they lead to?
Context:
In quantum complexity theory and quantum information, there are several papers which study the implications of closed timelike curves (CTCs). In 2008, Aaronson and Watrous published their ...
- 16.9k
5
votes
2
answers
325
views
References on quantum arithmetic circuit complexity
In classical computing, arithmetic circuit complexity is apparently a big topic. But I couldn't find much about the complexity of quantum arithmetic circuits. Almost all references like arXiv:1805....
- 16.9k
3
votes
1
answer
180
views
Cost of implementing Boolean function quantumly?
Say, I wanted to implement a unitary $U_f$ to compute a Boolean function $f:B_n \to B_n$. This is done by the unitary $$U_f|x\rangle | y \rangle =
|x\rangle|y\oplus f(x)\rangle$$ which one can ...
- 849
4
votes
0
answers
47
views
Complexity analysis of separability in the multipartite case
It's well known that determining whether a bipartite mixed state is separable or entangled is a $\mathsf{NP}$-hard problem under some accuracy estimates (cf. this TCS SE discussion). Now I'm curious ...
- 16.9k
2
votes
1
answer
118
views
Is it possible to construct an equivalent quantum circuit from a CORDIC-based digital circuit?
DaftWullie mentions an interesting point here:
let's assume that we know an efficient classical computation of $f(x)$. That means we can build a reversible quantum computation that runs in the same ...
- 16.9k
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,332
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