Skip to main content

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
1 answer
51 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 ...
MonteNero's user avatar
  • 2,684
0 votes
0 answers
29 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 ...
Join the party P.A.R.T.Y.'s user avatar
3 votes
3 answers
304 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 ...
Josh's user avatar
  • 407
1 vote
0 answers
22 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 ...
Pole_Star's user avatar
  • 111
4 votes
0 answers
45 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 ...
Dudu Ponar's user avatar
2 votes
1 answer
86 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 ...
BlackHat18's user avatar
  • 1,363
0 votes
0 answers
35 views

Derivation of complexity for data encoding schemes

Could anyone help to derive the space-time complexities of the following different data encoding schemes ?
kevin's user avatar
  • 7
6 votes
1 answer
196 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$. ...
Andrew Baker's user avatar
1 vote
1 answer
430 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 ...
Curious's user avatar
  • 259
3 votes
1 answer
99 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 ...
user avatar
2 votes
0 answers
156 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 ...
IsalanOnkar's user avatar
5 votes
0 answers
81 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 ...
greilchri's user avatar
1 vote
0 answers
44 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 ...
Alexey Uvarov's user avatar
2 votes
0 answers
62 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 ...
Loic Stoic's user avatar
3 votes
0 answers
37 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 ...
Loic Stoic's user avatar
1 vote
1 answer
97 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 ...
Loic Stoic's user avatar
1 vote
0 answers
28 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 ...
Loic Stoic's user avatar
11 votes
2 answers
774 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 ...
Loic Stoic's user avatar
1 vote
1 answer
53 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 ...
TwentyCents's user avatar
8 votes
1 answer
176 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 $...
Andrew Baker's user avatar
6 votes
1 answer
545 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....
Andrew Baker's user avatar
2 votes
2 answers
89 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 ...
trillianhaze's user avatar
2 votes
2 answers
823 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 ...
Andrew Baker's user avatar
2 votes
1 answer
76 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 ...
Andrew Baker's user avatar
9 votes
2 answers
334 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 ...
Pierre Yves Schobbens's user avatar
8 votes
1 answer
833 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 $...
wavosa's user avatar
  • 399
1 vote
1 answer
152 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 ...
wavosa's user avatar
  • 399
4 votes
1 answer
234 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 ...
Mauricio's user avatar
  • 2,346
2 votes
1 answer
868 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 ...
Josh's user avatar
  • 407
2 votes
0 answers
107 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>$...
Михаил Горчаков's user avatar
4 votes
1 answer
201 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 ...
lm1909's user avatar
  • 93
1 vote
0 answers
38 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, ...
Ilk's user avatar
  • 111
4 votes
1 answer
529 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) ...
wavosa's user avatar
  • 399
1 vote
0 answers
61 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.
rabah hacene benaissa's user avatar
2 votes
1 answer
173 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 ...
Ohad's user avatar
  • 1,759
1 vote
2 answers
82 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 ...
NYG's user avatar
  • 399
5 votes
0 answers
107 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} ...
Chaithanya's user avatar
2 votes
1 answer
137 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}...
Tom Clancy's user avatar
1 vote
0 answers
46 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 $\...
omerna's user avatar
  • 189
4 votes
1 answer
85 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 ...
omerna's user avatar
  • 189
1 vote
0 answers
65 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 ...
EuYu's user avatar
  • 111
4 votes
1 answer
243 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 ...
Ohad's user avatar
  • 1,759
5 votes
0 answers
104 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 ...
R.W's user avatar
  • 2,357
3 votes
2 answers
156 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 ...
RSW's user avatar
  • 289
0 votes
2 answers
277 views

What is 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 exponentially smaller than the total Hilbert ...
Dr. T. Q. Bit's user avatar
1 vote
2 answers
53 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\ \...
karry's user avatar
  • 629
0 votes
1 answer
331 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 ...
DYLAN NICO AMBROSI's user avatar
4 votes
0 answers
37 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 ...
bubakazouba's user avatar
2 votes
0 answers
44 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 ...
quantum novice's user avatar
3 votes
1 answer
133 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 ...
Solarflare0's user avatar

1
2
3 4 5
7