Skip to main content

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
30 views

Complexity of Partial transpose operation

Let us take a general bipartite system $H = H_a \otimes H_b $, with $d_a$ = dim $H_a$, and similarly $d_b$ = dim $H_b$. My question is: what is the complexity of the partial transpose operation on a ...
Soumyadeep sarma's user avatar
2 votes
0 answers
35 views

Defining quantum computer without reference to a classical computer

In the definition of an "efficient quantum computer", there is a uniformity condition that suggests to me that the notion of an efficient quantum computer is not independent of the notion of ...
trillianhaze's user avatar
1 vote
0 answers
33 views

Performance of quantum annealing systems vs gate based ones

Quantum annealers like D-Wave can be used to solve Quadratic Unconstrained Binary Optimization (QUBO) which is a NP Hard problem (see here) while gate based quantum computers, like the ones created by ...
antony paul's user avatar
9 votes
1 answer
348 views

The quantum complexity of implementing a permutation matrix

Suppose we are given a permutation matrix (which is unitary since it corresponds to a permutation of the basis), acting on a $2^n$-dimensional Hilbert space, which can be seen as a quantum system of $...
Danylo Y's user avatar
  • 7,452
3 votes
0 answers
55 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
67 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
40 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
47 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
85 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
84 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
100 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
81 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
123 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
50 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
75 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
  • 965
3 votes
1 answer
63 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
81 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
263 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
112 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
167 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
66 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
159 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
74 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
113 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
167 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
73 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
174 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
175 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
221 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
101 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
92 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
  • 3,075
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
151 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
78 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
178 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
29 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
134 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
84 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
77 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
146 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,684
1 vote
0 answers
22 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
164 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
141 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
  • 741
1 vote
1 answer
69 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
213 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

1
2 3 4 5
7