As of May 31, 2023, we have updated our Code of Conduct.

# Questions tagged [complexity-theory]

For questions regarding complexity analysis of quantum algorithms and comparisons with complexities of classical algorithms.

256 questions
Filter by
Sorted by
Tagged with
1 vote
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 ...
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 ...
1 vote
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 ...
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 ?
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$. ...
1 vote
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 ...
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 ...
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 ... 1 vote
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 ...
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 ...
1 vote
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 ...
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 ...
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 ...
1 vote
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 ...
1 vote
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 ...
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 ...
1 vote
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 ...
77 views

1 vote
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 ...
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 ...
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 ...
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>$...
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 ...
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, ...
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) ...
1 vote
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.
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 vote
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 ...
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} ...
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}...
1 vote
29 views

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 ...
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 ...
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 ...
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 ...
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 ...