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
8
votes
0answers
63 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
511 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
49 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 ...
5
votes
0answers
59 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
47 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 \...
5
votes
1answer
127 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, ...
11
votes
2answers
5k 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 ...
5
votes
1answer
47 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 ...
3
votes
1answer
125 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
1answer
153 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
102 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 ...
8
votes
1answer
440 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 $\...
2
votes
1answer
527 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 $...
4
votes
1answer
771 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 ...
7
votes
1answer
384 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 ...
6
votes
1answer
279 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 ...
44
votes
4answers
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 ...
2
votes
1answer
342 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?
9
votes
2answers
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 ...
9
votes
1answer
239 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 ...
3
votes
0answers
95 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 ...
5
votes
1answer
293 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 ...
6
votes
3answers
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 $...
5
votes
1answer
79 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 ...
11
votes
1answer
690 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 ...
11
votes
1answer
261 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 ...
34
votes
4answers
4k 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 ...
6
votes
1answer
168 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.
6
votes
2answers
136 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 $\...
4
votes
0answers
85 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. $\...
6
votes
1answer
218 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?
6
votes
1answer
133 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?
5
votes
6answers
435 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 ...
8
votes
2answers
1k 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 ...
12
votes
4answers
1k 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
0answers
49 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 ...
16
votes
1answer
292 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 ...
31
votes
2answers
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 ...
10
votes
2answers
758 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 ...
10
votes
2answers
487 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 ...
22
votes
2answers
3k 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) ...
6
votes
1answer
318 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 ...
7
votes
0answers
123 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
1answer
133 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 ...
10
votes
1answer
270 views

Are there any encryption suites which can be cracked by classical computers but not quantum computers?

Are there any encryption suites that can be cracked by usual computers or super computers, but not quantum computers? If that's possible, what assumptions will it depend on? (Factorizing big numbers, ...
5
votes
1answer
585 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 ...

1 2 3
4