Questions tagged [complexity-theory]
For questions regarding complexity analysis of quantum algorithms and comparisons with complexities of classical algorithms.
63
questions with no upvoted or accepted answers
13
votes
0
answers
418
views
Relation between quantum entanglement and quantum state complexity
Both quantum entanglement and quantum state complexity are important in quantum information processing. They are usually highly correlated, i.e., roughly a state with a higher entanglement corresponds ...
- 323
11
votes
0
answers
228
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 ...
- 9,346
10
votes
0
answers
298
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 ...
- 9,346
10
votes
0
answers
90
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 ...
- 201
8
votes
0
answers
147
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 ...
- 321
8
votes
0
answers
381
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 ...
- 9,346
7
votes
0
answers
58
views
Is there a practical architecture-independent benchmark suitable for adversarial proof of quantum supremacy?
Recent quantum supremacy claims rely, among other things, on extrapolation, which motivates the question in the title, where the word "adversarial" is added to exclude such extrapolation-...
- 326
7
votes
0
answers
130
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 ...
6
votes
0
answers
85
views
Postselection and hardness of estimating amplitudes
Let $A$ be a class of quantum circuits such that
\begin{equation}
\text{Post}A = \text{Post}BQP,
\end{equation}
where $\text{Post}$ indicates post-selection. Is only this amount of information ...
- 1,119
5
votes
0
answers
71
views
What is the computational complexity of decomposing operators in terms of quantum gates?
I have recently worked on a problem involving a rather large Hamiltonian, which I wrote some Python code for its generation following the method in this paper.
No when I used qiskits ...
- 51
5
votes
0
answers
102
views
Lowest energy problem with additional constraints
Consider the following minimization problem:
\begin{align}
&\min_{\rho} \mathrm{Tr}[\rho H] \\
\text{such that:}& \\
&Tr[\rho A_i] \leq 0 \ \ \forall A_i, \ i \in \{1,2,3,...\}
\end{align}
...
- 71
5
votes
0
answers
92
views
Consequences of MIP*=RE regarding quantum universality
Provided that $\mathsf{MIP}^*=\mathsf{RE}$ there can be Bell inequalities that have violations achievable only for infinite dimensional quantum systems (vide discussions in Post1 and Post2). Does this ...
- 2,247
5
votes
0
answers
54
views
Proving that with probability 1 $NP \nsubseteq BQP$ with respect to random oracles
In the paper Strength and Weakneses of Quantum Computers (https://arxiv.org/abs/quant-ph/9701001) by Bennet, Bernstein, Brassard and Vazirani, it is shown the statement in the title (Theorem 3.5 in ...
- 533
5
votes
0
answers
96
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 ...
- 156
5
votes
1
answer
96
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 ...
- 849
5
votes
0
answers
94
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 ...
- 103
4
votes
0
answers
35
views
Is there a general framework that allows us to compare probabilistic and deterministic algorithms fairly?
Many popular QC algorithms are probabilistic in nature, like Grover's, Shor's, QAOA ..etc
For some of these we have formulas that give probabilities of success (like for Grover's and Shor's), and for ...
- 249
4
votes
0
answers
116
views
Is the exponential speedup and output $\langle x|M|x\rangle$ in contradiction in HHL algorithm?
Isn't the exponential speedup and the output $\langle x|M|x\rangle$ in contradiction in HHL algorithm? How can we print the solution vector $|x\rangle$ without losing the exponential speedup?
- 51
4
votes
0
answers
64
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 ...
- 339
4
votes
0
answers
59
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 ...
- 1,036
4
votes
0
answers
71
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,357
4
votes
0
answers
47
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 ...
- 16.9k
4
votes
0
answers
110
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. $\...
- 16.9k
3
votes
0
answers
19
views
Can we have a constant-overhead threshold theorem?
The threshold theorem states that any abstract circuit in BQP can be computed by another polynomial-depth circuit that succeeds in the presence of noise. The original construction from 1996 requires ...
- 163
3
votes
0
answers
91
views
Relation between geometric and discrete circuit complexity
Geometric complexity of a unitary, as introduced for example here https://arxiv.org/abs/quant-ph/0502070, measures the length of a geodesic connecting the identity matrix and a given unitary in the ...
- 1,385
3
votes
0
answers
62
views
Could quantum computers answer the question of whether QCD predicts quark gluon confinement?
As I understand it, it is not known whether or not QCD actually predicts quark gluon confinement.
As I understand it answering questions in quantum field theories is generally harder in terms of ...
- 143
3
votes
0
answers
56
views
Feynman method and polynomial time algorithm for XQUATH
Consider the Feynman algorithm for simulating quantum circuits, as given here.
Consider the XQUATH conjecture for random quantum circuits from here, given by
(XQUATH, or Linear Cross-Entropy Quantum ...
- 1,119
3
votes
0
answers
54
views
Query complexity on Quantum Pattern Matching of Mateus Algorithm
I am trying to understand the complexity of the Mateus and Omar algorithm for quantum pattern matching, it is clear to me from the pseudocode that the query complexity is $O(\sqrt{N})$, apart from the ...
3
votes
0
answers
124
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,119
3
votes
0
answers
158
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 ...
- 131
3
votes
0
answers
263
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 ...
3
votes
0
answers
115
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)$.
...
- 53
3
votes
0
answers
104
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 ...
- 1,036
3
votes
0
answers
46
views
Explicit Construction of Classical Rules in Quantum Turing Machine
I knew that we usually use circuit instead of Turing machine in Quantum computation.
In a deterministic Turing machine one has transition rules,
$$
\delta: Q\times\Gamma\rightarrow Q\times\Gamma\...
- 175
3
votes
0
answers
57
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 ...
- 849
3
votes
0
answers
131
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 ...
- 488
2
votes
0
answers
47
views
Why do Hamiltonian simulation algorithms not depend on the size of the Hamiltonian for the gate complexity?
The wikipedia page for Hamiltonian simulation mentions the gate and query complexities for different algorithms used for the problem (Trotter-Suzuki, Taylor Series, Quantum Walks, and QSP).
They ...
- 373
2
votes
0
answers
26
views
Non-promise problems that are BQP complete, and showing them to be or not to be in NP
Whenever we discuss "BQP" as a complexity class, we often are really talking about "Promise-BQP" instead of BQP.
And the same goes for BQP-complete problems, all that I can find ...
- 373
2
votes
0
answers
46
views
Grover's algorithm for multiple solutions complexity
I'm reading Nielsen&Chuang book (for myself) and I'm completely stuck with one of the problems, 6.3(Database retrieval):
Given a quantum oracle which returns $\left|{k, y \bigoplus X(k)}\right>$...
2
votes
0
answers
319
views
What is the complexity of the Hadamard test and the SWAP test?
How to calculate the complexity of both the Hadamard test and SWAP test with $n$ qubits?
- 390
2
votes
0
answers
64
views
What is the explicit best known quantum algorithm for LWE?
Consider the learning with errors(LWE) problem which is known to be hard for quantum computers.
Let $q \geq 2$ be a prime integer. Consider us being given (polynomially many samples of) either:
$$A, ...
- 315
2
votes
0
answers
180
views
Is there an efficient quantum circuit that create a random permuntation matrix?
Suppose we want to generate a random, random according to some probability distribution, unitary permutation matrix that is applied to an input of $n$ qubits. So is there an efficient polynomial time ...
- 65
2
votes
0
answers
32
views
What constitutes generic dynamics, and how is it different from a fully random function?
What constitutes generic dynamics? And how is it different from a fully random function?
From what I understand, a fully random function is one that is "Haar" random. And generic dynamics, ...
- 110
2
votes
0
answers
111
views
Relation between approximate counting and sampling
Consider the following statement of Stockmeyer counting theorem.
Given as input a function $f:\{0, 1\}^{n} \rightarrow \{0, 1\}^{m}$
and $y \in \{0, 1\}^{m}$, there is a procedure that runs in ...
- 1,119
2
votes
0
answers
148
views
When is a Quantum Computer Slower Than a Classical Computer?
Someone offhandedly mentioned to me that quantum computers are sometimes significantly (I guess they meant asymptotically) slower than classical computers.
Unfortunately, I didn't get any arguments ...
- 121
2
votes
0
answers
77
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,119
1
vote
0
answers
7
views
How does Functional Completeness look like in the quantum world?
Can Post's theorem help to elucidate the nature of quantum logic or other non-classical logics? Quantum logic uses a different set of logical connectives than classical logic, which makes questions of ...
- 111
1
vote
0
answers
43
views
How to roughly analyze computational complexity of quantum circuit?
I'm looking for just a few simple calculations to analyze complexity when comparing quantum circuits.
I'll compare 2 scenarios, and I'd love for someone to critique or verify my analysis:
Circuit of ...
- 51
1
vote
0
answers
15
views
Can one simulate Gaussian Boson Sampling using Fock Boson Sampling or vice versa?
In Fock Boson Sampling, one starts with a particle-number state $|n_1, ..., n_m\rangle$ of $m$ modes, sends it to an interferometer effecting a unitary operation $U$ on the creation operators, and ...
- 664
1
vote
0
answers
26
views
Pure Product State Problem Clarification about $\alpha$-closeness and $\beta$-farness
I am reading a paper on entanglement, specifically, determining if a state is close to being entangled or not.
The problem first introduces the $(\alpha, \beta, l)$-Pure product state problem. This ...
- 373