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
3
votes
2answers
29 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
35 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 ...
1
vote
1answer
117 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
59 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
118 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
25 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
106 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
126 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
34 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
5
votes
1answer
82 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
59 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
46 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
141 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
51 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
149 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
77 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
40 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
140 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
182 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
32 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
46 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
25 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
200 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
165 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
124 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
104 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, ...
0
votes
0answers
52 views

Illustrating limitations of quantum computing

Can you illustrate why even with a functioning quantum computing energy minimization in an Ising Model simulation, an NP-hard problem, cannot be solved?
4
votes
1answer
37 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
207 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
0answers
58 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
80 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
27 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
70 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
237 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
510 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, ...
2
votes
1answer
101 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 ...
2
votes
1answer
221 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 $...
6
votes
1answer
164 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 ...
2
votes
1answer
251 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?
8
votes
2answers
2k 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 ...
5
votes
0answers
229 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 ...
2
votes
0answers
69 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 ...
4
votes
2answers
124 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: $\...
5
votes
1answer
123 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 ...
5
votes
1answer
167 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 ...
8
votes
2answers
258 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 ...
4
votes
1answer
467 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 ...