Questions tagged [complexity-theory]
For questions regarding complexity analysis of quantum algorithms and comparisons with complexities of classical algorithms.
242
questions
10
votes
2
answers
644
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 ...
- 167
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 ...
- 87
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 $...
- 187
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....
- 187
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 ...
- 179
2
votes
2
answers
88
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 ...
- 187
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 ...
- 187
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
225
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 ...
- 327
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}
...
- 71
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}...
- 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
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 ...
- 251
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. ...
- 381
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 ...
- 237
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
79
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 ...
- 51
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 ...
- 411
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 ...
- 101
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 ...
- 1,380
3
votes
1
answer
235
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 ...
- 95
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
258
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
361
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-...
- 463
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 ...
- 71
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 ...
- 1,383
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, ...
- 315
-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
207
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?
...
- 71