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
0
votes
1answer
17 views

Comparing complexity of digital and analog quantum computation

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 ...
2
votes
0answers
82 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 ...
4
votes
2answers
82 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
vote
1answer
26 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 ...
6
votes
0answers
66 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 ...
2
votes
2answers
61 views

Why is depth complexity revelant?

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 ...
5
votes
0answers
37 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-...
4
votes
1answer
152 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 ...
3
votes
0answers
40 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 ...
3
votes
0answers
35 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
2answers
197 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 ...
1
vote
0answers
37 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?
1
vote
1answer
61 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 ...
2
votes
0answers
25 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, ...
3
votes
1answer
44 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
vote
1answer
43 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,...
1
vote
1answer
54 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....
2
votes
0answers
44 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 ...
4
votes
2answers
96 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 ...
2
votes
0answers
82 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 ...
2
votes
1answer
51 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 ...
5
votes
1answer
133 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 ...
4
votes
1answer
82 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 ...
1
vote
1answer
46 views

Worst Case Asymptotic Complexity of Berstein-Vazirani

How would one determine the worst-case asymptotic complexity ($\theta$) of a Bernstein-Vazirani circuit encoding the secret 1111?
6
votes
1answer
101 views

Is the complexity of a quantum circuit constant in the depth of the circuit?

Take a quantum circuit on $n$ qubits, you have some sequence of gates. You can represent these gates as hermitian matrices, and then with some padding, you could take the product of these matrices, by ...
2
votes
1answer
85 views

How do I construct the oracle for a general Bernstein-Vazirani circuit?

Say I have a secret of length $n$, $s = |x_{n-1}x_{n-2}...x_0 \rangle$. If I want to construct an oracle for this problem would I just insert a CNOT gate on every qubit where the secret's value is 1? ...
2
votes
2answers
109 views

Estimating output amplitudes of quantum circuits as GapP functions

Let's fix a universal gate set comprising of a Hadamard gate and a Toffoli gate. Consider an $n$ qubit quantum circuit $U_{x}$, made up of gates from that universal set, applied to initial state $|0^{...
4
votes
1answer
41 views

Degree of $N$-bit Majority function is larger or equal to $N/2$

I am looking to prove that the $N$-bit Majority function $f$, which is 1 if its input $x \in \{0, 1\}^N$ has Hamming weight $> N/2$, and 0 if its input has Hamming weight $\leq N/2$ has degree $\...
2
votes
1answer
100 views

Quantum hardness of XQUATH conjecture

