Questions tagged [quantum-computing]
Quantum computation and computational issues related to quantum mechanics
90
questions with no upvoted or accepted answers
28
votes
0answers
483 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
291 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
512 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 ...
13
votes
0answers
302 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
277 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
263 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
220 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
251 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
229 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
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
votes
0answers
344 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
2answers
350 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 ...
7
votes
0answers
177 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
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 ...
7
votes
0answers
277 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
206 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
130 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 ...
6
votes
0answers
100 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
179 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
108 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 ...
5
votes
0answers
118 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
151 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 ...
5
votes
0answers
219 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-...
5
votes
0answers
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 ...
5
votes
0answers
190 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 ...
5
votes
1answer
131 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
69 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 ...
4
votes
0answers
241 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 ...
4
votes
0answers
106 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
76 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 ...
4
votes
0answers
184 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
200 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
85 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 ...
3
votes
0answers
109 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
173 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
208 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
55 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 ...
2
votes
0answers
179 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
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
83 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
64 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
109 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
44 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
115 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
105 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
95 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
55 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
163 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 ...
2
votes
0answers
1k views
From CHSH inequality to CHSH game
I have been going through Certifiable quantum dice: or, true random number generation secure against quantum adversaries by Umesh Vazirani and Thomas Vidick. They have used entangled particles as ...
1
vote
0answers
37 views
What type of Problems (Class and types) Can Be Solved Effectively with Quantum Computers?
The Question:
I'm trying to understand the type of problems that Quantum Computers are/will be good at solving and if there is a special class to categorizes these types of problems (e.g. Do we ...
