Questions tagged [quantum-computing]
Quantum computation and computational issues related to quantum mechanics
106
questions with no upvoted or accepted answers
28
votes
0
answers
523
views
Adiabatic quantum computing with level crossings
Question.
In adiabatic evolution, to ensure that the ground state high overlap with the unique ground state of the system (i.e. to achieve arbitrarily small error) using adiabatic theorems, it is ...
- 8,821
19
votes
1
answer
305
views
Is there a geometrical picture for adiabatic quantum computation?
In adiabatic quantum computation (AQC), one encodes the solution to an optimization problem in the ground state of a [problem] Hamiltonian $H_p$. To get to this ground state, you start in an easily ...
- 431
16
votes
0
answers
538
views
Quantum Hardness of Finding Nash Equilibria
This question is inspired by the recent, beautiful work On the Cryptographic Hardness of Finding a Nash Equilibrium by Bitansky, Paneth, and Rosen.
Their main result is that the existence of ...
- 5,961
13
votes
0
answers
668
views
New quantum algorithm for approximating permanent
Joonsuk Huh uploaded a paper "A fast quantum algorithm for computing matrix permanent
" on arxiv, which claims a polynomial-time algorithm approximating the permanent of an arbitrary matrix ...
- 261
13
votes
0
answers
303
views
Is there any known nontrivial result on QIP systems having a space-bounded verifier?
Is there any known nontrivial result on quantum interactive proof (QIP) systems having a space-bounded verifier?
The only paper I know is An application of quantum finite automata to interactive ...
- 3,707
11
votes
0
answers
291
views
Does MIP* = RE algebrize?
Does the MIP* = RE result algebrize? (It doesn’t relativize, as noted here.)
If it doesn’t algebrize, is there a more complicated similar notion that it does satisfy?
- 3,243
11
votes
0
answers
285
views
What are the most recent developments in small-depth quantum circuits?
Back in 2005, Scott Aaronson posted a list of 10 "semi-grand" challenges for quantum computing theory which contained the following challenge:
The power of small-depth quantum circuits. Is $BQP = ...
- 960
10
votes
0
answers
238
views
Relatively low ambitious frontiers
What are some of the current "relatively" low ambitious frontiers for MA/PhD thesis in complexity theory class separations/containment or quantum computing?
For example: In the draft version of Arora ...
- 1,596
10
votes
0
answers
260
views
How would proof of the Lindelöf hypothesis improve our understanding of computational complexity classes?
A recent press release from the Viterbi School of Engineering at USC discussed the proof of the Lindelöf hypothesis by Athanassios Fokas, a visiting professor from the Department of Applied ...
- 233
10
votes
0
answers
246
views
How hard it is to approximate the ground state of the (2-D) Hubbard model
The Hubbard model (see also the wikipedea article on the Bose-Hubbard model) is a basic quantum model of solid-state physics.
Question: What is the computational complexity of approximating the ...
- 6,013
9
votes
0
answers
115
views
Non-tomographical certification of projectors, using product states?
I'm interested in operational ways of demonstrating (with high probability of confidence, in an error-free setting) that a POVM operator on n-qubit states is a projector. Specifically, I'm interested ...
- 8,821
8
votes
0
answers
201
views
Computing permanents when we are promised that the value of the permanent is large
Suppose you are given an $n$ by $m$ real matrix (or even complex matrix) with orthonormal rows. ($m=poly(n)$, say $m=n^2$.) For an $n$-tuples of columns (with repetitions) from M we consider the ...
- 6,013
8
votes
0
answers
356
views
Approximation of Quantum Channels
Background:
In quantum information theory, a wide class of processes acting on stochastic quantum states can be described using the formalism of Quantum Channels:
A quantum channel is a linear, ...
7
votes
0
answers
201
views
What is the complexity of estimating the number of paths between two vertices of a large graph?
Consider an $N\times N$ adjacency matrix $A$ of some large, $b$-sparse undirected graph $G$. The $(i,j)$ entry of $A^m$ counts the number of $m$-length paths between vertex $i$ and vertex $j$.
We let ...
- 1,063
7
votes
0
answers
68
views
Explicit error bounds on the abelian hidden subgroup problem
What are some explicit forms for the error probability in the typical quantum abelian hidden subgroup algorithm as a function of oracles queries?
Ettinger, Hoyer, and Knill give a result that the ...
- 91
7
votes
0
answers
281
views
Implication of Bell test loopholes on Vazirani-Vidick random sequence generation scheme
I am trying to imagine what would be the implications of the loopholes on Bell test on the random sequence generation scheme proposed by Vazirani and Vidick (VV protocol) in the paper titled '...
- 653
7
votes
0
answers
207
views
Are the minimal quantum and classical span programs the same?
A span program is a linear-algebraic way of specifying a boolean function introduced here which has found recent application in quantum query complexity.
A span program for a function $f: \{0,1\}^n \...
- 10.2k
6
votes
0
answers
173
views
Could a quantum computer prove theorems with infeasibly long proofs?
The mathematician Andrew Granville recently published a
"philosophical" article, Accepted proofs: Objective truth, or culturally robust?.
At the end, he mentions in passing a suggestion by ...
- 7,465
6
votes
0
answers
134
views
Is there an analogue of QMA where Merlin gives Arthur unitaries rather than states?
$\def\braket#1#2{\langle#1|#2\rangle}\def\bra#1{\langle#1|}\def\ket#1{|#1\rangle}$Is there an analogue to $\mathsf{QMA}$ where Merlin provides to Arthur single-use access to a unitary operator $U$? By ...
- 161
6
votes
0
answers
164
views
Is there a universal gate set for classical probabilistic computing?
We know that NAND gates are universal for deterministic classical circuits, Toffoli gates are universal for reversible deterministic classical circuits, and Clifford+T is universal for quantum ...
- 161
6
votes
0
answers
102
views
Efficient quantum algorithm for CLASSICAL FFT
Is there a known improvement on the current O(n*log(n)) algorithm for CLASSICAL FFT using quantum computation? 'n' is the number of samples.
I need to find the amplitude and phase of the K dominating ...
6
votes
0
answers
293
views
Quantum computer versus Random 3-SAT?
It seems to be commonly believed that a quantum computer cannot efficiently solve NP-hard problems. What about problems that are challenging in the average-case, such as Planted Clique and Random 3-...
- 832
6
votes
0
answers
182
views
Local Hamiltonian and combinatorial search problems
I was going through the PhD thesis of Daniel Nagaj. At the beginning of chapter two he indicated a relation between the local Hamiltonian perspective of adiabatic quantum computation and combination ...
- 653
5
votes
0
answers
84
views
(Where) is determining the mixing time of an implicitly defined graph in the polynomial hierarchy?
Consider an implicitly defined graph; for example, let $G$ be a finite group generated with $n$ generators as $\langle g_1,g_2,\ldots g_n\rangle$ and let $\Gamma$ be the Cayley graph of $G$ under ...
- 1,063
5
votes
0
answers
121
views
Quantum security of cryptosystems: Are any non-Goppa code-based systems resistant to hidden subgroup attacks?
One of the main candidates for post-quantum cryptography is code-based cryptography (as opposed to lattice-based). The Niederreiter cryptosystem based on Goppa codes is shown to be resistant to hidden ...
- 387
5
votes
0
answers
186
views
Dequantumizability known and unknown?
Dequantumizable problems have been taking some headlines these days (for example this blog post by Scott Aaronson and this article in Quantum Magazine).
What are some problems that are currently ...
- 12.8k
5
votes
0
answers
279
views
Generating quadratic optimization problems amenable to quantum annealing
Some context: there is a current debate in adiabatic quantum computing over whether a particular machine, the D-Wave quantum annealer, can outperform a classical algorithm [*]. Earlier this year, a ...
- 431
5
votes
0
answers
191
views
Do the quantum communication complexity lower bounds hold when parties can send a "duplicated" qubits?
This question continues from the previous question where I mistakenly asked a question that is too general.
In quantum communication complexity, we always assume that Alice and Bob have unlimited ...
- 763
5
votes
1
answer
147
views
Is black box parallel quantum speedup ever nontrivial?
Grover's algorithm is not parallelizable, in that $p$ quantum processors searching over $n$ elements can't do better than $O(\sqrt{n/p})$ queries.
Are there any oracle problems where quantum ...
- 3,243
4
votes
0
answers
53
views
Quantum circuits vs quantum circuits w/ only local interactions?
If we restrict a quantum circuit to only have interactions between "nearby" qubits (for some connection topology that defines "nearby", as is the case in several actual quantum ...
- 36.9k
4
votes
0
answers
128
views
Relationship b/w $QMA$ and $QCMA$
I was trying to read and understand about the complexity classes $QMA$ and $QCMA$:
$QMA$ is defined as the class with the set of problem such that, given a quantum certificate for any problem, its ...
- 468
4
votes
0
answers
75
views
Hardness of ancilla free quantum circuit extraction from circuit with ancillas
Is there any known result regarding the hardness of the following problem:
Given a quantum circuit with ancillae implementing a unitary, find a quantum circuit that does not use any ancillae that ...
- 141
4
votes
0
answers
247
views
Convexity argument in QMA Amplification
I'm interested in the basic amplification procedure for QMA: the prover sends $O(r)$ copies of his witness to the verifier, which decreases the error probability to $2^{-O(r)}$ (Chernoff bound). The ...
- 293
4
votes
0
answers
107
views
Why primitive rotation is $53.13^\circ$ in the quantum Turing machine used by Vitanyi for Quantum Kolmogrov Complexity?
Right now I am going through Quantum Kolmogorov Complexity Based on Classical Descriptions by Vitanyi.
In the introduction, the author assumed the primitive rotation $\theta = 53.13^\circ$ to have ...
- 653
4
votes
0
answers
79
views
Does simulating chiral gauge theories lie within BQP?
In theoretical physics, there is a branch of quantum field theory dealing with chiral gauge theories. It has been conjectured by Feynman [1] and others that all quantum field theories can be simulated ...
- 41
4
votes
0
answers
189
views
Two questions on Shor's algorithm
Does Shor's algorithm produce factors of a $n$-bit number and discrete log modulo $n$-bit prime in $O((\log n)^{2+\epsilon})$ bit operations using fast multiplication? I am trying to read from ...
- 12.8k
4
votes
0
answers
248
views
Are NQP and QMA comparable?
Both definitions try to create a quantum analog for NP. NQP's definition comes from non-deterministic algorithms: it contains languages for which a Quantum Algorithm accepts with non-zero probability ...
- 554
3
votes
0
answers
27
views
(Classical) Zero Knowledge protocol with quantum poly time simulator
We have lower bounds for classical zero-knowledge protocols (eg we cannot have 3-round zero-knowledge protocols for NP, with negligible soundness and black-box simulation). However, some of these ...
- 31
3
votes
0
answers
117
views
Is there a name for the class of languages based on reversible circuits, as studied by the physicists of the late 70's/early 80's?
I'm interested in the (pre)history of quantum computing, especially in light of the work of physicists and engineers who studied reversible computing in the 60's through the late 70's/early 80's. ...
- 1,063
3
votes
0
answers
237
views
$NP=QMA$'s impact on $BPP$ vs $BQP$ problem
$\mathit{BPP}$ vs $\mathit{NP}$ and $\mathit{BQP}$ vs $\mathit{QMA}$ are two problems that are (in spirit, for classical and quantum computers respectively) similar and both are open. Moreover, we don'...
- 793
3
votes
0
answers
96
views
Worst to average case reductions for quantum complexity classes
I am studying worst to average case reductions for different complexity classes.
Consider quantum complexity classes like QMA, QSZK, or QIP. Is it known or believed that these classes are amenable to ...
- 173
3
votes
0
answers
108
views
Proof: Why are MM-1QFA strictly more powerful than MO-1QFA? (Quantum automata)
While dealing with quantum finite automata (QFA), I repeatedly come across the statement that measure-many QFA (MM-1QFA, KW97) are strictly more powerful than measure-once QFA (MO-1QFA, MC97). More ...
- 31
3
votes
0
answers
1k
views
BQNC and Abelian Hidden Subgroup Problem
We know integer factorization is in $BPP^{BQNC}$ from Cleve and Watrous.
Is Abelian Hidden Subgroup Problem also in $BPP^{BQNC}$?
In particular is Discrete Logarithm in $BQNC$ or at least in $BPP^{...
- 12.8k
3
votes
0
answers
113
views
Quantum annealing or adiabatic quantum optimization with continuous optimization problems
How do quantum annealing or adiabatic quantum optimization deal with continuous optimization problems such as SDP?
- 131
3
votes
0
answers
195
views
Why is Shor's algorithm in $BPP^{BQNC}$ when needing to uncompute subprocedure call?
Why is Shor's algorithm in $BPP^{BQNC}$? It's true the quantum Fourier transform is in $BPP^{BQNC}$, but the algorithm needs to call a number theoretic function f which has period p which is a factor ...
- 41
3
votes
0
answers
214
views
Environment-assisted quantum transport computation
The paper below and the news story based on it describe a new form of computation based on what they call environment-assisted quantum transport (ENAQT).
ENAQT involves a combination of quantum and ...
- 131
2
votes
0
answers
39
views
Space complexity of quantum algorithms for Subset sum
As far as I can find there are several quantum algorithms for the Subset sum problem with $2^{n/3}$ running time. Is there an algorithm with $2^{n/3}$ running time that uses much less space?
- 891
2
votes
0
answers
78
views
Status of QNC vs. PSPACE
It is known that $\text{NC} \neq \text{PSPACE}$, now I am wondering if there is a similar separation for $\text{QNC}$, the class of decision problems solvable by polylogarithmic-depth quantum circuits ...
- 910
2
votes
0
answers
65
views
Open Quantum Analogs to Classical Problems
I am looking for interesting examples of complexity-theoretic and cryptographic problems where we have a significant amount of knowledge about the classical version of the problem, but we have no ...
- 121
2
votes
1
answer
146
views
Can a collection of quantum circuits be calculated in superposition state?
My question is that, assuming there exist a sampler $\mathtt{S}$ (probably classically efficient) takes $x\in\{0,1\}^{n}$ as input and outputs a quantum polynomial-time circuit $\mathtt{S}(x)= Q_{x}$ ...
- 21