Unanswered Questions
75 questions with no upvoted or accepted answers
4
votes
0
answers
47
views
Complexity analysis of separability in the multipartite case
It's well known that determining whether a bipartite mixed state is separable or entangled is a $\mathsf{NP}$-hard problem under some accuracy estimates (cf. this TCS SE discussion). Now I'm curious ...
glS♦
- 25.9k
3
votes
1
answer
72
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)$. ...
CommunityBot
- 1
3
votes
0
answers
68
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 ...
- 711
3
votes
0
answers
88
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 ...
- 680
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 ...
- 14.6k
3
votes
0
answers
37
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 ...
- 423
3
votes
0
answers
122
views
How to find a marked item out of $K < N$ marked items when K is unknown?
I'm wondering about time complexities of variants of the searching problem in Grover's Algorithm. I know that using G.A. the time complexity required to find a market item reduces to $O(\sqrt N)$.
...
- 14.6k
3
votes
0
answers
125
views
Quantum algorithms, combinatorial optimization, and approximation bounds
Recently, I saw this article, Classical and Quantum Bounded Depth Approximation Algorithms where the author discusses the limitations of QAOA relative to classical approaches.
In particular, they ...
- 17.7k
3
votes
0
answers
51
views
Explicit Construction of Classical Rules in Quantum Turing Machine
I knew that we usually use circuit instead of Turing machine in Quantum computation.
In a deterministic Turing machine one has transition rules,
$$
\delta: Q\times\Gamma\rightarrow Q\times\Gamma\...
glS♦
- 25.9k
3
votes
0
answers
65
views
Estimating errors in Hamiltonian Simulation paper
I am looking at the paper: Simulating Hamiltonian dynamics with a truncated Taylor series and I am explicitly interested in Eq (15) and (16). These read
$$ ||PA |0\rangle |\psi \rangle - |0\rangle ...
- 949
3
votes
0
answers
151
views
Does strong error reduction for PostQMA exist?
$\mathsf{PostQMA}$ can be defined as the following (see Morimae-Nishimura and Usher-Hoban-Browne):
A promise problem $\mathcal{L}=(\mathcal{L_{yes},L_{no}})$ is in $\mathsf{PostQMA(c,s)}$ if there ...
- 488
2
votes
0
answers
29
views
Applicability of the error analysis of HHL algorithm assuming spectrum could contain negative and positive eigenvalues
I have a question concerning the applicability of the error analysis of the HHL algorithm , specifically the QPE subroutine. The authors state that they assume all the eigenvalues lie between $[\frac{...
glS♦
- 25.9k
2
votes
0
answers
42
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 ...
glS♦
- 25.9k
2
votes
0
answers
89
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 ...
- 711
2
votes
0
answers
31
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 $|...
- 21