Questions tagged [quantum-computing]

Quantum computation and computational issues related to quantum mechanics

Filter by
Sorted by
Tagged with
6 votes
0 answers
172 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,465
1 vote
1 answer
140 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
39 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
78 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
  • 900
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,063
4 votes
1 answer
148 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
219 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
48 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
84 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,063
3 votes
0 answers
27 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
65 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
0 votes
1 answer
322 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
54 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
53 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
102 views

Quantum END OF THE LINE Representation?

The complexity class PPAD is heavily based on the problem END OF THE LINE. However, it is unclear how to represent this problem on a quantum computer; i.e. the graph representation of having two ...
Steven's user avatar
  • 1
0 votes
0 answers
38 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
335 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
261 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,063
0 votes
2 answers
376 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
117 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,063
2 votes
1 answer
133 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
95 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
200 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,013
13 votes
0 answers
666 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
84 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
45 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
127 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
237 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
111 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
96 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
131 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
511 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
59 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
189 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
254 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
135 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
196 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
162 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
224 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
270 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
  • 706
1 vote
0 answers
57 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
2 votes
0 answers
109 views

Can hash functions speed up quantum simulation? (Generalizing May and Schlieper's idea) [closed]

To conform with the CS Theory SE crossposting rules, I've created a separate post for dequantizing Shor's algorithm (discussion on the Quantum Computing Stack Exchange was mostly about Shor's ...
botsina's user avatar
  • 101
1 vote
0 answers
60 views

Gate definitions for quantum random access codes

I would like to know how the gates are defined in quantum random access codes? Consider the $2 \to 1$ code described in Lemma 3.1 of this paper. The section defines the encoding and decoding circuits. ...
Omar Shehab's user avatar
7 votes
0 answers
201 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 ...
Mark S's user avatar
  • 1,063
-2 votes
1 answer
184 views

What evidences are there that $PP$ is in $BQP$ and $PP$ is not in $BQP$?

Unlike hierarchy collapse arguments for classical complexity we have that quantum complexity is different. What evidences are there that $PP$ is in $BQP$? What evidences are there that $PP$ is not ...
Turbo's user avatar
  • 12.8k
1 vote
0 answers
54 views

Non-rigid isomorphic structures

In many of the problems trying to solve hidden shift over some objects like graphs mainly the rigid classes are considered. For eg. in this and this isomorphism problem restricted over rigid graphs is ...
Root's user avatar
  • 387

1
2 3 4 5
8