Unanswered Questions
195 questions with no upvoted or accepted answers
15
votes
0
answers
599
views
Relation between quantum entanglement and quantum state complexity
Both quantum entanglement and quantum state complexity are important in quantum information processing. They are usually highly correlated, i.e., roughly a state with a higher entanglement corresponds ...
13
votes
0
answers
287
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 ...
10
votes
0
answers
122
views
Strong vs weak simulations and the polynomial hierarchy collapse
(Edited to make the argument and the question more precise)
An argument for quantum computational "supremacy" (specifically in Bremner et al. and the Google paper) assumes that there exists a ...
9
votes
0
answers
420
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 ...
9
votes
0
answers
141
views
Empirical Algorithmics for Near-Term Quantum Computing
In Empirical Algorithmics, researchers aim to understand the performance of algorithms through analyzing their empirical performance. This is quite common in machine learning and optimization. Right ...
8
votes
0
answers
198
views
Optimal estimation of quantum state overlap - Circuit implementation?
I've been reading this paper, but don't understand what their optimal method really is, and how it can be realized as a quantum circuit.
The paper mentions the "Schur transform" which has a ...
8
votes
0
answers
195
views
Better "In-Place" Amplification of QMA
$\def\braket#1#2{\langle#1|#2\rangle}\def\bra#1{\langle#1|}\def\ket#1{|#1\rangle}$
In MW05 the authors demonstrate so-called "in-place" amplitude amplification for QMA, exhibiting a method for Arthur ...
7
votes
0
answers
73
views
Is there a practical architecture-independent benchmark suitable for adversarial proof of quantum supremacy?
Recent quantum supremacy claims rely, among other things, on extrapolation, which motivates the question in the title, where the word "adversarial" is added to exclude such extrapolation-...
7
votes
0
answers
188
views
Sequential circuit using quantum gates
Without feedback/loop how can we build a sequential circuit? The basic feature of sequential circuit is that is depends not only on the current inputs but also on the previous inputs/outputs. I've ...
6
votes
0
answers
285
views
Could the Hamiltonian of a 2x2 Rubik's Cube be simulated with a NISQ device?
Consider the four cells on each of the six faces of the 2x2x2 Rubik's cube (the pocket cube). We can construct and simulate a quarter-turn Hamiltonian as below. $^*$
Let $\langle F_1,U_1,R_1\rangle$ ...
6
votes
0
answers
93
views
Postselection and hardness of estimating amplitudes
Let $A$ be a class of quantum circuits such that
\begin{equation}
\text{Post}A = \text{Post}BQP,
\end{equation}
where $\text{Post}$ indicates post-selection. Is only this amount of information ...
6
votes
2
answers
203
views
Equivalence checking of quantum circuits up to error
Suppose you are given two circuit descriptions $A$ and $B$ where by a circuit description I mean a sequence of gates (in the order they are applied) and the qubits they are applied on. (For the sake ...
6
votes
0
answers
149
views
How exactly is the stated composite state of the two registers being produced using the $R_{zz}$ controlled rotations?
This is a sequel to How are two different registers being used as "control"?
I found the following quantum circuit given in Fig 5 (page 6) of the same paper i.e. Quantum Circuit Design for ...
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 ...
5
votes
0
answers
73
views
Is circuit cutting equivalent in anyway to quantum teleportation?
I've been introduced recently to circuit cutting, and after seeing the 4 orthogonal measurements with their 8 corresponding initializations but no initial transfer of classical info, the first thing ...