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].
46 questions
0
votes
0
answers
66
views
Understanding theorem 6 of postBQP=PP paper
In this paper, $\mathsf{BQP}_p$ is defined to be similar to $\mathsf{BQP}$ in all aspects except that the Born's measurement rule is changed. For a normalised state
$$|{\psi}\rangle =\sum_x \alpha_x |...
- 988
2
votes
1
answer
146
views
Hardness result for Guided Local Hamiltonian problem for varies parameter regime
Definition (Guided 2-Local Hamiltonian). $\mathsf{2GLH(\delta, \gamma)}$
Input: A 2-local Hamiltonian H with ||H|| $\leq 1$ acting on n qubits, and a semi-classical quantum state $u \in \mathbb{C}^{2^...
- 988
13
votes
2
answers
681
views
Is it hard to invert unitary effects implemented using feedback?
It's well know that if you have a circuit made up of only unitary operations, it's trivial to invert the circuit. Just reverse the order of operations, and invert each individual operation.
However, ...
- 50.8k
1
vote
2
answers
180
views
Is there a sign-problem when the wavefunction itself has positive and negative values, or is it only when the Hamiltonian has such entries?
Consider the following two problems:
Let $A$ be an $s$-sparse $2^n\times 2^n$ Hermitian matrix with entries $A_{jk}$ in $\{0,1,-1\}$ both along the main diagonal and off the diagonal. Let $|\psi\...
- 16.4k
3
votes
1
answer
148
views
Factoring and hardness of Factoring $\Rightarrow$ BQP $\neq$ BPP, or $\Rightarrow$ promise BQP $\neq$ promise BPP?
I know that BQP and promise BQP are often not distinguished, but what I don't understand is, does Shor algorithm (under the important assumption that factoring is hard) prove that:
$BQP \ne BPP$, so ...
- 33
2
votes
0
answers
131
views
Is there a name for this complexity class?
Let me use the ad hoc name weak-$BQP$ for the class obtained from $BQP$ by the following modification: Given a problem instance $x$ with correct solution $y\in \{0, 1 \}^n$, the circuit $C_{|x|}$ ...
2
votes
0
answers
214
views
APPROX-QCIRCUIT-PROB: does it exist outside wikipedia? What is the correct formulation?
In this Wikipedia page there is the description of the problem APPROX-QCIRCUIT-PROB, complete for BQP:
Given a description of a quantum circuit $C$ acting on $n$ qubits with $m$ gates, where $m$ is a ...
- 521
2
votes
1
answer
174
views
Is there any known characterization of k-Local Hamiltonian (k-LH) to distinguish if it has an efficient guiding state?
In general, k-LH promise problem, where input is given as $<H, a, b>$, is QMA complete if $a-b>1/{\textrm{poly}(n)}$.
Also, if a guiding state (say, a "good" approximation to the ...
- 988
2
votes
1
answer
174
views
Clarification about a notation (or typo?) in ComplexityZoo for QAM class
In ComplexityZoo for QAM,
The last line goes as:
(QAM) Contains QMA and is contained in QIP(2) and $BP\&\#149;PP$ (and therefore PSPACE).
I need a help in deciphering "$BP\&\#149;PP$&...
- 988
0
votes
0
answers
104
views
What the key difficulty in (efficiently) simulating a 'Quantum Turing machine' with 'Non-deterministic Turing machine '?
I am reading Niel de Beaudrap's answer in quantumcomputing.SE post to understand the workings of:
Deterministic Turing Machine (DTM),
Non-deterministic Turing Machine (NDTM) and
Quantum Truing ...
- 988
1
vote
1
answer
167
views
Containment in BQP of GLHLE (Guided Local-Hamiltonian Low Energy estimation problem)
In the paper 'Complexity of the Guided Local Hamiltonian Problem:
Improved Parameters and Extension to Excited States' by Cade et. al (2022), they define the following problem
[From page 2; last ...
- 988
3
votes
1
answer
153
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 ...
- 988
1
vote
1
answer
170
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....
- 988
2
votes
0
answers
138
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 ...
- 988
4
votes
1
answer
196
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 ...
- 988