Skip to main content

Questions tagged [bqp]

For questions about the quantum complexity class referring to problems that can be solved by a quantum computer in polynomial time (the quantum equivalent of the classical complexity class P). You may also wish to tag with [complexity-theory].

Filter by
Sorted by
Tagged with
2 votes
1 answer
83 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
74 views

On the genesis of 'APPROX-QCIRCUIT-PROB': a (promise) BQP-complete problem

Wikipedia mentions APPROX-QCIRCUIT-PROB (AQP) as a (promise) BQP-complete problem. It seems convincing that it is a complete problem for BQP. The lecture notes of Prof. Henry Yuen mention it too, here....
Manish Kumar's user avatar
2 votes
0 answers
80 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
4 votes
1 answer
158 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
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
166 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
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
  • 731
3 votes
1 answer
205 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
4 votes
0 answers
45 views

Can we have a constant-overhead threshold theorem?

The threshold theorem states that any abstract circuit in BQP can be computed by another polynomial-depth circuit that succeeds in the presence of noise. The original construction from 1996 requires ...
Dudu Ponar's user avatar
2 votes
1 answer
86 views

Confusion regarding hardness of BQP

Consider a polynomial time quantum circuit on $n$ qubits. The class of circuits under consideration encompasses the complexity class $\mathsf{BQP}$. Now, say we have an $n-1$ qubit polynomial time ...
BlackHat18's user avatar
  • 1,363
3 votes
0 answers
36 views

Non-promise problems that are BQP complete, and showing them to be or not to be in NP

Whenever we discuss "BQP" as a complexity class, we often are really talking about "Promise-BQP" instead of BQP. And the same goes for BQP-complete problems, all that I can find ...
Loic Stoic's user avatar
1 vote
1 answer
53 views

Are Quantum Algorithms that construct another Quantum Algorithm still valid to solve problems in BQP?

The title of this question is somewhat convoluted. Essentially, a problem is in BQP if there is a Turing machine that runs in polynomial time that computes a polynomial depth quantum circuit that ...
TwentyCents's user avatar
8 votes
1 answer
175 views

Polynomial time reductions vs. Quantum Polynomial time reductions

In computer science, a language $A$ reduces to a language $B$ if there exists a computable function (one that can be computed by a Turing machine) $f_{AB} \colon \Sigma^* \mapsto \Sigma^*$ such that $...
Andrew Baker's user avatar
9 votes
2 answers
333 views

Is APPROX-QCIRCUIT-PROB a BQP-complete problem?

I've read contradictory information: on the Wikipedia page for BQP, it is written without proof that "APPROX-QCIRCUIT-PROB is a BQP-complete problem", while I have read elsewhere (don't ...
Pierre Yves Schobbens's user avatar
8 votes
1 answer
826 views

Is it known that BQP is not contained within NP?

