Questions tagged [complexity-theory]

For questions regarding complexity analysis of quantum algorithms and comparisons with complexities of classical algorithms.

Filter by
Sorted by
Tagged with
0
votes
0answers
36 views

Rings or algebras with many nilpotent elements and efficient computation

Searching the web for '"quantum computer" nilpotent' returns many results, so maybe the question is ontopic for this site. Can a quantum computer solve the following mathematical problem: ...
5
votes
2answers
62 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 $...
3
votes
0answers
19 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 "...
1
vote
1answer
27 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))...
7
votes
0answers
44 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 ...
2
votes
1answer
37 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 ...
0
votes
0answers
36 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$  ...
1
vote
1answer
23 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 ...
2
votes
0answers
20 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)$. ...
3
votes
1answer
37 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 ...
1
vote
1answer
22 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\...
2
votes
2answers
111 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 ...
2
votes
1answer
37 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 ...
3
votes
2answers
50 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 ...
0
votes
0answers
50 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 ...
2
votes
1answer
198 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 ...
4
votes
0answers
82 views

Is Connes' Embedding Problem akin 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 (...
8
votes
1answer
306 views

Why Non-Clifford gates are 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. ...
3
votes
1answer
32 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 $...
5
votes
1answer
109 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
votes
0answers
155 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}$ ...
-2
votes
1answer
39 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
6
votes
1answer
91 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 ...
9
votes
5answers
1k 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 ...
2
votes
0answers
62 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 ...
3
votes
0answers
52 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 ...
3
votes
2answers
150 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 ...
6
votes
0answers
54 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 ...
19
votes
2answers
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 ?...
6
votes
3answers
171 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 ...
1
vote
0answers
88 views

What is the cost of implementing the Quantum Fourier transform in a classical computer?

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$ ...
4
votes
0answers
42 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 ...
5
votes
2answers
145 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 ...
5
votes
2answers
240 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}$ ...
3
votes
0answers
37 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 ...
4
votes
0answers
47 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 ...
0
votes
1answer
32 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 \...
4
votes
1answer
213 views

Quantum State Sanitizing

I was reading these lecture notes from Prof. Aaronson about Waltrous's MA protocol for the group non-membership problem. At the end of the description, there's an approach to distinguish if Merlin ...
10
votes
1answer
216 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 ...
3
votes
1answer
142 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 ...
5
votes
1answer
106 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, ...
4
votes
1answer
38 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 ...
4
votes
1answer
215 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 ...
3
votes
2answers
88 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....
3
votes
1answer
86 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 ...
3
votes
0answers
28 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 ...
2
votes
1answer
77 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 ...
6
votes
0answers
252 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 ...
7
votes
2answers
1k 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 ...
11
votes
0answers
588 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, ...