Unanswered Questions
76 questions with no upvoted or accepted answers
1
vote
0
answers
21
views
Beyond polynomial speedups in diagonal entries estimation
Consider the task of estimating the diagonal entries of the power of a real sparse matrix A with $N = 2^n$ rows:
Input: $A \in \mathbb{R}^{N \times N}$ with $A = A^\top$ and $s$-sparse and row-...
- 751
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
1
vote
0
answers
38
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 ...
- 14.6k
1
vote
0
answers
82
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 ...
- 12.9k
4
votes
0
answers
47
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^{ ...
- 14.6k
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
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
1
vote
1
answer
168
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 ...
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
5
votes
0
answers
114
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 ...
glS♦
- 25.9k
1
vote
1
answer
106
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 $\...
CommunityBot
- 1
1
vote
0
answers
36
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 ...
- 430
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