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
7
votes
1answer
390 views

Classical algorithm with complexity similar to Shor's discovered: Are there more efficient quantum algorithms than Shor's?

In the article Fast Factoring Integers by SVP Algorithms the author claims that he discovered classical algorithm for factoring integers in polynomial time. The Quantum Report mentioned here that it ...
1
vote
1answer
67 views

What does "large-scale universal quantum computation" mean?

I was reading this lecture notes by Sevag Gharibian. He mentioned the following statement: Large-scale universal quantum computer can be built. I do understand what quantum computer is, but I don't ...
2
votes
1answer
93 views

How do I calculate the number of uses of a unitary $U$ in iterative phase estimation?

How would one go along to calculate the number of uses of an unitary $U$ in Iterative Phase Estimation (IPE) to compare it to the number of uses of $U$ in standard Phase Estimation (Qiskit QPE)?
8
votes
2answers
171 views

Why does QAOA achieve quantum supremacy in an algorithmic sense?

In the paper Quantum Supremacy through the Quantum Approximate Optimization Algorithm the authors claim (last sentence of page 15): "If [...] the QAOA outperforms all known classical algorithms ...
6
votes
1answer
36 views

List of problems in the query complexity model with no super-polynomial quantum speedup

Similar to this list over at cstheory, I'm looking for a list of computational problems in the query complexity model for which it is known that no super-polynomial quantum speedups exist. What are ...
6
votes
1answer
94 views

Properties of QAOA

