Unanswered Questions
76 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
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
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
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 ...
- 1,373
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 ...
CommunityBot
- 1
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 ...
glS♦
- 25.9k
5
votes
0
answers
81
views
What is the computational complexity of decomposing operators in terms of quantum gates?
I have recently worked on a problem involving a rather large Hamiltonian, which I wrote some Python code for its generation following the method in this paper.
No when I used qiskits ...
- 51
5
votes
0
answers
107
views
Lowest energy problem with additional constraints
Consider the following minimization problem:
\begin{align}
&\min_{\rho} \mathrm{Tr}[\rho H] \\
\text{such that:}& \\
&Tr[\rho A_i] \leq 0 \ \ \forall A_i, \ i \in \{1,2,3,...\}
\end{align}
...
- 695
5
votes
0
answers
104
views
Consequences of MIP*=RE regarding quantum universality
Provided that $\mathsf{MIP}^*=\mathsf{RE}$ there can be Bell inequalities that have violations achievable only for infinite dimensional quantum systems (vide discussions in Post1 and Post2). Does this ...
- 2,357
5
votes
0
answers
123
views
Complexity of controlled operations in a two-level unitary operation
In Neilsen and Chuang, chapter 4.5.2 (~p.193), why did the authors come to the conclusion that complexity of operations $C^n(X)$ and $C^n(\tilde{U})$ is $O(n)$?
Did they assume using work qubits? If ...
glS♦
- 25.9k
5
votes
0
answers
119
views
complexity of classical counting algorithm
Does anyone know the solution of Exercise 6.14 of Nielsen and Cheung:
Prove that any classical counting algorithm with a probability at least
3/4 for estimating $M$ correctly to within an ...
- 103
5
votes
0
answers
129
views
Why is there no $N$ in the time complexity of the QLSP algorithm by Childs et al.?
The paper Quantum linear systems algorithms: a primer by Dervovic et al has this table on page 3:
I'm not sure why there's no $N$ in the time complexity of the algorithm by Childs et al. i.e. $\...
- 17.7k
4
votes
0
answers
47
views
Alternative algorithm for quantum phase estimation problem
The Quantum Phase estimation problem is stated below:
Input: Given $U$ as a unitary operator acting on an m-qubit register. If $| \psi \rangle$ is an eigenvector of $U$, then U$| \psi\rangle$ = $e^{ ...
- 14.6k
4
votes
0
answers
46
views
Can we have a constant-overhead threshold theorem?
The threshold theorem states that any abstract circuit in BQP can be computed by another polynomial-depth circuit that succeeds in the presence of noise. The original construction from 1996 requires ...
- 430
4
votes
0
answers
37
views
Is there a general framework that allows us to compare probabilistic and deterministic algorithms fairly?
Many popular QC algorithms are probabilistic in nature, like Grover's, Shor's, QAOA ..etc
For some of these we have formulas that give probabilities of success (like for Grover's and Shor's), and for ...
- 271
4
votes
0
answers
104
views
Relation between geometric and discrete circuit complexity
Geometric complexity of a unitary, as introduced for example here https://arxiv.org/abs/quant-ph/0502070, measures the length of a geodesic connecting the identity matrix and a given unitary in the ...
- 1,655
4
votes
0
answers
125
views
Is the exponential speedup and output $\langle x|M|x\rangle$ in contradiction in HHL algorithm?
Isn't the exponential speedup and the output $\langle x|M|x\rangle$ in contradiction in HHL algorithm? How can we print the solution vector $|x\rangle$ without losing the exponential speedup?
glS♦
- 25.9k
4
votes
0
answers
71
views
Could quantum computers answer the question of whether QCD predicts quark gluon confinement?
As I understand it, it is not known whether or not QCD actually predicts quark gluon confinement.
As I understand it answering questions in quantum field theories is generally harder in terms of ...
- 153
4
votes
0
answers
69
views
Feynman method and polynomial time algorithm for XQUATH
Consider the Feynman algorithm for simulating quantum circuits, as given here.
Consider the XQUATH conjecture for random quantum circuits from here, given by
(XQUATH, or Linear Cross-Entropy Quantum ...
- 1,373
4
votes
0
answers
65
views
Query complexity on Quantum Pattern Matching of Mateus Algorithm
I am trying to understand the complexity of the Mateus and Omar algorithm for quantum pattern matching, it is clear to me from the pseudocode that the query complexity is $O(\sqrt{N})$, apart from the ...
- 2,915
4
votes
0
answers
78
views
What is the computational complexity of approximate quantum adders, in terms of big O notation?
I have recently found papers on approximate quantum adders. However, the papers do not seem to mention the computational complexities of their algorithms. What are their complexities, in terms of big ...
- 1
4
votes
0
answers
134
views
How close is the history state to the ground state in the Kitaev clock construction?
Consider a standard circuit to Hamiltonian reduction in QMA. For example, refer here (Vazirani's lecture notes) or page 235 of here (survey by Gharibian et al).
The history state of the Kitaev clock ...
- 1,373
4
votes
0
answers
65
views
Bound on quantum speedups under various models of complexity
What are the bounds on quantum speedups under the various models of complexity? How big or small can they be?
Under the query model, my understanding is that the lower bound is $\Omega(\sqrt{N})$ as ...
- 23.2k
4
votes
0
answers
227
views
What is the query complexity of the QUBO algorithm?
What is the complexity of the quantum unconstrained binary optimization (QUBO) algorithm in the number of queries to the quantum processor?
To clarify, I'm asking about the complexity on quantum ...
glS♦
- 25.9k
4
votes
0
answers
464
views
What is known about the quantum version of Schoening's algorithm for 3SAT?
Schoening's algorithm for 3SAT can be converted to a quantum algorithm. The classical circuit representing a 3SAT expression in CNF form can be converted to a quantum version involving reversible ...
4
votes
0
answers
81
views
Is either the adiabatic or the diabatic version of quantum annealing known to be theoretically more powerful than the other?
Quantum annealing can be considered either in the perfectly adiabatic "slow" limit (in which case it's usually referred as "adiabatic quantum computing" (AQC) instead of "...
- 2,851
4
votes
0
answers
47
views
Complexity analysis of separability in the multipartite case
It's well known that determining whether a bipartite mixed state is separable or entangled is a $\mathsf{NP}$-hard problem under some accuracy estimates (cf. this TCS SE discussion). Now I'm curious ...
glS♦
- 25.9k
3
votes
1
answer
72
views
Complexity of Variational Quantum Eigensolvers
I am doing research surrounding VQE and am a bit confused about the complexity and its comparison to classical systems. My brief research has yielded me that classical eigenvalue solving is $O(n^3)$. ...
CommunityBot
- 1
3
votes
0
answers
68
views
Why FACTORING is in second level of Fourier hierarchy?
As per comlexityzoo web, the definition of the k-th level of Fourier Hierarchy (FH) is:
$FH_k$ is the class of problems solvable by a uniform family of polynomial-size quantum circuits, with k levels ...
- 711
3
votes
0
answers
88
views
The no fast forwarding theorem and exponential advantage for many body Hamiltonians
When simulating Hamiltonians in first quantization there are $\eta$ particles occupying a grid of $N$ grid points. In the first quantization, you directly discretize the differential operators onto a ...
- 680
3
votes
0
answers
87
views
Complexity of the quantum circuits that are needed to implement communication protocol?
Consider the following simultaneous communication problem. Alice and Bob do not share any
entanglement or any common randomness, and cannot communicate directly with each other. As
inputs, x is given ...
- 14.6k
3
votes
0
answers
37
views
Non-promise problems that are BQP complete, and showing them to be or not to be in NP
Whenever we discuss "BQP" as a complexity class, we often are really talking about "Promise-BQP" instead of BQP.
And the same goes for BQP-complete problems, all that I can find ...
- 423
3
votes
0
answers
122
views
How to find a marked item out of $K < N$ marked items when K is unknown?
I'm wondering about time complexities of variants of the searching problem in Grover's Algorithm. I know that using G.A. the time complexity required to find a market item reduces to $O(\sqrt N)$.
...
- 14.6k
3
votes
0
answers
125
views
Quantum algorithms, combinatorial optimization, and approximation bounds
Recently, I saw this article, Classical and Quantum Bounded Depth Approximation Algorithms where the author discusses the limitations of QAOA relative to classical approaches.
In particular, they ...
- 17.7k
3
votes
0
answers
51
views
Explicit Construction of Classical Rules in Quantum Turing Machine
I knew that we usually use circuit instead of Turing machine in Quantum computation.
In a deterministic Turing machine one has transition rules,
$$
\delta: Q\times\Gamma\rightarrow Q\times\Gamma\...
glS♦
- 25.9k
3
votes
0
answers
65
views
Estimating errors in Hamiltonian Simulation paper
I am looking at the paper: Simulating Hamiltonian dynamics with a truncated Taylor series and I am explicitly interested in Eq (15) and (16). These read
$$ ||PA |0\rangle |\psi \rangle - |0\rangle ...
- 949
3
votes
0
answers
151
views
Does strong error reduction for PostQMA exist?
$\mathsf{PostQMA}$ can be defined as the following (see Morimae-Nishimura and Usher-Hoban-Browne):
A promise problem $\mathcal{L}=(\mathcal{L_{yes},L_{no}})$ is in $\mathsf{PostQMA(c,s)}$ if there ...
- 488
2
votes
0
answers
29
views
Applicability of the error analysis of HHL algorithm assuming spectrum could contain negative and positive eigenvalues
I have a question concerning the applicability of the error analysis of the HHL algorithm , specifically the QPE subroutine. The authors state that they assume all the eigenvalues lie between $[\frac{...
glS♦
- 25.9k
2
votes
0
answers
42
views
Defining quantum computer without reference to a classical computer
In the definition of an "efficient quantum computer", there is a uniformity condition that suggests to me that the notion of an efficient quantum computer is not independent of the notion of ...
glS♦
- 25.9k
2
votes
0
answers
89
views
Is BQP contained in BPP with Quantum Phase Estimation (QPE) oracle?
I am trying to see if the below proposition holds:
Proposition-1: $BQP\subseteq BPP^{QPE}$.
Here, QPE is the Quantum Phase estimation algorithm. QPE takes an eigenstate and the unitary matrix as ...
- 711
2
votes
0
answers
31
views
Why is 3-Coloring in PQMA(2)?
I'm reading https://arxiv.org/abs/0709.0738 about the complexity of PQMA(2) and its relation to NP. It describes a PQMA(2) protocol (3.1) for 3-coloring which contains the following check:
For both $|...
- 21
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