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
2
votes
1answer
27 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 ...
2
votes
0answers
54 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
54 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). ...
6
votes
1answer
77 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 ...
2
votes
0answers
19 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
54 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 ...
1
vote
0answers
45 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
26 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
92 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
68 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
298 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).$$
4
votes
1answer
213 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
161 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 ...
2
votes
0answers
23 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 ...
2
votes
0answers
47 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 ...
7
votes
0answers
127 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 ...
7
votes
1answer
237 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
56 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
44 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
92 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 ...
1
vote
1answer
75 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 ...
4
votes
0answers
35 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
38 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
70 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
28 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
31 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
76 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
48 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
39 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
26 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
27 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
66 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
28 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
124 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
43 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
63 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
58 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 ...
3
votes
1answer
291 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 ...
5
votes
1answer
150 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
640 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. ...
3
votes
1answer
43 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
112 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
1answer
185 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
42 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
105 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
6answers
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 ...
3
votes
0answers
82 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
58 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
165 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
58 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 ...