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
2 votes
0 answers
13 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
0 answers
51 views
+100

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
20 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
55 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
42 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
3 votes
1 answer
81 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,237
5 votes
0 answers
76 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 ...
  • 1,997
3 votes
2 answers
102 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 ...
1 vote
1 answer
79 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
43 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\ \...
  • 359
0 votes
1 answer
49 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
29 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
59 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
77 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
132 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 ...
  • 1,161
0 votes
0 answers
15 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 ...
0 votes
0 answers
16 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 ...
8 votes
2 answers
252 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
99 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
167 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?
  • 388
1 vote
0 answers
77 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 ...
  • 388
3 votes
1 answer
53 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 ...
  • 388
6 votes
2 answers
175 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
291 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
87 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
80 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
51 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
50 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
156 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,107
5 votes
1 answer
165 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? ...
4 votes
0 answers
107 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
135 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
126 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
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.
9 votes
3 answers
889 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
2 answers
372 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
54 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 ...
2 votes
1 answer
83 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
53 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
1 answer
35 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?
5 votes
1 answer
146 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
206 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 ...
4 votes
0 answers
47 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 ...
  • 493
2 votes
2 answers
107 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 ...
  • 4,254
2 votes
1 answer
63 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
0 answers
132 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 ...
  • 55
4 votes
2 answers
128 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
256 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
0 answers
79 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
2 3 4 5