Unanswered Questions
76 questions with no upvoted or accepted answers
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
1
vote
0
answers
86
views
What is the quantum circuit complexity of a multi-control Y-gate with n control bits and 1 output bit?
It is known that many multicontrol quantum gates consist of sets of elementary gates, and there seems to be no authoritative way to give the complexity of such multicontrol quantum gates. So using one ...
- 536
1
vote
0
answers
22
views
Intuitive explanation on dependence of Hamiltonian simulation on norm?
Suppose I have two Hamiltonians, $H_1$ and $H_2$, that I want to simulate for time $T$. If $\|\|H_1\|\|>\|\|H_2\|\|$, why is it more costly to simulate $H_1$ compared to $H_2$? Is there an ...
- 155
1
vote
0
answers
22
views
How does Functional Completeness look like in the quantum world?
Can Post's theorem help to elucidate the nature of quantum logic or other non-classical logics? Quantum logic uses a different set of logical connectives than classical logic, which makes questions of ...
- 111
1
vote
0
answers
44
views
Can one simulate Gaussian Boson Sampling using Fock Boson Sampling or vice versa?
In Fock Boson Sampling, one starts with a particle-number state $|n_1, ..., n_m\rangle$ of $m$ modes, sends it to an interferometer effecting a unitary operation $U$ on the creation operators, and ...
- 704
1
vote
0
answers
28
views
Pure Product State Problem Clarification about $\alpha$-closeness and $\beta$-farness
I am reading a paper on entanglement, specifically, determining if a state is close to being entangled or not.
The problem first introduces the $(\alpha, \beta, l)$-Pure product state problem. This ...
glS♦
- 25.9k
1
vote
0
answers
38
views
Bound on scaling mixed quantum-classical computer designs
I am familiar with some basics of quantum computation and this makes me wonder, are there any upper bounds known on the size of a quantum circuit, such that quantum circuit + some classical circuit, ...
- 111
1
vote
0
answers
62
views
Time Complexity (Big O Notation)
What is the time complexity of the two error-mitigation methods that are implemented in qiskit.ignis.
1- pseudo inverse.
2- least squares.
1
vote
0
answers
48
views
Alternate proof to the witness-preserving amplification theorem for QMA
The most familiar witness-preserving amplification for QMA is based on Jordan's lemma and uses the projections $\Pi_1$ and $\Pi_2$ where $\Pi_1$ is he projection on the 'ancilla zero' space, and $\...
- 189
1
vote
0
answers
69
views
Definition of promise problems with growth conditions
I will preface this by saying that I am a physicist, so I suspect that there are some basic misunderstandings about computer science terminology here which I hope can be clarified.
A typical ...
- 111
1
vote
0
answers
132
views
How to estimate the complexity of a variational quantum circuit？
How to estimate the complexity of a variational quantum circuit? For example, I have a quantum circuit of $n$ qubits that uses alternating operators to build the network and train it. So what is the ...
glS♦
- 25.9k
1
vote
0
answers
52
views
Hardwiring the output in black box separation
In this paper, while using a diagonalization argument in Section $5$, the authors write:
Fix some enumeration over all $poly(n)$-size quantum verifiers $M_{1},
M_{2},...$ which we can do because the ...
- 1,373
1
vote
0
answers
367
views
Not sure what do Nielsen and Chuang mean by number of operations
I am reading Nielsen and Chuang's "Quantum Computation and Quantum Information". One important concept about algorithms is how the number of operations scales with the length of the input. I realized ...
- 3,251
0
votes
0
answers
35
views
Derivation of complexity for data encoding schemes
Could anyone help to derive the space-time complexities of the following different data encoding schemes ?
- 7