Questions tagged [complexity-theory]
For questions regarding complexity analysis of quantum algorithms and comparisons with complexities of classical algorithms.
276
questions
0
votes
1
answer
55
views
If all terms of a local Hamiltonian commute, how hard is it to learn the ground state (energy)?
Suppose we have a $k$-local Hamiltonian with each of $m$ terms acting on $k$ of $n$ qudits of constant dimension $d$:
$$H=H_1+H_2+\cdots+H_m.$$
If at least some of the terms don't commute, e.g., if $[...
- 10.7k
1
vote
0
answers
36
views
The no fast forwarding theorem and exponential advantage for many body Hamiltonians
When simulating Hamiltonians in first quantization there are $\eta$ particles occupying a grid of $N$ grid points. In the first quantization, you directly discretize the differential operators onto a ...
- 611
5
votes
2
answers
144
views
Why is it hard to prove complexity bounds for variational algorithms?
I'm not very familiar with variational algorithms, but I've heard people say that they're "heuristic" and it's difficult to measure their performance via complexity analysis. Why is this the ...
- 145
3
votes
0
answers
78
views
Complexity of the quantum circuits that are needed to implement communication protocol?
Consider the following simultaneous communication problem. Alice and Bob do not share any
entanglement or any common randomness, and cannot communicate directly with each other. As
inputs, x is given ...
- 31
2
votes
0
answers
27
views
Why is 3-Coloring in PQMA(2)?
I'm reading https://arxiv.org/abs/0709.0738 about the complexity of PQMA(2) and its relation to NP. It describes a PQMA(2) protocol (3.1) for 3-coloring which contains the following check:
For both $|...
- 21
2
votes
1
answer
83
views
Quantum circuits, quantum Turing machine and universal quantum computer-comparing different models of quantum computations
Forgive me if this question was already asked somewhere on this site-I haven't found it but it is possible that I've overlooked it. So basically, I would like to summarize different notions of quantum ...
- 133
1
vote
0
answers
51
views
What is the quantum circuit complexity of a multi-control Y-gate with n control bits and 1 output bit?
It is known that many multicontrol quantum gates consist of sets of elementary gates, and there seems to be no authoritative way to give the complexity of such multicontrol quantum gates. So using one ...
- 526
3
votes
1
answer
46
views
Simulating Sparse Hamiltonians: help understanding query complexity bounds
tl;dr: How can I show that $e^k/k^k$ is less than $\epsilon^2/2$ when $k=\Omega\left(\frac{\log(1/\epsilon)}{\log \log(1/\epsilon)}\right)$, where $k,\epsilon\in \mathbb{R}$ and > 0?
Context:
Berry ...
- 33
4
votes
1
answer
129
views
Quantum algorithm to get $d$ (private exponent) directly without factoring first
Shor's algorithm is for finding period $r$ such that $a^r\equiv 1\bmod N$. Knowing period we can factor $N$.
In RSA we encrypt message $m$ by $m^e\bmod N$ ($e$ and $N$ are public keys).
Let us pick ...
- 141
1
vote
1
answer
55
views
Efficiently simulating a BQP circuit and polynomial hierachy collapse
If we were able to simulate a BQP (Bounded-error Quantum Polynomial time) circuit using a classical computer in an efficient manner, does it necessarily mean that the Polynomial Hierarchy (PH) would ...
- 2,369
1
vote
0
answers
19
views
Intuitive explanation on dependence of Hamiltonian simulation on norm?
Suppose I have two Hamiltonians, $H_1$ and $H_2$, that I want to simulate for time $T$. If $\|\|H_1\|\|>\|\|H_2\|\|$, why is it more costly to simulate $H_1$ compared to $H_2$? Is there an ...
- 145
2
votes
1
answer
74
views
How many eigenstates are accessible in polynomial time?
A result of Hamiltonian complexity theory by Poulin et al. shows that only a small fraction of the volume of Hilbert space can be reached in polynomial time for any physical system or quantum computer....
- 508
4
votes
1
answer
124
views
In Shor's algorithm, what is the exact analysis of its time and probability complexity?
Generally exact complexities aren't interesting, but I couldn't find any info on it for this case at all.
Specifically my question, is let's say I have a polynomial p(n) and I want to have a quantum ...
- 49
3
votes
1
answer
52
views
Relation between BQP-Complete and $BQP\setminus PH$
Recently the separation between BQP and PH has been proven. Does this result tell us something about the relation between BQP-complete problems (e.g. approximation jones polynomial solved by AJL ...
- 681
1
vote
1
answer
62
views
Amplitude Estimation/Counting - unsatisfiability
The Amplitude Amplification paper states in Theorem 13:
For any positive integers $M$ and $k$, and any Boolean function $f: \{0,1,\ldots,N-1\}\rightarrow\{0,1\}$, the algorithm Count $\left(f,M\right)...
- 111
1
vote
1
answer
96
views
Question about the definition of BQP-completeness
From what I know, a problem $p_0$ is BQP-complete if you can reduce any BQP problem $p$ to $p_0$.
There will be an overhead involved in doing the reduction from $p$ to $p_0$. What I was wondering was ...
- 133
4
votes
1
answer
97
views
Is BQP or PromiseBQP the better formalization of the set of "problems" that a quantum computer could solve efficiently?
This question is inherently somewhat subjective, but here goes.
BQP is (roughly) defined to be the set of decision problems that can be efficiently solved by a quantum computer. PromiseBQP is (roughly)...
- 2,641
11
votes
2
answers
1k
views
Are there any quantum algorithms conjectured to give an exponential speedup for a non-oracle problem that don't use the Quantum Fourier Transform?
The Quantum Fourier Transform (QFT) subroutine seems ubiquitous in most quantum algorithms that are conjectured to give an exponential (or at least superpolynomial) speedup over the best classical ...
- 2,641
2
votes
1
answer
48
views
Change of basis on a per vector component level
Suppose we have an $n$-qubit quantum state in the computational basis encoded in a classical blackbox function $f(x)$. That is, with $x \in \{0,1\}^n$ we can query $f$ and get the respective ...
- 2,369
0
votes
0
answers
27
views
On quantum and classical complexity [duplicate]
Do we have an example of a task that provably consumes more time/memory in the case of a classical computer than a quantum one? For example, Shor's factorization is polynomial, while the classical ...
3
votes
3
answers
253
views
Is verifying the solution to a QMA-complete problem efficient?
I am interested in the current state of the art on the difficulty of verifiability of a QMA complete problem, such as the local Hamiltonian problem. Suppose you are given a solution to a QMA complete ...
- 365
1
vote
0
answers
14
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
4
votes
0
answers
40
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 ...
- 348
2
votes
1
answer
78
views
Confusion regarding hardness of BQP
Consider a polynomial time quantum circuit on $n$ qubits. The class of circuits under consideration encompasses the complexity class $\mathsf{BQP}$.
Now, say we have an $n-1$ qubit polynomial time ...
- 1,251
0
votes
0
answers
27
views
Derivation of complexity for data encoding schemes
Could anyone help to derive the space-time complexities of the following different data encoding schemes ?
- 7
6
votes
1
answer
192
views
How would HSP with $S_N$ work when the automorphism subgroup is (almost) equal to the symmetric group?
The graph isomorphism problem can be reduced to a case of the hidden subgroup problem, with the group $S_N$ and the function $f \colon \pi \mapsto \pi(G)$ where $G$ is some graph, and $\pi \in S_N$.
...
- 249
1
vote
1
answer
224
views
Is QFT really faster FFT?
The standard DFT:
$$X[k]=\sum_{n=0}^{N-1}x[n]e^{-j2 \pi kn/N} \tag{1}$$
takes approximately $N^2$ complex summations and multiplications (or $\mathcal{O}(N^2)$). The faster version of FT known as FFT ...
- 249
0
votes
0
answers
27
views
Parallel repetition to amplify the gap for nonlocal games
Suppose for an one-round nonlocal game $G$ with question size $n$, answer size $2$ (i.e the answer is yes or no), a verifier and two provers Alice and Bob sharing $\text{Poly}(n)$ entangled-qubits. If ...
- 123
3
votes
1
answer
78
views
Computational complexity of the circuit model vs adiabatic model?
I'm trying to understand how computational complexity is quantified in adiabatic quantum computing.
With the circuit model, computational complexity is simple: count the number of times you queried ...
anon
2
votes
0
answers
70
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 ...
- 71
5
votes
0
answers
75
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
1
vote
0
answers
25
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 ...
- 684
2
votes
0
answers
55
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 ...
- 383
2
votes
0
answers
32
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 ...
- 383
1
vote
1
answer
60
views
Is Hamiltonian simulation with only real entries BQP-complete?
It is often asserted that Hamiltonian simulation (given some Hermitian matrix, $H$) is BQP-complete.
I don't see how the input to such an algorithm is done without the use of some block-encoding or ...
- 383
1
vote
0
answers
27
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 ...
- 383
10
votes
2
answers
733
views
What is the complexity of determining if a state is entangled?
I have been looking around for an answer to this question but can't really come up with anything. Given some oracle, $U$, that maps $| 0 \rangle$ to $| \psi \rangle$, is there some algorithm that ...
- 383
1
vote
1
answer
46
views
Are Quantum Algorithms that construct another Quantum Algorithm still valid to solve problems in BQP?
The title of this question is somewhat convoluted. Essentially, a problem is in BQP if there is a Turing machine that runs in polynomial time that computes a polynomial depth quantum circuit that ...
- 107
6
votes
1
answer
113
views
Polynomial time reductions vs. Quantum Polynomial time reductions
In computer science, a language $A$ reduces to a language $B$ if there exists a computable function (one that can be computed by a Turing machine) $f_{AB} \colon \Sigma^* \mapsto \Sigma^*$ such that $...
- 249
6
votes
1
answer
521
views
Is the Deutsch-Jozsa problem in NP?
The Deutsch-Jozsa problem is a problem that quantum computers can solve deterministically, while classical computers cannot. However, there are classical algorithms that can solve it probabilistically....
- 249
2
votes
2
answers
84
views
If sampling the output of $U_1U_2$ is easy, is sampling the output of $(U_1U_2)^\dagger$ also easy?
Let $U_1$ and $U_2$ be $n$-qubit unitaries, and denote by $P_{U_1U_2}(y \mid x) = |\langle y | U_1U_2 | x \rangle|^2$ the probability of measuring $y \in \{0,1\}^n$ on input $x \in \{0,1\}^n$. Suppose ...
- 429
2
votes
2
answers
487
views
What exactly are "variational quantum algorithms"?
I constantly see papers on "variational quantum algorithms" but I don't really see any explanation of what they are that are clear to me.
I found out about the variational method in quantum ...
- 249
2
votes
1
answer
69
views
Where is "quantum search" in the complexity hierarchy?
Grover's algorithm is one of the most popular quantum algorithms that solves the problem of "quantum search." But what is this problem, and what are its characteristics.
When considering ...
- 249
7
votes
2
answers
287
views
Is APPROX-QCIRCUIT-PROB a BQP-complete problem?
I've read contradictory information: on the Wikipedia page for BQP, it is written without proof that "APPROX-QCIRCUIT-PROB is a BQP-complete problem", while I have read elsewhere (don't ...
8
votes
1
answer
518
views
Is it known that BQP is not contained within NP?
I recently stumbled upon this paper here and here on the "deep ai" website that claims "BQP is not in NP."
I thought that this result would be huge (as a corollary would be that $...
- 379
1
vote
1
answer
96
views
Why is the application of a Quantum Fourier Transform constant time?
I am just curious (complexity theory wise) why the unitary matrix for the QFT (Quantum Fourier Transform) is constant time. From what I know, there is no general way to represent it as a sequence of ...
- 379
3
votes
1
answer
163
views
What are some examples of uncomputability with quantum computers?
It is sometimes said that quantum effects lead to non computable results in the weak sense that quantum computers might allow truly random actions (at least according to some interpretations). I think ...
- 2,202
2
votes
1
answer
850
views
Are there computational problems with classical advantage over quantum computing?
There are many instances, at least in theory, of problems that quantum computers can solve faster than classical computers. On the other hand, quantum computers are capable of computing anything that ...
- 365
2
votes
0
answers
74
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>$...
4
votes
1
answer
167
views
Is it known whether the Fermi-Hubbard ground state can be prepared efficiently or not?
Naturally, in general, ground state preparation is QMA-complete. There exists a paper by Andrew Childs, David Gosset & Zak Webb, which shows that ground state preparation for the Bose-Hubbard ...
- 93