I recently stumbled upon this paper here and here on the "deep ai" website that claims "BQP is not in NP." I thought that this result would be huge (as a corollary would be that $...
wavosa's user avatar
  • 399
5 votes
1 answer
207 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$-...
Haim's user avatar
  • 257
6 votes
2 answers
422 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 ...
user777's user avatar
  • 377
7 votes
3 answers
1k 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.
Eoin Dowling's user avatar
11 votes
1 answer
499 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 ...
Mark Spinelli's user avatar
3 votes
1 answer
360 views

BQP and PH separation

I was reading the Quanta article here which shows that there exists a problem which achieves "oracle separation between BQP and PH". In simple terms, there exists a problem which a quantum ...
user1936752's user avatar
  • 3,033
12 votes
0 answers
279 views

Is HHL still BQP-complete when the matrix entries are only in {0,1}?

I'm studying BQP-completeness proofs of a number of interesting problems of Janzing and Wocjan, and Wocjan and Zhang. Janzing and Wocjan show that estimating entries of matrix powers $(A^m)_{ij}$ with ...
Mark Spinelli's user avatar
4 votes
1 answer
103 views

Could finding Golomb rulers be in $\mathrm{BQP}$?

The problem of factoring large numbers may be in the so-called "intermediate" regime. These are problems that are in $\mathrm{NP}$, but are neither likely to be easy enough to be in $\mathrm{P}$ nor ...
Mark Spinelli's user avatar
1 vote
1 answer
97 views

$\sf BQP$ and general $\mathrm{SU}(2^n)$ gates

In his lecture on quantum computing, Scott Aaronson describes polynomial-size quantum circuits, Now, once we fix a universal set (any universal set) of quantum gates, we'll be interested in those ...
Dyon J Don Kiwi van Vreumingen's user avatar
22 votes
2 answers
4k views

What does Google's claim of "Quantum Supremacy" mean for the question of BQP vs BPP vs NP?

Google recently announced that they have achieved "Quantum Supremacy": "that would be practically impossible for a classical machine." Does this mean that they have definitely proved that BQP ≠ BPP ?...
Alex Kinman's user avatar
9 votes
0 answers
418 views

Is there a BQP algorithm for each level of the polynomial hierarchy PH?

This question is inspired by thinking about quantum computing power with respect to games, such as chess/checkers/other toy games. Games fit naturally into the polynomial hierarchy $\mathrm{PH}$; I'm ...
Mark Spinelli's user avatar
1 vote
1 answer
1k views

Clarification needed for the N&C proof that BQP ⊆ PSPACE

In QCQI by Chuang and Nielsen (page 201), they prove that $\mathsf{BQP} \subseteq \mathsf{PSPACE}$. I can't understand what they say. They write "Supposing the quantum circuit starts in the state $...
bilanush's user avatar
  • 881
9 votes
2 answers
716 views

Why doesn't Deutsch-Jozsa Algorithm show that P ≠ BQP?

To my understanding, Deutsch-Jozsa algorithm solves a specific problem in constant time, using a fixed circuit depth, compared to a classical deterministic algorithm, which would require time ...
3yakuya's user avatar
  • 632
10 votes
1 answer
758 views

What is recursive Fourier sampling and how does it prove separations between BQP and NP in the black-box model?

Context: I was going through John Watrous' lecture Quantum Complexity Theory (Part 1) - CSSQI 2012. Around 48 minutes into the lecture, he presents the following: No relationship is known between $\...
Sanchayan Dutta's user avatar
7 votes
1 answer
650 views

Query regarding BQP belonging to PP

I found the following proof of BQP belonging to PP (the original document is here). There is a part of the proof that I have trouble understanding. First, the structure is given below. We try to ...
BlackHat18's user avatar
  • 1,363
15 votes
2 answers
887 views

Jones Polynomial

There are many fairly standard quantum algorithms that can all be understood within a very similar framework, from Deutsch's algorithm Simon's problem, Grover's search, Shor's algorithm and so on. ...
DaftWullie's user avatar
  • 59.3k
25 votes
1 answer
2k views

What are examples of Hamiltonian simulation problems that are BQP-complete?

Many papers assert that Hamiltonian simulation is BQP-complete (e.g., Hamiltonian simulation with nearly optimal dependence on all parameters and Hamiltonian Simulation by Qubitization). It is easy ...
groupsgroupsgroups's user avatar
10 votes
2 answers
802 views

Is BQP only about time? Is this meaningful?

The complexity class BQP (bounded-error quantum polynomial time) seems to be defined only considering the time factor. Is this always meaningful? Do algorithms exist where computational time scales ...
Daniel Tordera's user avatar
10 votes
2 answers
428 views

Consequences of SAT ∈ BQP

"Quantum magic won't be enough" (Bennett et al. 1997) If you throw away the problem structure, and just consider the space of $2^n$ possible solutions, then even a quantum computer needs about $\...
Didix's user avatar
  • 785
36 votes
2 answers
2k views

Why is a quantum computer in some ways more powerful than a nondeterministic Turing machine?

The standard popular-news account of quantum computing is that a quantum computer (QC) would work by splitting into exponentially many noninteracting parallel copies of itself in different universes ...
tparker's user avatar
  • 2,831
30 votes
2 answers
6k views

What is postselection in quantum computing?

A quantum computer can efficiently solve problems lying in the complexity class BQP. I have seen a claim that one can (potentially, because we don't know whether BQP is a proper subset or equal to PP) ...
Sir Cornflakes's user avatar