Skip to main content
Share Your Experience: Take the 2024 Developer Survey

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
3 votes
0 answers
54 views

Are there approximability schemes for NP-Hard problems using quantum algorithms? [duplicate]

I'm looking into some parts of Quantum Complexity Theory and was wondering if we have any approximability schemes for NP-Hard problems using quantum algorithms. I was unable to find any literature on ...
LukasM's user avatar
  • 53
1 vote
0 answers
62 views

Could a quantum walk easily traverse Rush-Hour type puzzles?

I was staring at a Rush-Hour type puzzle recently and I began to wonder if any such puzzles are amenable to a continuous-time quantum walk. The entrance and exit vertex are well-defined; at each stage ...
Mark Spinelli's user avatar
3 votes
0 answers
38 views

Alternative algorithm for quantum phase estimation problem

The Quantum Phase estimation problem is stated below: Input: Given $U$ as a unitary operator acting on an m-qubit register. If $| \psi \rangle$ is an eigenvector of $U$, then U$| \psi\rangle$ = $e^{ ...
Manish Kumar's user avatar
3 votes
1 answer
43 views

What is the "equivalent" quantum computational complexity class of the classical class APX (or PTAS)?

According to Wikipedia, APX contains those optimization problems in NP for which there exists a polynomial time algorithm which approximates the objective function multiplicatively to within a ...
Another User's user avatar
4 votes
1 answer
80 views

Are commuting unitary operators related to commuting Hamiltonians?

TL/DR: Can unitary operators: $$U_a=e^{-it(H_{a1}+H_{a2}+\cdots)}$$ and $$U_b=e^{-it(H_{b1}+H_{b2}+\cdots)}$$ commute, even though $[H_{aj},H_{ak}]\ne 0$ and $[H_{bj},H_{bk}]\ne 0$ for all $j,k$? ...
Mark Spinelli's user avatar
2 votes
1 answer
79 views

What is the promise gap in APPROX-CIRCUIT-VALUE (BQP-complete) problem?

I want to understand how the precision of promise gap on input size changes the problem's difficulty. I read the guided local Hamiltonian problem (GLHP). Description of GLHP: We have been given a ...
Manish Kumar's user avatar
1 vote
1 answer
93 views

Does measurement at the end of all transformations in quantum computing have a specified time?

The concept of measurement in quantum mechanics is usually discussed without specifying how much time such measurement might take. In principle, one can imagine that the time needed to perform ...
quantum novice's user avatar
2 votes
0 answers
64 views

Is BQP contained in BPP with Quantum Phase Estimation (QPE) oracle?

I am trying to see if the below proposition holds: Proposition-1: $BQP\subseteq BPP^{QPE}$. Here, QPE is the Quantum Phase estimation algorithm. QPE takes an eigenstate and the unitary matrix as ...
Manish Kumar's user avatar
2 votes
1 answer
114 views

Non-linear quantum mechanics and NP-complete problems

Thanks to user Cuhrazatee (comments to my other question here) I came accross article Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems by D. Abrams and S. ...
Martin Vesely's user avatar
2 votes
1 answer
48 views

Complexity of controlled-$U^j$ operations in QPE applied to Hamiltonian simulation

One method to obtain the eigenvalues of a Hamiltonian $H$ is by applying quantum phase estimation to its time-evolution operator $U(t) = e^{-iHt}$. If I want to obtain an eigenvalue to $k$ bits in ...
Solarflare0's user avatar
4 votes
1 answer
70 views

What is an example of a problem that we strongly suspect lies in NP $\cap$ co-NP but not in BQP?

Motivated by the latest lattice crypto paper (no idea if it's correct), I was wondering if there were any out there that thought perhaps NP $\cap$ co-NP was contained in BQP? Or alternatively, if ...
squiggles's user avatar
  • 925
3 votes
1 answer
50 views

Complexity of Variational Quantum Eigensolvers

I am doing research surrounding VQE and am a bit confused about the complexity and its comparison to classical systems. My brief research has yielded me that classical eigenvalue solving is $O(n^3)$. ...
Jonah Sachs's user avatar
2 votes
1 answer
56 views

The time complexity of quantum circuit

I want to figure out how to evaluate the time complexity of a quantum circuit. An simple understanding is that if there are more quantum gates in a quantum circuit. The time complexity is higher. (...
tangyao's user avatar
  • 151
4 votes
2 answers
261 views

Prove that there is no polynomial size quantum algorithm for a Simon's problem with no promise on the input

We look at the following variant of Simon's problem. There is an algorithm $A$ that solves a problem with the following settings: The input is an oracle $f:\{0,1\}^n \to [M]$. The output of the ...
Gabi G's user avatar
  • 229
0 votes
1 answer
102 views

What is the oracle in every quantum algorithm?

There is a machine called oracle which appears in a lot of algorithm of quantum computing, such as Deutsch's algorithm, QFT period-finding. This oracle machine really makes me confused. I've read ...
tangyao's user avatar
  • 151
1 vote
1 answer
166 views

Classical electronics controls from both sides - could we do it for some quantum electronics?

In classical electronics we actively pull and push electrons by electric field - could we get such two-way control for some quantum electronics? For example silicon quantum dots - for state ...
Jarek Duda's user avatar
3 votes
0 answers
64 views

Why FACTORING is in second level of Fourier hierarchy?

As per comlexityzoo web, the definition of the k-th level of Fourier Hierarchy (FH) is: $FH_k$ is the class of problems solvable by a uniform family of polynomial-size quantum circuits, with k levels ...
Manish Kumar's user avatar
4 votes
1 answer
154 views

Requirement of vector 'b' in the definition of Phase Estimation Sampling (PES)

In this paper (last paragraph, page 3) by Wocjan and Zhang, the definition of PES requires vector/bit string b. The phase estimation problem (PE) very much inspires the definition. I cannot ...
Manish Kumar's user avatar
1 vote
1 answer
68 views

How many gates are necessary to implement an arbitrary n-qubit permutation unitary?

How many gates are necessary to implement an arbitrary n-qubit permutation unitary, using only 1- and 2-qubit gates? An n-qubit permutation unitary is a $2^n$ x $2^n$ unitary matrix where each entry ...
QNA's user avatar
  • 181
5 votes
0 answers
112 views

What is the classical cost of simulating an arbitrary quantum state?

The past couple of years has seen various groups claim quantum advantage/utility only to have their experiments efficiently simulated with classical methods, notably using tensor networks. My question ...
jsbaker's user avatar
  • 156
4 votes
3 answers
165 views

What is the definition of an "efficient" algorithm?

Suppose I have an algorithm that prepares a state of $N$ qubits ($N$ variable); I was recently told that the algorithm is called efficient if the depth of the circuit is independent of $N$. However, ...
David Raveh's user avatar
3 votes
1 answer
72 views

Understanding how to solve group isomorphism given the state $\sum_{\pi \in S_n} |\pi(G) \rangle$

Let $G=([n],E)$ be an undirected graph, which is represented by a $n \choose 2$ bit string, by indicating for each $i < j$ if $(i,j) \in E$. And let $| G \rangle$ be the $n \choose 2$ qubit state ...
Gabi G's user avatar
  • 229
4 votes
3 answers
171 views

What is the computational power of classically mixed states?

It is my understanding that mostly one considers as the "classical" state, a single bit string (eg 00101), with a discrete number of deterministic gates applied to it. All computers that ...
Wouter's user avatar
  • 301
3 votes
1 answer
82 views

Does k-fold FORRELATION problem lies in BQP or $BQP^O$

It is known that the Simon Problem lies in $BQP^O$ (oracular problem). Even it proves $\exists O$ $BPP^O\neq BQP^O$. Or It separates the classes in the Oracle/Query model of computation. Meanwhile, ...
Manish Kumar's user avatar
4 votes
1 answer
145 views

Optimal dependency of HHL (or any QLSP) algorithm on condition number $\kappa$

This is conserning the optimal dependency on condition number for Quantum linear system problem (QLSP). For solving QLSP, the HHL (algorithm) paper mentions any polylog($\kappa$) quantum algorihm ...
Manish Kumar's user avatar
7 votes
1 answer
211 views

Anything in between quadratic and exponential speedups?

Question There exist a handful of proven quadratic quantum speedups (some examples include [1-3]) and even a few proven exponential quantum speedups (some examples include [4-6]). But there seems to ...
sheesymcdeezy's user avatar
4 votes
1 answer
90 views

How does the complexity of extracting eigenvalues via quantum phase estimation compare with the classical one?

Suppose, I have ideal quantum computer that allows me to find exact eigenvalues with QPE algorithm under perfect matrix, eigenvectors and eigenvalues conditions. How the complexity of this algorithm ...
Марина Лисниченко's user avatar
1 vote
1 answer
97 views

Ground state energy for commuting local Hamiltonians

I am going through S. Gharibian's course on quantum complexity theory (https://groups.uni-paderborn.de/fg-qi/data/QCT_Masterfile.pdf) and encountered the following problem (Ex 6.39, note that here $\...
user896578's user avatar
2 votes
1 answer
90 views

Does assuming the security of LWE imply $BPP\subset BQP$?

Here's a "proof" for why $BPP\subset BQP$ assuming Learning With Errors (LWE) is postquantum. Consider the Mahadev protocol that uses LWE-based cryptography to verify if an instance $x\in L$ ...
user1936752's user avatar
  • 2,997
1 vote
0 answers
35 views

Proving CLDM is in QMA, In particular why is it possible to assume that the given input is a product of copies in the soundness section?

I'm wondering about a specific proof for Consistency of Local Density Matrices (CLDM) $ \in $ QMA appearing in "QMA-hardness of Consistency of Local Density Matrices with Applications to Quantum ...
Dudu Ponar's user avatar
2 votes
1 answer
149 views

If all terms of a local Hamiltonian commute, how hard is it to learn the ground state (energy)?

Suppose we have a $k$-local Hamiltonian with each of $m$ terms acting on $k$ of $n$ qudits of constant dimension $d$: $$H=H_1+H_2+\cdots+H_m.$$ If at least some of the terms don't commute, e.g., if $[...
Mark Spinelli's user avatar
3 votes
0 answers
72 views

The no fast forwarding theorem and exponential advantage for many body Hamiltonians

When simulating Hamiltonians in first quantization there are $\eta$ particles occupying a grid of $N$ grid points. In the first quantization, you directly discretize the differential operators onto a ...
Cuhrazatee's user avatar
5 votes
2 answers
177 views

Why is it hard to prove complexity bounds for variational algorithms?

I'm not very familiar with variational algorithms, but I've heard people say that they're "heuristic" and it's difficult to measure their performance via complexity analysis. Why is this the ...
confusion's user avatar
  • 155
3 votes
0 answers
87 views

Complexity of the quantum circuits that are needed to implement communication protocol?

Consider the following simultaneous communication problem. Alice and Bob do not share any entanglement or any common randomness, and cannot communicate directly with each other. As inputs, x is given ...
Ruben Hoba's user avatar
2 votes
0 answers
28 views

Why is 3-Coloring in PQMA(2)?

I'm reading https://arxiv.org/abs/0709.0738 about the complexity of PQMA(2) and its relation to NP. It describes a PQMA(2) protocol (3.1) for 3-coloring which contains the following check: For both $|...
benimus's user avatar
  • 21
3 votes
1 answer
129 views

Quantum circuits, quantum Turing machine and universal quantum computer-comparing different models of quantum computations

Forgive me if this question was already asked somewhere on this site-I haven't found it but it is possible that I've overlooked it. So basically, I would like to summarize different notions of quantum ...
truebaran's user avatar
  • 153
1 vote
0 answers
77 views

What is the quantum circuit complexity of a multi-control Y-gate with n control bits and 1 output bit?

It is known that many multicontrol quantum gates consist of sets of elementary gates, and there seems to be no authoritative way to give the complexity of such multicontrol quantum gates. So using one ...
Ren-Xin Zhao's user avatar
3 votes
1 answer
73 views

Simulating Sparse Hamiltonians: help understanding query complexity bounds

tl;dr: How can I show that $e^k/k^k$ is less than $\epsilon^2/2$ when $k=\Omega\left(\frac{\log(1/\epsilon)}{\log \log(1/\epsilon)}\right)$, where $k,\epsilon\in \mathbb{R}$ and > 0? Context: Berry ...
muru's user avatar
  • 33
4 votes
1 answer
144 views

Quantum algorithm to get $d$ (private exponent) directly without factoring first

Shor's algorithm is for finding period $r$ such that $a^r\equiv 1\bmod N$. Knowing period we can factor $N$. In RSA we encrypt message $m$ by $m^e\bmod N$ ($e$ and $N$ are public keys). Let us pick ...
Turbo's user avatar
  • 181
1 vote
1 answer
71 views

Efficiently simulating a BQP circuit and polynomial hierachy collapse

If we were able to simulate a BQP (Bounded-error Quantum Polynomial time) circuit using a classical computer in an efficient manner, does it necessarily mean that the Polynomial Hierarchy (PH) would ...
MonteNero's user avatar
  • 2,656
1 vote
0 answers
21 views

Intuitive explanation on dependence of Hamiltonian simulation on norm?

Suppose I have two Hamiltonians, $H_1$ and $H_2$, that I want to simulate for time $T$. If $\|\|H_1\|\|>\|\|H_2\|\|$, why is it more costly to simulate $H_1$ compared to $H_2$? Is there an ...
confusion's user avatar
  • 155
2 votes
1 answer
83 views

How many eigenstates are accessible in polynomial time?

A result of Hamiltonian complexity theory by Poulin et al. shows that only a small fraction of the volume of Hilbert space can be reached in polynomial time for any physical system or quantum computer....
Dr. T. Q. Bit's user avatar
4 votes
1 answer
162 views

In Shor's algorithm, what is the exact analysis of its time and probability complexity?

Generally exact complexities aren't interesting, but I couldn't find any info on it for this case at all. Specifically my question, is let's say I have a polynomial p(n) and I want to have a quantum ...
user25790's user avatar
4 votes
2 answers
138 views

Relation between BQP-Complete and BQP \ PH

Recently, the oracle separation between BQP and PH has been proven. Does this result tell us something about the relation between BQP-complete problems (e.g. approximation Jones polynomial solved by ...
incud's user avatar
  • 721
1 vote
1 answer
67 views

Amplitude Estimation/Counting - unsatisfiability

The Amplitude Amplification paper states in Theorem 13: For any positive integers $M$ and $k$, and any Boolean function $f: \{0,1,\ldots,N-1\}\rightarrow\{0,1\}$, the algorithm Count $\left(f,M\right)...
inq's user avatar
  • 111
3 votes
1 answer
189 views

Question about the definition of BQP-completeness

From what I know, a problem $p_0$ is BQP-complete if you can reduce any BQP problem $p$ to $p_0$. There will be an overhead involved in doing the reduction from $p$ to $p_0$. What I was wondering was ...
Sean Thrasher's user avatar
5 votes
1 answer
191 views

Is BQP or PromiseBQP the better formalization of the set of "problems" that a quantum computer could solve efficiently?

This question is inherently somewhat subjective, but here goes. BQP is (roughly) defined to be the set of decision problems that can be efficiently solved by a quantum computer. PromiseBQP is (roughly)...
tparker's user avatar
  • 2,811
13 votes
3 answers
2k views

Are there any quantum algorithms conjectured to give an exponential speedup for a non-oracle problem that don't use the Quantum Fourier Transform?

The Quantum Fourier Transform (QFT) subroutine seems ubiquitous in most quantum algorithms that are conjectured to give an exponential (or at least superpolynomial) speedup over the best classical ...
tparker's user avatar
  • 2,811
2 votes
1 answer
51 views

Change of basis on a per vector component level

Suppose we have an $n$-qubit quantum state in the computational basis encoded in a classical blackbox function $f(x)$. That is, with $x \in \{0,1\}^n$ we can query $f$ and get the respective ...
MonteNero's user avatar
  • 2,656
0 votes
0 answers
28 views

On quantum and classical complexity [duplicate]

Do we have an example of a task that provably consumes more time/memory in the case of a classical computer than a quantum one? For example, Shor's factorization is polynomial, while the classical ...
Join the party P.A.R.T.Y.'s user avatar

1
2 3 4 5
7