# Questions tagged [quantum-computing]

Quantum computation and computational issues related to quantum mechanics

408 questions
Filter by
Sorted by
Tagged with
91 views

### Classical Fourier analysis for the nonabelian hidden subgroup problem

I am hoping to disentangle some subtle distinctions between solving the hidden subgroup problem on a quantum computer and performing classical Fourier analysis on functions on groups valued in fields. ...
103 views

### On the power of QMA(2)

I searched for references. But I could not find any. Is $EXP\subseteq QMA(2)$ known?
1 vote
127 views

### Where does a problem lie which is NP-hard but not QMA-hard?

I saw this complexity classes diagram in this quantum computing paper in NATURE. Based on the standard assumption of $P\neq NP\neq QMA$, they also seem to have related the NP-hard and QMA-hard ...
• 245
148 views

### Does Rush-Hour (or Klotski) admit a search-to-decision reduction?

Consider puzzles like Rush-Hour or Klotski. When suitably generalized, such puzzles are known to be PSPACE-complete, but surely there is an interesting subclass of instances intesecting NP (and not ...
• 1,135
60 views

### How to implement the Regev's factoring algorithm on Qiskit?

I want to use the Regev algorithm to factorize 77 and demonstrate the principles of the algorithm. However, I am unsure how to construct the specific circuit. Additionally, why does the algorithm ...
472 views

### Comparing Shor's and Regev's Quantum Factoring algorithm

Regev's factoring algorithm works as follows: (Say, for factoring integer $N$; input bitsize $n$). Step I: Choose $a_1,\ ..., a_d$ small number (say, squares of first $d$ primes: (4, 9, 16, ...), ...
• 245
158 views

### Is there a 'mathematical program' to separate P from BQP?

This question has been motivated by the existence of an ongoing (and possibly long-term) program for $P\neq NP$ conjecture like GCT(Mulmuley, 1999). Usually, such programs are marked by long and ...
• 245
97 views

### Is there a Hidden subgroup problem in BQP but suspected not to be in NP?

Wikipedia lists HSP problems in abelian and non-abelian groups. So does the following (extensive) compedium. I searched and found none is a BQP-complete (or even BQP-hard) problem. There has been a ...
• 245
516 views

### Is relation between BQP and QMA resolved?

BQP vs QMA is a Quantum analogy of P vs NP. I recently went through the below pre-print on the IACR (International Association for Cryptologic Research) webpage. $BQP\neq QMA$ [link] I find it ...
• 245
245 views

### Richard Feynman says that all quantum procedures are able to be simulated by quantum computation

Richard Feynman says that all quantum procedures are able to be simulated by quantum computation，but his argument is not rigid, it seems to be a conjecture. Is there any physics/math argument ...
• 1,079
59 views

### Implications of NL $\subseteq$ BQL/poly

As far as I could see it's not known whether NL $\subseteq$ BQL/poly. Is it actually not known? If not, what would be the implications of the inclusion?
182 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,560
1 vote
160 views

### A contradiction in the realm of quantum digital and analog computation

It is a well known result that the circuit model of Quantum Computing (QC) is equivalent to the adiabatic model. Furthermore, the former is nothing more than a "slightly" more powerful ...
• 183
51 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?
• 901
88 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 ...
• 920
49 views

• 11
140 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 ...
• 478
256 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'...
• 821
1 vote
47 views

### Weak simulation of Clifford circuits

Quantum circuits composed by Clifford gates can be simulated by classical computation in polynomial time. More precisely, this simulation should be a weak simulation, i.e. it is possible to sample the ...
117 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 ...
• 109
105 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
1 vote
132 views

### Input length and calculation time to simulate a quantum measurement

Let us consider $n$ quits $b_i$. Let us start from the state $|0,0,...,0>$ and apply a circuit $C$ composed by $m$ quantum gates, with $m$ polynomial in $n$. The final state is $C|0,0,...,0>$. ...
1 vote
37 views

### Am I manipulating the content of states when I manipulate a superposition of indices?

I posted this question on quantumcomputing forum but I think maybe is more adequate to cstheory. I'm trying to understand something, I have been reading some papers about Grover's iterator, especially ...
621 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 ...
• 219
65 views

### What is known about the stabilizer rank of this simple state?

Consider the uniform superposition of all length-$n$ bit-strings of Hammming weight $w$, $$|\phi_w\rangle =\sum_{x\in \{0,1\}^n,|x|=w} |x\rangle$$ What is known or conjectured about the stabilizer ...
• 2,079
200 views

### The complexity of LH with constant gap

Kitaev's quantum equivalent of the Cook-Levin Theorem, provides a polynomial time classical reduction from a QMA verification circuit to a sum $H$ of local hamiltonians, such that the least eigenvalue ...
• 101
1 vote
263 views

### Pursuing Theoretical Computer Science after CS major

So I am currently a sophomore majoring in Computer Science. In the Data Structures course that I am currently studying, I studied the basics of complexity of a program and big O-notation, etc. That ...
• 19
1 vote
This is a follow up to Quantum complexity of TQBF, trying to model the situation where we have good heuristics. Let $L$ be the language of true, fully alternating totally quantified boolean formulas ...