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
10 votes
2 answers
652 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
1 answer
27 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 ...
5 votes
1 answer
51 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 $...
6 votes
1 answer
451 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....
2 votes
2 answers
77 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 ...
2 votes
2 answers
89 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 ...
2 votes
1 answer
53 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 ...
6 votes
2 answers
211 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
226 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 $...
  • 315
1 vote
1 answer
45 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 ...
  • 315
3 votes
1 answer
95 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 ...
  • 1,983
2 votes
1 answer
797 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 ...
  • 255
2 votes
0 answers
41 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
66 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
184 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) ...
  • 315
1 vote
0 answers
48 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
79 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,604
1 vote
2 answers
75 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 ...
5 votes
0 answers
99 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} ...
2 votes
1 answer
98 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
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
65 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
55 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
125 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,604
5 votes
0 answers
86 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,224
3 votes
2 answers
119 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 ...
0 votes
1 answer
135 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. ...
1 vote
2 answers
47 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\ \...
  • 437
0 votes
1 answer
111 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 ...
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 ...
0 votes
1 answer
81 views

Generalized Diffusion Operator

Consider a variant of the SAT problem when for a given boolean formula, we would like to find an assignment that is also in the support of a given quantum state. Formally let $ A $ be a set of the ...
3 votes
1 answer
107 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 ...
2 votes
3 answers
256 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,041
0 votes
0 answers
17 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 ...
1 vote
0 answers
24 views

Computational Complexity of random Transverse-Ising Chain

It is well known that many NP-hard classical problems can be mapped to a spin-configuration Ising problem (see for example https://arxiv.org/pdf/1302.5843.pdf) However, what I would like to know is ...
9 votes
2 answers
289 views

A rigorous definition for an exponential quantum advantage

Let's assume that we have an algorithmic problem to solve. This problem takes an integer $n$ as input to describe it and provides as output a bit string providing the answer we are expecting. For some ...
3 votes
1 answer
236 views

O(N log(M)) vs O(log(MN)) Complexity Name

I have a quantum system that solves a problem that takes $O(MN)$ on a classical computer. However, because it is solved using a quantum algorithm, it takes $O(\log(MN))$. I also have another algorithm ...
2 votes
0 answers
269 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
1 vote
0 answers
100 views

How to estimate the complexity of a variational quantum circuit?

How to estimate the complexity of a variational quantum circuit? For example, I have a quantum circuit of $n$ qubits that uses alternating operators to build the network and train it. So what is the ...
  • 390
3 votes
1 answer
73 views

Do quantum algorithms and classical algorithms of the same complexity have the same time consumption?

The classical computer field likes to use the complexity O(x) to represent the complexity of an algorithm. Is this concept applicable to quantum computers, if quantum algorithm A with the same ...
  • 390
6 votes
2 answers
259 views

How can I show that $\mathsf{QMA}\subseteq \mathsf{PSPACE}$

Lately I have seen the claim that $\mathsf{QMA}\subseteq \mathsf{PSPACE}$, and I wonder how can it be proved. Thanks
  • 179
6 votes
1 answer
362 views

What is the complexity of hidden subgroup problems?

It is often stated that some of the "hidden subgroup problems" can be efficiently solved by quantum computers if the group is abelian, while no efficient algorithm is known for the non-...
0 votes
1 answer
91 views

To what class of complexity theory a problem for whom I can’t check the solution, ever, belong?

Let’s say I have a problem that can only be solved with a trapdoor, but regardless of whether the trapdoor is right or wrong, you can’t check if you have found the solution to the problem. To what ...
3 votes
0 answers
89 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 ...
2 votes
0 answers
61 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, ...
-1 votes
1 answer
64 views

What time complexity is considered difficult for quantum computers? [closed]

Not space complexity this time. Just want to know the limitations of its performance
  • 1
6 votes
1 answer
208 views

What is the relationship between the size of the Hilbert space for boson sampling and the complexity of classical simulating it?

My intuition is that the fastest classical algorithm for simulating some kind of noiseless quantum sampling process should scale roughly with the dimension of the Hilbert space: you would need to ...
  • 2,317
5 votes
1 answer
192 views

Has the possibility of there being a classical cryptography algorithm able to withstand quantum computing been proven?

Has it been proven, that a classical codec (encoder-decoder) (classical meaning one that doesn't require a quantum system for its operation) is possible, such that a quantum computer cannot crack it? ...

1
2 3 4 5