Consider the XQUATH conjectures, as defined here (https://arxiv.org/abs/1910.12085, Definition 1). (XQUATH, or Linear Cross-Entropy Quantum Threshold Assumption). There is no polynomial-time ...
11
votes
3answers
1k views

Are spin-glass problems NP (-complete)?

It is well known that finding ground states for spin-glass systems (Ising, XY...) is NP-hard (at least as hard as the hardest NP-problems) so that they can be efficiently used to solve other NP ...
2
votes
1answer
97 views

Complexity of Quantum Satisfiability vs Local Hamiltonians

$k$QSAT$c$ is the promise problem where the input, given in an explicit encoding with finite number of bits, is a set $\{p_{1},p_{2},\ldots p_{m}\}$ of $k$-local projectors over a $n$-qbits register, ...
1
vote
1answer
61 views

The complexity of LH restricted to projectors

Let's denote $kLP_{c}$ the promise problem where the input, given in an explicit encoding with finite number of bits, is a set $\{p_{1},p_{2},\ldots p_{m}\}$ of k-local projectors over a n-qbits ...
6
votes
1answer
142 views

How is a promise gap related to a spectral gap?

In linear algebra one often concerns oneself with the spectral gap of a given matrix, which may be defined as the difference between the smallest and second-smallest eigenvalue (or, depending on ...
4
votes
2answers
144 views

The complexity of LH with constant gap

Kitaev's quantum equivalent of the Cook-Levin Theorem, provides a polynomial time classical reduction from a QMA verification circuit to a sum $H$ of local hamiltonians, such that the least eigenvalue ...
3
votes
1answer
99 views

How would I theorise a quantum query algorithm in O(1)?

I am currently attempting to solve a problem from Nielsen-Chuang, and I can't seem to figure out how I would do this; I'm trying to implement Grover's algorithm to solve the problem of differentiating ...
2
votes
1answer
582 views

Can quantum computer solve NP-complete problems? [duplicate]

As far as I know, quantum computers are able to solve only some of the NP-Problems in polynomial time, using the Grovers algorithm. I read that if one manages to create a reduction of Grovers ...
7
votes
1answer
314 views

Classical algorithm with complexity similar to Shor's discovered: Are there more efficient quantum algorithms than Shor's?

In the article Fast Factoring Integers by SVP Algorithms the author claims that he discovered classical algorithm for factoring integers in polynomial time. The Quantum Report mentioned here that it ...
1
vote
1answer
54 views

What does “large-scale universal quantum computation” mean?

I was reading this lecture notes by Sevag Gharibian. He mentioned the following statement: Large-scale universal quantum computer can be built. I do understand what quantum computer is, but I don't ...
2
votes
1answer
87 views

How do I calculate the number of uses of a unitary $U$ in iterative phase estimation?

How would one go along to calculate the number of uses of an unitary $U$ in Iterative Phase Estimation (IPE) to compare it to the number of uses of $U$ in standard Phase Estimation (Qiskit QPE)?
8
votes
2answers
143 views

Why does QAOA achieve quantum supremacy in an algorithmic sense?

In the paper Quantum Supremacy through the Quantum Approximate Optimization Algorithm the authors claim (last sentence of page 15): "If [...] the QAOA outperforms all known classical algorithms ...
6
votes
1answer
35 views

List of problems in the query complexity model with no super-polynomial quantum speedup

Similar to this list over at cstheory, I'm looking for a list of computational problems in the query complexity model for which it is known that no super-polynomial quantum speedups exist. What are ...
4
votes
0answers
64 views

Properties of QAOA

The QAOA algorithm consists of two elements: The outer loop, basically a classical optimization algorithm The quantum circuit, taking $2p$ parameters (where $p$ is the number of layers, where each ...
6
votes
2answers
101 views

What is the computational complexity of quantum annealing?

Quantum annealing can be thought of as a black box solver that can find approximate solutions to hard optimization problems. For example, D-Wave quantum annealers can approximately solve quadratic ...
4
votes
2answers
169 views

CS conjecture that Quantum Computer cannot solve NP-complete problems, but Boson Samplers do a #P-hard problem. How is it?

There is something very strange and absurd for me about the power of a quantum computer. Let me briefly states the following facts: Fact 1: theoretical computer scientists believe (very likely to ...
3
votes
0answers
32 views

What is the computational complexity of approximate quantum adders, in terms of big O notation?

I have recently found papers on approximate quantum adders. However, the papers do not seem to mention the computational complexities of their algorithms. What are their complexities, in terms of big ...
6
votes
1answer
134 views

Are almost-Clifford circuits almost easy to simulate?

Circuits consisting entirely of Clifford operations in $\{X, Y, Z, H, S, \text{CNOT} \}$ are "easy" to simulate classically since there is a method that can fully compute such circuits over $...
3
votes
2answers
826 views

Do there exist problems known to be computationally intractable for quantum computer, but tractable for classical computer?

Or alternatively phrased, is it believed that the complexity class P is a complete subset of BQP? Consider the following diagram à la MIT OpenCourseWare, which seems to explicitly state as much.
8
votes
0answers
136 views

What is stopping FACTORING from being BQP-complete?

Classical complexity theory makes much of the study of so-called intermediate problems - that is, problems that are in $\mathsf{NP}$ but are nonetheless not known to be in $\mathsf{P}$ and further not ...
7
votes
2answers
179 views

What kind of boolean functions are faster to compute on qc?

Deutsch-Jozsa algorithm can compute if some function $f : \{0,1\}^n \rightarrow \{0,1\} $ is constant. This goes exponentially faster than on classical computers. If we consider the set of all boolean ...
4
votes
0answers
58 views

Complexity of controlled operations in a two-level unitary operation

In Neilsen and Chuang, chapter 4.5.2 (~p.193), why did the authors come to the conclusion that complexity of operations $C^n(X)$ and $C^n(\tilde{U})$ is $O(n)$? Did they assume using work qubits? If ...