Questions tagged [quantum-computing]
Quantum computation and computational issues related to quantum mechanics
90
questions with no upvoted or accepted answers
27
votes
0answers
469 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 ...
19
votes
1answer
282 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 ...
17
votes
0answers
493 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 ...
15
votes
0answers
74 views
Lower bounds for quantum circuits using the geodesic framework
(this question is a crosspost from cstheory. I've incorporated the one answer there into the question)
Some of us have been reading Michael Nielsen's paper on a geometric approach to using quantum ...
13
votes
0answers
301 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 ...
11
votes
0answers
260 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 = ...
10
votes
0answers
248 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?
10
votes
0answers
206 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 ...
10
votes
0answers
247 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 ...
10
votes
0answers
214 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 ...
9
votes
0answers
112 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
votes
0answers
338 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
0answers
158 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 ...
7
votes
0answers
63 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 ...
7
votes
0answers
264 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 '...
7
votes
0answers
195 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 \...
6
votes
0answers
96 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
0answers
175 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 ...
5
votes
0answers
122 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 ...
5
votes
0answers
98 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 ...
5
votes
0answers
129 views
Dequantumizability known and unknown?
Dequantumizable problems have been taking some headlines these days (for example https://www.scottaaronson.com/blog/?p=3880 and https://www.quantamagazine.org/teenager-finds-classical-alternative-to-...
5
votes
0answers
272 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 ...
5
votes
1answer
126 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 ...
4
votes
0answers
100 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 ...
4
votes
0answers
180 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 ...
4
votes
0answers
186 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 ...
3
votes
1answer
102 views
What are some “must-read” papers for someone getting into Quantum Cryptography?
I'm a graduate student that just finished a first course on quantum computation. I've also done a graduate-level course in (classical) cryptography.
I'm interested in Quantum Cryptography and would ...
3
votes
0answers
62 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 ...
3
votes
0answers
234 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 ...
3
votes
0answers
104 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?
3
votes
0answers
71 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 ...
3
votes
0answers
173 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 ...
3
votes
0answers
160 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 ...
3
votes
0answers
203 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 ...
2
votes
0answers
70 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 ...
2
votes
0answers
146 views
Quantum advantage beyond the black-box model
Question
Aaronson wrote in his thesis that
“essentially all quantum algorithms that we know today—from Shor’s algorithm, as discussed previously, to Grover’s algorithm, to the quantum adiabatic ...
2
votes
0answers
83 views
Quantum security of cryptosystems
One of the main candidates for PQ cryptography is code based cryptography (other than lattice based). The Niederreiter cryptosystem based on goppa codes is shown to be resistant to hidden subgroup ...
2
votes
0answers
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^{...
2
votes
0answers
74 views
Query complexity of quantum search with measuring oracle
Consider the following problem:
Let $x\in X$ be a uniformly random value.
Let $O$ be an oracle that measures whether the register $Q$ contains $x$. More precisely, $O$ measures $Q$ using the ...
2
votes
0answers
62 views
A random ensemble of sparse boundary operators
The following question arises from the study of quantum error correction, and high-dimensional expanders:
Is there an algorithm that for given numbers $n>0,d≤n,r≤n$ samples uniformly a linear ...
2
votes
0answers
158 views
Computational Complexity of cycle double cover
Let $\mathcal{G}$ be the set of all finite simple graphs. Let graph $G\in \mathcal{G}$ and $C_G=\left <C_1,...,C_m \right >$ be a sequence of cycles of $G$ for some $m$. For every edge $e$ of $G$...
2
votes
0answers
101 views
Cutting edge of quantum error correction
Often I find myself needing to know the best error correcting code for a certain quantum scenario. For example, suppose my logical systems are 3-dimensional; then what's the most efficient encoding to ...
2
votes
0answers
41 views
Non-commutative quantum counting with aggregate constant work per increment
Classically, it's very easy to create an incrementing function that can perform up to $n$ increments with $O(n)$ work:
...
2
votes
0answers
119 views
On FFT and trigonometric matrix eigenvalues
Let $N=2^n$ for a natural number $n$ and $B$ be the $N\times N$ square matrix of $0$'s and $1$'s
$$
B=\begin{pmatrix}
0 & 1 & 0 & \ldots & 0 \\
1 & 0 & 1 & \ldots ...
2
votes
0answers
158 views
Quantum computer versus Random 3-SAT?
It seems to be commonly believed that quantum computer cannot efficiently solve NP-hard problems. What about the challenging problems in average-case, such as Planted Clique and Random 3-SAT?
2
votes
0answers
108 views
Why hidden subgroup problem is easy for very large subgroup?
I am going through QUANTUM MECHANICAL ALGORITHMS FOR THE
NONABELIAN HIDDEN SUBGROUP PROBLEM by Grigni et al. On page 2, it is said that solving the hidden subgroup problem becomes very easy when the ...
2
votes
0answers
102 views
Claw finding using quantum walk: superposition for Szegedy's framework
Within Claw Finding Algorithms Using Quantum Walk there is the subroutine $claw_{detect}$ described. As in above paper:
Let $J_f(N, l)$ and $J_G(M, m)$ be Johnson graphs. Let $F$ and $G$ be vertices ...
2
votes
0answers
94 views
Proofs to verify quantum states without revealing their description
Consider the following function $$f_s: k \rightarrow \lvert \psi_k \rangle$$
where $s,k$ are bit strings, and $\lvert \psi_k \rangle$ is a $n$-qubit state.
Assume the function is a one-to-one mapping....
2
votes
0answers
53 views
How the errors of the measured quantities of an adiabatic Hamiltonian are inversely proportional to the square root of the number of measurements?
I am going through the paper, Solving the graph-isomorphism problem with a quantum annealer, by Hen et. al. In the last line of the second paragraph of the second column of page 2, it says,
Since ...
2
votes
0answers
158 views
Quantum algorithm of graphs: How to create superposition of paths?
Let us allow path to have same vertexes in it. (defining)
So suppose we have a graph of $N$ vertexes and we want to separate it into some superposition of paths that have $N$ vertexes (so if the ...
