Unanswered Questions
309 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 ...
- 1,482
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 ...
- 12.2k
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 ...
- 201
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 ...
- 12.9k
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
105
views
How to decide which quantum device to use if a quantum algorithm is given?
I'm planning to write my master thesis in quantum computing. The subject of the thesis is to find out which attributes (properties, features) of quantum algorithms respectively their implementations (...
- 387
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 ...
glS♦
- 25.9k
8
votes
0
answers
95
views
Are non-secret-based quantum money mini-schemes susceptable to Jogenfors' "reuse attack?"
Aaronson and Christiano call public-key or private-key quantum mini-schemes $\mathcal M$ secret-based if a mint works by first uniformly generating a secret random classical strings $r$, and then ...
- 12.9k
8
votes
1
answer
639
views
Gradient boosting akin to XGBoost using a quantum device
I am currently trying to implement a boosting algorithm akin to XGBoost with a quantum device. The reason is that I want to make use of a quantum device to train weak classifiers. However, as far as I ...
CommunityBot
- 1
8
votes
0
answers
366
views
Requirements for Achieving a Quantum Speedup
We usually talk about the power of a quantum computer by examining the separation between sets of gates that we know we can efficiently simulate on a classical computer (i.e. problems in the class BPP)...
- 2,337
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-...
- 326
7
votes
0
answers
75
views
If we could only get two-qubit tomography as an output, what algorithms are possible
According to the circuit model, the output for a quantum computation on $n$ qubits is an $n$-bit string. But what if we instead got a full two qubit tomography for all $n(n-1)$ pairs of qubits?
This ...
- 11.3k
7
votes
0
answers
257
views
How can blackholes be fast information scramblers?
I noticed that there was already a post discussing the fast scrambling property of black holes. But it seems no satisfactory answer was given.
As mentioned by L. Susskind et. al, the fast scrambling ...
glS♦
- 25.9k
6
votes
0
answers
81
views
Is amplitude estimation optimal?
Amplitude estimation requires $O(1/\epsilon)$ measurements if we want to estimate an amplitude to absolute precision $\epsilon$. Is this optimal? Why can't we do better than this?
I'm trying to see if ...
glS♦
- 25.9k
6
votes
0
answers
136
views
Why is lattice-based cryptography believed to be hard to solve for quantum computers?
Lattice-based cryptography is said to be the main contender for a post-quantum cryptography framework. It's thought that instead of having to switch everything over to QKD, post-quantum algorithms can ...
- 1,149