The QAOA algorithm consists of two elements: The outer loop, basically a classical optimization algorithm The quantum circuit, taking $2p$ parameters (where $p$ is the number of layers, where each ...
7
votes
2answers
167 views

What is the computational complexity of quantum annealing?

Quantum annealing can be thought of as a black box solver that can find approximate solutions to hard optimization problems. For example, D-Wave quantum annealers can approximately solve quadratic ...
4
votes
2answers
201 views

CS conjecture that Quantum Computer cannot solve NP-complete problems, but Boson Samplers do a #P-hard problem. How is it?

There is something very strange and absurd for me about the power of a quantum computer. Let me briefly states the following facts: Fact 1: theoretical computer scientists believe (very likely to ...
3
votes
0answers
32 views

What is the computational complexity of approximate quantum adders, in terms of big O notation?

I have recently found papers on approximate quantum adders. However, the papers do not seem to mention the computational complexities of their algorithms. What are their complexities, in terms of big ...
6
votes
1answer
187 views

Are almost-Clifford circuits almost easy to simulate?

Circuits consisting entirely of Clifford operations in $\{X, Y, Z, H, S, \text{CNOT} \}$ are "easy" to simulate classically since there is a method that can fully compute such circuits over $...
4
votes
2answers
883 views

Do there exist problems known to be computationally intractable for quantum computer, but tractable for classical computer?

Or alternatively phrased, is it believed that the complexity class P is a complete subset of BQP? Consider the following diagram à la MIT OpenCourseWare, which seems to explicitly state as much.
9
votes
0answers
163 views

What is stopping FACTORING from being BQP-complete?

Classical complexity theory makes much of the study of so-called intermediate problems - that is, problems that are in $\mathsf{NP}$ but are nonetheless not known to be in $\mathsf{P}$ and further not ...
7
votes
2answers
201 views

What kind of boolean functions are faster to compute on qc?

Deutsch-Jozsa algorithm can compute if some function $f : \{0,1\}^n \rightarrow \{0,1\} $ is constant. This goes exponentially faster than on classical computers. If we consider the set of all boolean ...
4
votes
0answers
64 views

Complexity of controlled operations in a two-level unitary operation

In Neilsen and Chuang, chapter 4.5.2 (~p.193), why did the authors come to the conclusion that complexity of operations $C^n(X)$ and $C^n(\tilde{U})$ is $O(n)$? Did they assume using work qubits? If ...
2
votes
1answer
35 views

Hybrid lower bound proof Kaye Laflamme Mosca (lemma 9.3.6)

I am confused about one point in the proof on the lower bounds in Kaye, Laflamme Mosca's lemma 9.3.6. Context: $|\psi_T\rangle$ is the final state of the search algorithm that started on the all-zero ...
3
votes
0answers
83 views

How close is the history state to the ground state in the Kitaev clock construction?

Consider a standard circuit to Hamiltonian reduction in QMA. For example, refer here (Vazirani's lecture notes) or page 235 of here (survey by Gharibian et al). The history state of the Kitaev clock ...
1
vote
1answer
71 views

PreciseQMA = PreciseBQP gives PP = PSPACE

$\text{PreciseBQP}$ is defined as $\text{BQP}$ with inverse exponentially close completeness and soundness bounds (for a better definition, see Section 3.1 here, in the paper by Gharibian et al). ...
7
votes
1answer
107 views

Could random quantum circuits be efficiently approximately simulated?

Google's landmark result last year was to compute a task with a quantum computer that a classical computer could not compute, and they chose random circuit sampling. Part of their justification was ...
4
votes
0answers
45 views

Bound on quantum speedups under various models of complexity

What are the bounds on quantum speedups under the various models of complexity? How big or small can they be? Under the query model, my understanding is that the lower bound is $\Omega(\sqrt{N})$ as ...
3
votes
1answer
152 views

BQP and PH separation

I was reading the Quanta article here which shows that there exists a problem which achieves "oracle separation between BQP and PH". In simple terms, there exists a problem which a quantum ...
2
votes
0answers
58 views

How precise are BQPSPACE measurements?

This is in a similar spirit to another question I asked here. Let's say I am given a $k$-local Hamiltonian $H$. We know that $||H|| \leq 1$. Let the ground state be $|\psi_{0}\rangle$, with energy $E_{...
1
vote
1answer
30 views

How precise are BQP measurements?

Let's say I am given a Hamiltonian $H$, whose ground state is efficiently preparable. We know that $||H|| \leq 1$. Let that ground state be $|\psi_{0}\rangle$, with energy $E_{0}$. We also know that ...
1
vote
1answer
113 views

Dirichlet distribution: posteriors and priors of distribution

Let $|\psi\rangle \in \mathbb{C}^{2n}$ be a random quantum state such that $ |\langle z| \psi \rangle|^{2} $ is distributed according to a $\text{Dirichlet}(1, 1, \ldots, 1)$ distribution, for $z \in \...
4
votes
1answer
85 views

What is the relationship between quantum circuit and quantum query complexities?

I am trying to ascertain a precise understanding of the relationship between the quantum query model of complexity and the quantum circuit model of complexity. Specifically, is there an established ...
4
votes
1answer
318 views

Proof that any unitary can be written as $U=e^{-iH}$ with $H$ Hamiltonian with bounded norm

I am looking for a proof that any unitary matrix can be written as: $$U = e^{-iH}$$ where $H$ is some Hamiltonian with bounded norm. That is $$||H||_{2} = O(1).$$
5
votes
1answer
244 views

Proof using hybrid method that inverting a permutation requires exponential queries for BQP machines

Let's say I am given a permutation $\sigma$ that maps $n$ bit strings to $n$ bit strings. I want to output $1$ if $\sigma^{-1}(000\cdots1)$ is even and $0$ if $\sigma^{-1}(000\cdots1)$ is odd. It can ...
2
votes
2answers
170 views

Question regarding soundness bound in QMA versus QCMA separation

I am trying to understand the soundness bound reached in Theorem 4 of this paper, which deals with separating $QMA$ and $QCMA$ with respect to an in-place oracle. To state just the part I am confused ...
3
votes
0answers
53 views

What is the query complexity of the QUBO algorithm?

What is the complexity of the quantum unconstrained binary optimization (QUBO) algorithm in the number of queries to the quantum processor? To clarify, I'm asking about the complexity on quantum ...
3
votes
0answers
97 views

What is known about the quantum version of Schoening's algorithm for 3SAT?

Schoening's algorithm for 3SAT can be converted to a quantum algorithm.  The classical circuit representing a 3SAT expression in CNF form can be converted to a quantum version involving reversible ...
9
votes
0answers
176 views

Is HHL still BQP-complete when the matrix entries are only in {0,1}?

I'm studying BQP-completeness proofs of a number of interesting problems of Janzing and Wocjan, and Wocjan and Zhang. Janzing and Wocjan show that estimating entries of matrix powers $(A^m)_{ij}$ with ...
8
votes
1answer
324 views

Consequences of $MIP^\ast=RE$ Regarding Quantum Algorithms

The (pending-peer review) proof of $MIP^\ast=RE$ in this pre-print has been hailed as a significant breakthrough. The significance of this result is addressed by Henry Yuen (one of the authors) in ...
2
votes
1answer
83 views

Does finding an algorithm that solves an NP-Problem in Polynomial time in a Quantum Computer imply P = NP?

I was wondering if the complexity of a quantum circuit that solves a problem that is in NP implies P=NP?
1
vote
0answers
45 views

Hardwiring the output in black box separation

In this paper, while using a diagonalization argument in Section $5$, the authors write: Fix some enumeration over all $poly(n)$-size quantum verifiers $M_{1}, M_{2},...$ which we can do because the ...
4
votes
2answers
302 views

How do I check if a gate represented by Unitary $U$ is a Clifford Gate?

The Gottesman–Knill theorem states that stabilizer circuits, circuits that only consist of gates from Clifford group, can be perfectly simulated in polynomial time on a probabilistic classical ...
3
votes
1answer
410 views

Can quantum computers be used to solve P = NP

The P versus NP problem is a major unsolved problem in computer science. It asks whether every problem whose solution can be quickly verified can also be solved quickly. It is one of the seven ...
5
votes
0answers
41 views

Equivalence checking of quantum circuits up to error

Suppose you are given two circuit descriptions $A$ and $B$ where by a circuit description I mean a sequence of gates (in the order they are applied) and the qubits they are applied on. (For the sake ...
0
votes
0answers
44 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: ...
6
votes
2answers
84 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 $...
4
votes
0answers
47 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
votes
1answer
36 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
1answer
114 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 ...
3
votes
1answer
70 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
41 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
1answer
31 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 ...
3
votes
0answers
55 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)$. ...
2
votes
1answer
136 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 ...
2
votes
1answer
55 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\...
3
votes
2answers
165 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
69 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
97 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 ...