Questions tagged [quantum-computing]

Quantum computation and computational issues related to quantum mechanics

Filter by
Sorted by
Tagged with
7 votes
1 answer
305 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, ...), ...
108_mk's user avatar
  • 225
4 votes
0 answers
141 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 ...
108_mk's user avatar
  • 225
0 votes
0 answers
83 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 ...
108_mk's user avatar
  • 225
6 votes
1 answer
424 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 ...
108_mk's user avatar
  • 225
-3 votes
1 answer
220 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 ...
XL _At_Here_There's user avatar
0 votes
0 answers
55 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?
eunice.goudarzi's user avatar
6 votes
0 answers
178 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 ...
Timothy Chow's user avatar
  • 7,550
1 vote
1 answer
148 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 ...
Marion's user avatar
  • 183
2 votes
0 answers
43 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?
ivmihajlin's user avatar
2 votes
0 answers
82 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 ...
Ilk's user avatar
  • 920
2 votes
1 answer
45 views

Could an *implicitly* defined graph be a member of a *strongly-explicit* family of expanders?

There seems to be a slight difference in terminology among a couple of different traditions within theoretical computer science. To have a quantum computer simulate the Hamiltonian evolution of $\exp(...
Mark S's user avatar
  • 1,083
4 votes
1 answer
163 views

On the plausability of quantum RAM

I'm fairly new to quantum computation and quantum complexity theory, but I came across some articles that suggest that quantum RAM (QRAM) is not very realistic assumption. For example some works show ...
terett's user avatar
  • 151
-2 votes
1 answer
247 views

What is the reason to believe that quantum heuristic algorithms can solve NP-Complete problems?

There is an ever going trend to believe that a large number of NP-Complete or NP-Hard problems can be solved using quantum heuristics. I have observed, a common trend, to take any sort of ...
Marion's user avatar
  • 183
1 vote
0 answers
50 views

Oracle for the permanent-of-gaussians problem

In this paper, Aaronson and Arkhipov formulate the $GPE_\times$ problem as follows: given an $n \times n$ matrix $X$ of i.i.d. Gaussian random numbers, find the permanent of $X$ up to multiplicative ...
Alexey Uvarov's user avatar
0 votes
0 answers
35 views

Is SZK dependent on the verifier’s model of computation?

What if instead of a probabilistic TM, the verifier in the definition of SZK was a quantum TM? How would this affect its relation to other classes? Would Statistical Difference still be a complete ...
Irna Mosa's user avatar
5 votes
0 answers
88 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 ...
Mark S's user avatar
  • 1,083
3 votes
0 answers
28 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 ...
vk19's user avatar
  • 31
2 votes
0 answers
69 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 ...
SAS's user avatar
  • 121
1 vote
0 answers
472 views

Is it known that P $\neq$ NP implies BQP $\neq$ NP?

Pretty much the title. Is there any result that shows that $P \neq NP \Rightarrow BQP \neq NP$. I think it's pretty clear that $BQP \neq NP \Rightarrow P \neq NP$, as $P$ is a subclass of $BQP$. But ...
Loic Stoic's user avatar
0 votes
1 answer
57 views

Impact HHL caveat relaxation on quantum advantage

We know that there are four caveats for the exponential speedup proven for the HHL algorithm. Could anyone answer how that exponential speedup evolves as we relax the caveats? For example, the ...
Omar Shehab's user avatar
4 votes
0 answers
59 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 ...
Joshua Grochow's user avatar
0 votes
0 answers
41 views

Computability for universal quantum turing machines

I would like to ask if anyone has any ideas about what a universal quantum turing machine (UQTM) can do as supposed to a classical universal turing machine (UTM) (i.e. quantum computer vs classical ...
Shane Gervais's user avatar
1 vote
0 answers
369 views

Claimed proof of PSPACE ⊆ BQP on arXiv

A new paper appeared on arxiv: PSPACE ⊆ BQP by Shibdas Roy: https://arxiv.org/abs/2301.10557 From the abstract: The complexity class PSPACE includes all computational problems that can be solved by a ...
kodlu's user avatar
  • 2,070
7 votes
1 answer
270 views

How do separations in of query complexities imply complexity class separations relative to oracles?

Simon's problem is the following: Given oracle access to a Boolean function $f: \{0,1\}^n\rightarrow \{0,1\}^n$, and promised that precisely one of the following two cases is true, decide which of ...
gen's user avatar
  • 260
0 votes
0 answers
122 views

Can an NP-search problem be defined non-constructively?

Given a random two-to-one function $f(x)$ from $n$ bits to $n$ bits, consider the following search problem: Find a polynomial number of pairs $(d,y)\in \{0,1\}^n\times\{0,1\}^n$ with $d\ne \bf 0$ ...
Mark S's user avatar
  • 1,083
0 votes
2 answers
396 views

Is it proved that error rate of quantum computation is bounded by constant rather than a function dependent on time and environment by quantum theory

Anyone has proved the error rate of quantum computation is bounded by (less than) a constant rather than a function dependent on time and environment by quantum theory? For error rate and error ...
XL _At_Here_There's user avatar
3 votes
0 answers
118 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. ...
Mark S's user avatar
  • 1,083
3 votes
1 answer
162 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}$ ...
Cao Shuajiao's user avatar
2 votes
0 answers
100 views

Survey of Quantum Algorithms similar to Montanaro's from 2015

The survey https://arxiv.org/abs/1511.04206 by Montanaro is very nice in terms of giving a bird's eye view, which is very useful. As the author states in the abstract Here we briefly survey some ...
kodlu's user avatar
  • 2,070
8 votes
0 answers
203 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 ...
Gil Kalai's user avatar
  • 6,033
13 votes
0 answers
688 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 ...
Hhan's user avatar
  • 261
0 votes
1 answer
86 views

Vidick's proof of parallel DI-QKD

This question is based on the paper- https://arxiv.org/abs/1703.08508. As far as I understand, for this proof Vidick uses a quantum parallel repetition for 3 player- Alice, Bob and Eve but the results ...
Noel's user avatar
  • 101
1 vote
0 answers
46 views

Quantum Communication Complexity Bound on Vector Inner Product

Say Alice has a (complex) vector $a\in\mathbb{C}^d$, and interacts with Bob in a quantum communication protocol (sending qubits back and forth). At the end of the protocol, Bob produces a guess $b\in\...
Yang's user avatar
  • 11
4 votes
0 answers
135 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 ...
J.Doe's user avatar
  • 468
3 votes
0 answers
249 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'...
TheoryQuest1's user avatar
1 vote
0 answers
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 ...
Doriano Brogioli's user avatar
0 votes
0 answers
116 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 ...
VenomFangs's user avatar
3 votes
0 answers
99 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 ...
AngryLion's user avatar
  • 173
1 vote
0 answers
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>$. ...
Doriano Brogioli's user avatar
1 vote
0 answers
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 ...
Julio César JX's user avatar
8 votes
3 answers
565 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 ...
CSSTUDENT's user avatar
  • 219
2 votes
0 answers
63 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 ...
Lieuwe Vinkhuijzen's user avatar
3 votes
3 answers
197 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 ...
J.Ask's user avatar
  • 101
1 vote
1 answer
259 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 ...
eipim1's user avatar
  • 19
1 vote
1 answer
137 views

Quantum complexity of TQBF with an untrusted oracle

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 ...
Geoffrey Irving's user avatar
7 votes
1 answer
202 views

Quantum complexity of TQBF

There is no classical algorithm for $n$-bit TQBF with better than $O(2^n)$ complexity. Is that also the best known bound for quantum algorithms / circuits? Edit: As pointed out by Huck Bennett, in ...
Geoffrey Irving's user avatar
8 votes
1 answer
165 views

What are the general direction and target question in the field of quantum error correction?

After quantum error correction was introduced in mid '90s, in subsequent years many of the classical analogues regarding the structure of code (such as singleton bound, GV bound etc) were obtained in ...
Root's user avatar
  • 387
4 votes
1 answer
237 views

Survey on Quantum error correction

Are there any standard recent survey articles on quantum error correction (and may be including fault Tolerant computing)? The most standard ones that many people refer to are this and this. Both of ...
Root's user avatar
  • 387
6 votes
1 answer
275 views

Are all computational models of quantum computing equivalent?

So the question was inspired by a seminar which presented the following models of quantum computing: Quantum Computing with Photons Quantum Computing with Rydberg atoms Quantum Computing with trapped ...
SagarM's user avatar
  • 716
1 vote
0 answers
58 views

Does the approximatibility of individual gates together with unitarity imply BPP=BQP

Suppose you can prove upper bounds on errors from approximating an individual quantum gate by randomly hashing the qubits of a circuit to a polylog number of qubits. (So, you prove a bound on how much ...
botsina's user avatar
  • 101

1
2 3 4 5
9