Questions tagged [complexity-theory]
For questions regarding complexity analysis of quantum algorithms and comparisons with complexities of classical algorithms.
255
questions
9
votes
2
answers
297
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,142
3
votes
1
answer
265
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
317
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
103
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
86
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
286
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
428
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
93
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
91
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,425
2
votes
0
answers
64
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
67
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
228
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,347
5
votes
1
answer
196
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
4
votes
0
answers
116
views
Is the exponential speedup and output $\langle x|M|x\rangle$ in contradiction in HHL algorithm?
Isn't the exponential speedup and the output $\langle x|M|x\rangle$ in contradiction in HHL algorithm? How can we print the solution vector $|x\rangle$ without losing the exponential speedup?
- 51
4
votes
1
answer
267
views
How to theoretically compare the complexity of quantum and classical algorithms?
I am working on reducing an NP class problem to a QUBO so can be solved with QAOA. I know that there is not a practical way to compare the performance as there is no QPU with enough qubits. I am doing ...
- 81
6
votes
1
answer
175
views
Complexity of a distribution of measurement of output of quantum circuit
The Kolmogorov complexity of a string refers to a deterministic object. Here, I refer to the analogous "complexity of a distribution", or better, to the complexity of sampling from a ...
- 463
9
votes
1
answer
1k
views
Can a quantum computer tell whether a program is Turing complete?
I am very new to quantum computing and would like to know if a quantum computer can decide whether a given program is Turing complete.
- 101
10
votes
3
answers
1k
views
Quantum advantage with only Clifford gates (Gottesman Knill theorem)
Let's say I want to solve a computational task which input can be encoded in $n$ bits of information.
The look for a quantum advantage is (usually) asking to find a quantum algorithm in which there ...
- 1,142
5
votes
2
answers
419
views
What is the computational complexity in initializing a quantum register?
I'm trying to figure out what is the computational complexity of initializing a quantum register of N qubits.
For my research, I have used the initialize method of qiskit, in which you set the ...
3
votes
0
answers
62
views
Could quantum computers answer the question of whether QCD predicts quark gluon confinement?
As I understand it, it is not known whether or not QCD actually predicts quark gluon confinement.
As I understand it answering questions in quantum field theories is generally harder in terms of ...
- 143
2
votes
1
answer
124
views
What is quantum advantage truly?
Let's consider the Deutsch Jozsa algorithm, I understand that the superposition principle in quantum mechanics, helps us design circuits which would give answers in one single query. But then I would ...
- 203
1
vote
1
answer
57
views
References about deriving the complexity of a given algorithm
Trying to learn about how to derive (& intuition) the complexity for a given algorithm as shown below.
If there is any good reference or starting point that anyone can suggest that will be highly ...
- 981
2
votes
1
answer
43
views
Is quantum query complexity equivalent to the total number of calls to the quantum computer for any given algorithm?
In other words, if an algorithm requires N total calls to the quantum computer to find the solution (of any given problem), would N be equivalent to its query complexity?
- 21
5
votes
1
answer
168
views
How powerful are boundedly many $T$-gates?
For a natural number $k$ (0 is a natural number), let $T_k$ be the collection of all languages that can be efficiently decided by quantum circuits consisting of Clifford gates and at most $k$ $T$-...
- 227
5
votes
1
answer
317
views
BHT algorithm implementation
Summary of Method
Amplitude Amplification Summary
The BHT algorithm uses amplitude amplification, a nice generalisation of Grover's algorithm, where there is a subset $G\subset X$ of good elements in ...
- 183
5
votes
0
answers
54
views
Proving that with probability 1 $NP \nsubseteq BQP$ with respect to random oracles
In the paper Strength and Weakneses of Quantum Computers (https://arxiv.org/abs/quant-ph/9701001) by Bennet, Bernstein, Brassard and Vazirani, it is shown the statement in the title (Theorem 3.5 in ...
- 533
3
votes
2
answers
144
views
How come classical Deutsch-Jozsa is $O(1)$ when allowing "a small error rate"?
I'm reading Quantum Computing: An Applied Approach, by Hidary. Chapter 8.2 (p104) says:
While it is true that Deutsch-Jozsa demonstrates an advantage of quantum over classical computing, if we allow ...
- 5,078
3
votes
1
answer
88
views
Comparing complexity of digital and analog quantum computation
The complexity of an algorithm run on a digital quantum computer is quantified, roughly, by the number of elementary gates in the corresponding circuit. Can one similarly quantify the complexity of an ...
- 1,425
2
votes
0
answers
180
views
Is there an efficient quantum circuit that create a random permuntation matrix?
Suppose we want to generate a random, random according to some probability distribution, unitary permutation matrix that is applied to an input of $n$ qubits. So is there an efficient polynomial time ...
- 65
4
votes
2
answers
155
views
Are all computational resources reducible to the time resource?
It's well known that in most (if not all?) computations you can trade time and space resources. An extreme example might be creating an infinitely large lookup table of all composites produced from ...
- 1,036
1
vote
1
answer
262
views
Would quantum computers be more efficient at solving circular reference problems than classical computers?
A circular reference is when a certain value either refers to itself or a value refers to a value that refers to it. An example of a circular reference problem would be $x=f(x)$. One way to solve ...
- 143
6
votes
0
answers
85
views
Postselection and hardness of estimating amplitudes
Let $A$ be a class of quantum circuits such that
\begin{equation}
\text{Post}A = \text{Post}BQP,
\end{equation}
where $\text{Post}$ indicates post-selection. Is only this amount of information ...
- 1,119
7
votes
2
answers
352
views
Why is depth complexity relevant?
Since gate complexity correspond to the number of gate for a given quantum circuit, it seems that depth complexity bring no more information about quantum complexity than gate complexity. So does gate ...
- 95
7
votes
0
answers
58
views
Is there a practical architecture-independent benchmark suitable for adversarial proof of quantum supremacy?
Recent quantum supremacy claims rely, among other things, on extrapolation, which motivates the question in the title, where the word "adversarial" is added to exclude such extrapolation-...
- 326
4
votes
1
answer
174
views
Spoofing XQUATH with the Feynman method
Consider the XQUATH conjecture for random quantum circuits, as mentioned here.
(XQUATH, or Linear Cross-Entropy Quantum Threshold Assumption). There
is no polynomial-time classical algorithm that ...
- 1,119
3
votes
0
answers
56
views
Feynman method and polynomial time algorithm for XQUATH
Consider the Feynman algorithm for simulating quantum circuits, as given here.
Consider the XQUATH conjecture for random quantum circuits from here, given by
(XQUATH, or Linear Cross-Entropy Quantum ...
- 1,119
3
votes
0
answers
54
views
Query complexity on Quantum Pattern Matching of Mateus Algorithm
I am trying to understand the complexity of the Mateus and Omar algorithm for quantum pattern matching, it is clear to me from the pseudocode that the query complexity is $O(\sqrt{N})$, apart from the ...
7
votes
2
answers
414
views
Complexity of $n$-Toffoli with phase difference
I'm interested in the $n$-Toffoli gates with phase differences. I found a quadratic technique in section 7.2 of this paper.
Here's the front page of the paper.
Here's an image of the section that I'm ...
- 101
1
vote
0
answers
70
views
Why is sampling considered difficult on a classical computer but easy on a quantum computer? [closed]
It is my understanding that classical computers have a hard time sampling results from an output from a quantum circuit, but quantum computers find it very easy to do so. Why is this?
- 137
1
vote
1
answer
86
views
What are the types of models of computation aside from the quantum query model?
It looks like in a lot of quantum algorithms, we use the quantum query model. I wanted to know what are the other types of models of computation, used in quantum computing as well as in classical ...
- 23
2
votes
0
answers
32
views
What constitutes generic dynamics, and how is it different from a fully random function?
What constitutes generic dynamics? And how is it different from a fully random function?
From what I understand, a fully random function is one that is "Haar" random. And generic dynamics, ...
- 100
3
votes
1
answer
92
views
Learning k positions of a Boolean function with a quantum computer
Consider a Boolean function with multiple outputs $f: \{0, 1\}^{n} \rightarrow \{0, 1\}^{m}$, and consider being given oracle access to the function $f$. Let us denote the oracle by $O_f$. For an $x \...
- 1,119
1
vote
1
answer
82
views
What is the counting argument for the number of elementary operations required for a random function?
What is the counting argument for the following statement (classical)?
"A random function on n bits requires $e^{\Omega(n)}$ elementary operations."
It appears in the introduction of PRL 116,...
- 100
1
vote
1
answer
74
views
Accessing parameter in oracle and their relation
I am actually a newbie in quantum computing. I do have some doubts regarding quantum query complexity.
From what I understood is that we can't explicitly give the input and use oracle for this purpose....
- 23
2
votes
0
answers
111
views
Relation between approximate counting and sampling
Consider the following statement of Stockmeyer counting theorem.
Given as input a function $f:\{0, 1\}^{n} \rightarrow \{0, 1\}^{m}$
and $y \in \{0, 1\}^{m}$, there is a procedure that runs in ...
- 1,119
4
votes
2
answers
145
views
Can the difference between quantum and classical circuits be attributed to different paths in the Hilbert space?
One of the explanations I have encountered for why quantum computation can provide speed-up over the classical is a picture that in the Hilbert space much more paths are allowed quantum-mechanically ...
- 1,425
2
votes
0
answers
148
views
When is a Quantum Computer Slower Than a Classical Computer?
Someone offhandedly mentioned to me that quantum computers are sometimes significantly (I guess they meant asymptotically) slower than classical computers.
Unfortunately, I didn't get any arguments ...
- 121
2
votes
1
answer
64
views
Is there a quantum implementation like HashSet?
There are many data structures in classical computers, like Tree, HashSet, etc. These data structures give convenience to the performance (time complexity) of algorithms. I am wondering how to create ...
- 315
5
votes
1
answer
230
views
How can one cheat in Mahadev's classical verification protocol if one can find a "claw''?
I was going through the seminal paper of Urmila Mahadev on Classical Verification of Quantum Computations(for an overview see this excellent talk by her). As a physicist by training, I am not very ...
- 221
5
votes
1
answer
320
views
What is the quantum query complexity of the period finding routine of Shor's algorithm?
It seems like it should be a function of N - O(log N), to minimise probability of getting a multiple of the period. However, Prof Preskill's lec notes mention:
Thus we solve Period Finding if the ...
- 83