Questions tagged [quantum-computing]

Quantum computation and computational issues related to quantum mechanics

90 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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 ...