Questions tagged [complexity-theory]
For questions regarding complexity analysis of quantum algorithms and comparisons with complexities of classical algorithms.
256
questions
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
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
1
vote
1
answer
63
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,119
0
votes
0
answers
15
views
Derivation of complexity for data encoding schemes
Could anyone help to derive the space-time complexities of the following different data encoding schemes ?
- 1
6
votes
1
answer
180
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$.
...
- 227
1
vote
1
answer
121
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 ...
- 219
0
votes
0
answers
10
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
2
votes
1
answer
58
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
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
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
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
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
1
vote
1
answer
35
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 ...
- 373
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
10
votes
2
answers
700
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 ...
- 373
1
vote
1
answer
34
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 ...
- 87
5
votes
1
answer
77
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 $...
- 227
6
votes
1
answer
471
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....
- 227
2
votes
2
answers
79
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 ...
- 397
2
votes
2
answers
126
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 ...
- 227
2
votes
1
answer
60
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 ...
- 227
7
votes
2
answers
232
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 ...
7
votes
1
answer
308
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 $...
- 359
1
vote
1
answer
51
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 ...
- 359
3
votes
1
answer
100
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,013
2
votes
1
answer
813
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 ...
- 341
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>$...
3
votes
1
answer
86
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 ...
- 71
0
votes
0
answers
29
views
Bound on scaling mixed quantum-classical computer designs
I am familiar with some basics of quantum computation and this makes me wonder, are there any upper bounds known on the size of a quantum circuit, such that quantum circuit + some classical circuit, ...
- 101
3
votes
1
answer
220
views
What is "Fixed-Point" in the Fixed-Point quantum search?
One of the most famous quantum algorithms is the quantum search, which is given an oracle, $U$ with elements along the diagonal. One element in $U$ is $-1$, and the rest are $1$ (along the diagonal) ...
- 359
1
vote
0
answers
51
views
Time Complexity (Big O Notation)
What is the time complexity of the two error-mitigation methods that are implemented in qiskit.ignis.
1- pseudo inverse.
2- least squares.
2
votes
1
answer
85
views
How VQE is scalable if the dimension of the Pauli basis of the given Hamiltonian grows exponentially with the number of qubits?
For a given Hamiltonian operator $H$, It's possible to approximate its smallest eigenvalue using VQE. Any Hamiltonian is a Hermitian operator. Therefore, for a system with $n$ qubits, the set $S$ of ...
- 1,624
1
vote
2
answers
76
views
Computing $e^{i\phi Z}$ in polynomial time
A lot of papers and algorithms make use of phase shift unitaries such as $\exp(i \phi Z)$ (see, e.g., Quantum Fourier Transform). But is that really a thing that you can compute in polynomial time? I ...
- 327
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
2
votes
1
answer
103
views
Padding a quantum circuit to increase the amplitude by a constant
Let us be given the description of a quantum circuit $\mathsf{Q}$, acting on $n$ qubits, such that
\begin{equation}
\langle 0^n|\mathsf{Q}|0^n\rangle = \frac{\#0_f - \#1_f}{\sqrt{2^n}},
\end{equation}...
- 315
1
vote
0
answers
29
views
Alternate proof to the witness-preserving amplification theorem for QMA
The most familiar witness-preserving amplification for QMA is based on Jordan's lemma and uses the projections $\Pi_1$ and $\Pi_2$ where $\Pi_1$ is he projection on the 'ancilla zero' space, and $\...
- 179
4
votes
1
answer
66
views
Why the "Close Images" problem is QIP-complete
The following problem is known as the "close images" problem:
the input is two circuits $Q_0$, $!_1$, with the same number of input
and output qubits (The circuits are allowed to add ancilla ...
- 179
1
vote
0
answers
56
views
Definition of promise problems with growth conditions
I will preface this by saying that I am a physicist, so I suspect that there are some basic misunderstandings about computer science terminology here which I hope can be clarified.
A typical ...
- 111
4
votes
1
answer
150
views
How Grover's algorithm retrieves a value from an unsorted list in $O(\sqrt{N})$ steps, if the iterator is consisted of more than $O(1)$ steps?
First, I would like to state that I went through many excellent sources of information (among them - Grover's original paper, several QCSE posts like 1 2, and many more sources) - And yet I couldn't ...
- 1,624
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
3
votes
2
answers
122
views
Does having infinitely many quantum gates helpful in solving problems in any ways
A general classical gate accepting $m$ inputs and producing $m$ outputs has total $2^{2^m}$ number gates (which may or may not have names.) Thus number of gates functions are finite.
But QC allows to ...
- 251
0
votes
1
answer
153
views
Size of the "physical" Hilbert space for non-local Hamiltonians?
In their 2011 paper, D. Poulin and coauthors show that the size of "physically" accessible states in Hilbert space for local Hamiltonians is much, much smaller than the total Hilbert space. ...
- 406
1
vote
2
answers
49
views
What is the difference between the complexity $O$-notation?
For a rank $r,d\times d$ density matrix $\rho$, where $d=2^n$, using $O(rdlog^2d)$ measurement settings can reconstruct the density matrix, while I see another description that we need $\Omega(rd\ \...
- 457
0
votes
1
answer
142
views
Computational cost of a circuit in Qiskit
I would like to see, in terms of complexity, the cost of a circuit. For example: I have written two algorithm that does the same thing, but in one of them I initialize data differently, so I would ...
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
2
votes
0
answers
35
views
Is there a known class of problems that a classical computer can theoretically solve using fewer steps and same/smaller memory resources than quantum? [duplicate]
It is my understanding that probabilistic classical computing can be simulated efficiently (using same order of steps) as quantum computing. However, is anything known about the existence of problems ...
3
votes
1
answer
110
views
Can a polynomial-sized superposition of computational basis states be prepared with a polynomial-sized quantum circuit?
Suppose I am working with a class of states which consist of a superposition of $O(\text{poly}(N))$ computational basis states on $N$ qubits. Examples of this would be the subspace of states of fixed ...
- 411
2
votes
3
answers
285
views
Definitions of a quantum circuit's depth and connectivity
The quantum circuit model of computation uses wires and gates. The information flows along the wires and gates attached to the wires modify the information and pass it further down the wires.
In ...
- 2,182
0
votes
0
answers
19
views
determine degree of boolean polynomial given as black box
I searched a lot but couldn't find a good resource that addresses this question. Given a boolean polynomial with $n$ boolean variables as a black box, what is the most efficient way to compute its ...
