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
0answers
188 views
+50

Quantum algorithms for Prolog or automated theorem proving?

Are there quantum algorithms for Prolog (SLD resolution - unification and depth-first-search) or for automated theorem proving in general (negation, resolution, and SAT)? Usually automated theorem ...
2
votes
1answer
59 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 ...
2
votes
0answers
48 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?
5
votes
0answers
91 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 ...
9
votes
1answer
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.
7
votes
2answers
4k views

Will quantum computers be able to solve the game of chess?

Will it be possible to use quantum computing to one day solve the game of chess? If so, any estimate as to how many qubits it would require? The game of checkers has already been solved through back ...
5
votes
1answer
159 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 ...
7
votes
3answers
693 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 ...
5
votes
2answers
328 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
0answers
47 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 ...
4
votes
0answers
39 views

Complexity analysis of separability in the multipartite case

It's well known that determining whether a bipartite mixed state is separable or entangled is a $\mathsf{NP}$-hard problem under some accuracy estimates (cf. this TCS SE discussion). Now I'm curious ...
2
votes
1answer
65 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 ...
1
vote
1answer
44 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 ...
2
votes
1answer
29 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?
7
votes
2answers
149 views

Upper Bounds for QMA Quantum Merlin Arthur, and QMA(k)

QMA (Quantum Merlin Arthur), is the quantum analog of NP, and QMA(k) is the class with $k$ Merlins. These are important classes when studying Quantum Complexity theory. QMA(k) is QMA with $k$ ...
5
votes
1answer
119 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$-...
5
votes
1answer
132 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 ...
6
votes
1answer
94 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 ...
3
votes
2answers
212 views

Hilbert space to accurately represent 3x3 Rubik's Cube

What Hilbert space of dimension greater than 4.3e19 would be most convenient for working with the Rubik's Cube verse one qudit? The cardinality of the Rubik's Cube group is given by: Examples 66 ...
4
votes
0answers
37 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 ...
2
votes
2answers
73 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 ...
2
votes
1answer
36 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 ...
2
votes
0answers
89 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
89 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 ...
10
votes
0answers
264 views

Relation between quantum entanglement and quantum state complexity

Both quantum entanglement and quantum state complexity are important in quantum information processing. They are usually highly correlated, i.e., roughly a state with a higher entanglement corresponds ...
1
vote
1answer
35 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 ...
4
votes
1answer
310 views

CTCs and information time travel — what non-trivial insights do they lead to?

Context: In quantum complexity theory and quantum information, there are several papers which study the implications of closed timelike curves (CTCs). In 2008, Aaronson and Watrous published their ...
6
votes
0answers
70 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
88 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 ...
4
votes
1answer
155 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 ...
5
votes
0answers
40 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-...
7
votes
2answers
233 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 ...
3
votes
0answers
44 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
43 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 ...
1
vote
0answers
41 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?
3
votes
1answer
49 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
64 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 ...
1
vote
1answer
45 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,...
2
votes
0answers
26 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, ...
1
vote
1answer
58 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
1answer
93 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)?
36
votes
2answers
5k views

How is the oracle in Grover's search algorithm implemented?

Grover's search algorithm provides a provable quadratic speed-up for unsorted database search. The algorithm is usually expressed by the following quantum circuit: In most representations, a crucial ...
2
votes
0answers
50 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
101 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
88 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
53 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 ...
18
votes
1answer
1k views

Is there a list of accessible open problems in quantum computing from a theoretical computer science perspective?

(Classical) theoretical computer science (TCS) has a number of outstanding open problems that can easily be instantiated in a manner that is accessible to a wider general public. For example, ...
4
votes
1answer
114 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
47 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
116 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 ...