Questions tagged [quantum-computing]
Quantum computation and computational issues related to quantum mechanics
398
questions
2
votes
1
answer
146
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}$ ...
CommunityBot
- 1
0
votes
1
answer
323
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 ...
CommunityBot
- 1
6
votes
0
answers
173
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 ...
- 24.3k
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 ...
- 910
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(...
- 849
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 ...
- 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 ...
- 24.3k
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
-2
votes
1
answer
220
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 ...
- 1,063
22
votes
3
answers
8k
views
Oracle Construction for Grover's Algorithm
In Mike and Ike's "Quantum Computation and Quantum Information", Grover's algorithm is explained in great detail. However, in the book, and in all explanations I have found online for Grover's ...
- 1
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 ...
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
5
votes
2
answers
307
views
Witness verifiable quantum advantage
Update: A slightly different version of this question has been answered here.
As far as I can see, a major issue with Google's recent quantum supremacy claim is that it is hard to verify the results.
...
- 1,063
8
votes
3
answers
623
views
Is the wording of Google's QC Supremacy valid?
Quantum supremacy using a programmable superconducting processor was published today. Scott Aaronson posted a few weeks ago a post about this paper and it was clear we will see a Nature or Science ...
- 141
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 ...
- 135
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
336
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
8
votes
0
answers
201
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
7
votes
1
answer
262
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 ...
- 723
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 ...
17
votes
1
answer
397
views
Which results make quantum space interesting?
Time-bounded quantum computation is obviously very interesting. What about space-bounded quantum computation?
I know many interesting results for quantum computation with sublogarithmic space bounds ...
- 357
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
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
6
votes
1
answer
522
views
How efficiently can a 1-sparse Hamiltonian be simulated (quantum mechanically)?
In quantum computation there is a fair amount of interest in the task of simulating quantum physics. One instance of this is the problem of simulating the evolution of a system under the action of ...
- 357
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
4
votes
1
answer
759
views
String theory based computations
I was reading Arora and Barak's book on computational complexity and in the section on 'criticism on Turing machine model and the class P' along with quantum computer it also mentions possibilities of ...
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
13
votes
0
answers
668
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
3
votes
1
answer
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 ...
- 24.3k
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
128
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
8
votes
3
answers
513
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 ...
- 960
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 ...
6
votes
0
answers
293
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-...
- 541
5
votes
0
answers
121
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 ...
- 541
5
votes
0
answers
186
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 ...
- 541
3
votes
0
answers
108
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 ...
- 541
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 ...
15
votes
0
answers
118
views
Lower bounds for quantum circuits using the geodesic framework [duplicate]
Some of us have been reading Michael Nielsen's paper on a geometric approach to using quantum lower bounds (in brief, the construction of a Finsler metric on $SU(2^n)$ such that the geodesic distance ...
- 541
42
votes
2
answers
6k
views
Do any quantum algorithms improve on classical SAT?
Classical algorithms can solve 3-SAT in $1.3071^n$ time (randomized) or $1.3303^n$ time (deterministic). (Reference: Best Upper Bounds on SAT )
For comparison, using Grover's algorithm on a quantum ...
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
2
votes
2
answers
2k
views
Is quantum annealing faster than simulated annealing/genetic/other state-of-the-art optimization algorithms?
There's the idea of quantum annealing being used to solve optimization problems in terms of a QUBO problem for D-Wave's quantum algorithm. I understand that the advantage of quantum annealing as ...
- 1
26
votes
5
answers
966
views
Universal sets of gates for SU(3)?
In quantum computing we are often interested in cases where group of special unitary operators, G, for some d-dimensional system gives either the whole group SU(d) exactly or even just an ...
CommunityBot
- 1
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>$. ...