Questions tagged [quantum-computing]
Quantum computation and computational issues related to quantum mechanics
398
questions
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 ...
- 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 ...
- 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?
- 891
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 ...
- 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(...
- 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 ...
- 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 ...
- 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 ...
- 111
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 ...
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 ...
- 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 ...
- 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 ...
- 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 ...
- 101
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 ...
- 653
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 ...
- 36.9k
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 ...
- 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 ...
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 ...
- 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 ...
- 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$ ...
- 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 ...
- 1,058
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. ...
- 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}$ ...
- 21
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 ...
- 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 ...
- 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 ...
- 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 ...
- 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\...
- 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 ...
- 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'...
- 793
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 ...
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 ...
- 109
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 ...
- 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>$. ...
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 ...
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 ...
- 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 ...
- 1,959
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 ...
- 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 ...
- 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 ...
- 3,243
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 ...
- 3,243
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 ...
- 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 ...
- 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 ...
- 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 ...
- 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 ...
- 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. ...
- 653
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 ...
- 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 ...
- 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 ...
- 387