Unanswered Questions
631 questions with no upvoted or accepted answers
13
votes
0
answers
270
views
Does the Curry-Howard correspondence have a quantum-specific type system?
In Wikipedia we can read that
the Curry–Howard correspondence is a correspondence between formal proof calculi and type systems for models of computation. In particular, it splits into two ...
- 3,342
11
votes
0
answers
179
views
Anti-symmetrization on the lattice
Assume, I'm using a system of qubits to simulate a fermionic system.
If I'm using the second-quantized formalism (e.g. orbitals in quantum chemistry), the anti-symmetric nature of the fermionic wave ...
- 2,221
9
votes
0
answers
430
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 ...
- 14.4k
8
votes
0
answers
154
views
Are there any known or obvious practical applications for good solutions to the optimal polynomial intersection problem?
I learned from Aaronson's blog about a recent preprint by Jordan, Shutty, Wootters, (our very own) Zalcman, Schmidhuber, King, Isakov, and Babbush that provides an efficient quantum algorithm to give ...
- 14.4k
8
votes
1
answer
410
views
Enforcing a particular layout mapping in Qiskit
I would like to ask how to set a particular layout during transpiling. I guess that the layout can be set by the initial_layout parameter in the transpiler. However,...
CommunityBot
- 1
8
votes
0
answers
202
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♦
- 26.9k
8
votes
0
answers
262
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♦
- 26.9k
8
votes
0
answers
100
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 ...
- 14.4k
8
votes
0
answers
372
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,319
7
votes
0
answers
210
views
Run VQE for parametrized quantum circuit with ancilla qubits
Let's say we have the following circuit (picture and code shown below), and now the $q_0$ is an ancilla qubit. If the system of interest has only two qubits, Is there a way to use only $q_{1,2}$ as my ...
glS♦
- 26.9k
7
votes
0
answers
77
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.5k
6
votes
0
answers
85
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♦
- 26.9k
6
votes
0
answers
152
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
6
votes
0
answers
159
views
Weak Schur sampling and state distinguishability
Consider the task of distinguishing between the following two $n$ qubit quantum states.
$$ \rho = \frac{\mathbb{I}}{2^{n}}.$$
$$ \sigma = \frac{1}{2^{n/2}}\sum_{x \in \{0, 1\}^{n/2}} |x\rangle\langle ...
- 1,515
6
votes
0
answers
98
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 ...
- 1,515