Unanswered Questions
75 questions with no upvoted or accepted answers
2
votes
0
answers
169
views
How to roughly analyze computational complexity of quantum circuit?
I'm looking for just a few simple calculations to analyze complexity when comparing quantum circuits.
I'll compare 2 scenarios, and I'd love for someone to critique or verify my analysis:
Circuit of ...
- 81
2
votes
0
answers
68
views
Why do Hamiltonian simulation algorithms not depend on the size of the Hamiltonian for the gate complexity?
The wikipedia page for Hamiltonian simulation mentions the gate and query complexities for different algorithms used for the problem (Trotter-Suzuki, Taylor Series, Quantum Walks, and QSP).
They ...
- 423
2
votes
0
answers
110
views
Grover's algorithm for multiple solutions complexity
I'm reading Nielsen&Chuang book (for myself) and I'm completely stuck with one of the problems, 6.3(Database retrieval):
Given a quantum oracle which returns $\left|{k, y \bigoplus X(k)}\right>$...
- 1
2
votes
0
answers
38
views
Computational Complexity of random Transverse-Ising Chain
It is well known that many NP-hard classical problems can be mapped to a spin-configuration Ising problem (see for example https://arxiv.org/pdf/1302.5843.pdf)
However, what I would like to know is ...
- 131
2
votes
0
answers
595
views
What is the complexity of the Hadamard test and the SWAP test?
How to calculate the complexity of both the Hadamard test and SWAP test with $n$ qubits?
- 2,357
2
votes
0
answers
79
views
What is the explicit best known quantum algorithm for LWE?
Consider the learning with errors(LWE) problem which is known to be hard for quantum computers.
Let $q \geq 2$ be a prime integer. Consider us being given (polynomially many samples of) either:
$$A, ...
- 3,009
2
votes
0
answers
220
views
Is there an efficient quantum circuit that create a random permuntation matrix?
Suppose we want to generate a random, random according to some probability distribution, unitary permutation matrix that is applied to an input of $n$ qubits. So is there an efficient polynomial time ...
glS♦
- 25.9k
2
votes
0
answers
38
views
What constitutes generic dynamics, and how is it different from a fully random function?
What constitutes generic dynamics? And how is it different from a fully random function?
From what I understand, a fully random function is one that is "Haar" random. And generic dynamics, ...
glS♦
- 25.9k
2
votes
0
answers
156
views
Relation between approximate counting and sampling
Consider the following statement of Stockmeyer counting theorem.
Given as input a function $f:\{0, 1\}^{n} \rightarrow \{0, 1\}^{m}$
and $y \in \{0, 1\}^{m}$, there is a procedure that runs in ...
- 1,373
2
votes
0
answers
199
views
When is a Quantum Computer Slower Than a Classical Computer?
Someone offhandedly mentioned to me that quantum computers are sometimes significantly (I guess they meant asymptotically) slower than classical computers.
Unfortunately, I didn't get any arguments ...
- 189
2
votes
0
answers
92
views
How precise are BQPSPACE measurements?
This is in a similar spirit to another question I asked here.
Let's say I am given a $k$-local Hamiltonian $H$. We know that $||H|| \leq 1$. Let the ground state be $|\psi_{0}\rangle$, with energy $E_{...
- 1,373
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
83
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
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
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