Questions tagged [quantum-computing]
Quantum computation and computational issues related to quantum mechanics
337
questions
-4
votes
0answers
56 views
An algebro-combinatorial argument that P = NP [on hold]
Also asked in normal CS stack exchange.
I have long been fascinated by this question and recently wrote an article about it. The version of computation described in the article is similar to those ...
3
votes
1answer
167 views
Qubit gates in google supremacy
The gates in quantum supremacy experiment are nearest-neighbor and have spatial locality. Would this additional information help bolster IBM's argument to perhaps simulate quantum supremacy experiment ...
1
vote
1answer
103 views
How exactly is solving the random circuit sampling problem a computation in the Church-Turing thesis sense? [closed]
Note: This has been cross-posted to Quantum Computing SE.
If we assume $\mathsf{BQP} \neq \mathsf{BPP}$, then we can say with reasonable certainty that Google's random sampling experiment falsifies ...
8
votes
3answers
435 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 ...
2
votes
0answers
60 views
Quantum advantage beyond the black-box model
The common quantum algorithms I know of can be all explained using black-box model (i.e., query model):
Grover's search. An $O(\sqrt{n})$-query algorithm that computes the OR of $n$ bits.
Shor's ...
4
votes
1answer
181 views
Results comparing BQP and NEXP
Are there oracle results with $$P=NP\neq BQP=NEXP\mbox{ and }P=NP\neq BQP\neq NEXP?$$
Also is there a $PCP$ characterization of $BQP$ like $$PCP(O(poly(n)),1)=PCP(O(poly(n)),O(poly(n)))=NEXP?$$
15
votes
1answer
379 views
Oracular separations between poly- and log-depth quantum circuits
The following problem appears in Aaronson's list Ten Semi-Grand Challenges for Quantum Computing Theory.
Is $\mathsf{BQP}=\mathsf{BPP}^{\mathsf{BQNC}}$ In other words, can the "quantum" part of any ...
10
votes
2answers
455 views
PPAD and Quantum
Today in New York and all over the world Christos Papadimitriou's birthday is celebrated. This is a good opportunity to ask about the relations between Christos' complexity class PPAD (and his other ...
0
votes
0answers
39 views
Hidden subgroup problems in a tower of subgroups
Let $H$ be a hidden subgroup of $G_1$ that is indistinguishable from subgroup $H^{\prime}$ by quantum Fourier sampling. Now take a larger group $G_2$ such that it contains $G_1$. Now if I do quantum ...
2
votes
0answers
71 views
Quantum security of cryptosystems
One of the main candidates for PQ cryptography is code based cryptography (other than lattice based). The Niederreiter cryptosystem based on goppa codes is shown to be resistant to hidden subgroup ...
3
votes
1answer
134 views
Given a subset of of the hypercube and an affine transform of it, find the affine map
This is a follow up to this resolved question.
Suppose we are given a set of bitvectors $A\subseteq\mathbb{F}_2^d$ and an invertible affine transformed copy of it
$$B=\{Mx + s\mid x\in A\}$$
for some ...
7
votes
2answers
319 views
Given a subset of the hypercube and a copy translated by s, find s
Problem: Suppose we are given an $n$ element subset $A\subseteq\{0,1\}^d$ of the $d$ dimensional hypercube and a translated copy $B= A+s$ by some secret $s\in\{0,1\}^d$. Find $s$ as fast as possible ...
0
votes
1answer
68 views
Grover's algorithm, M out of N, when M is large
The more general version of Grover's algorithm searches for one of $M$ entries that match a criterion, out of $N$ total entries.
I have seen it written that this takes $O(\sqrt{N/M})$ iterations, to ...
1
vote
1answer
58 views
QPIP minimal client quantum capabilities
It is conjectured that classical (BPP) client blind quantum computing is implausible according to Aaronson et al:
https://www.researchgate.net/publication/...
8
votes
1answer
264 views
Is there any quantum analog of the VP vs. VNP problem?
From Wikipedia:
$\mathsf{VP}$: The class VP is the algebraic analog of P; it is the class of polynomials $f$ of polynomial degree that have polynomial size circuits over a fixed field $K$.
$\...
8
votes
3answers
426 views
Why exactly are complexity theorists interested in closed timelike curves?
Context:
There are several papers that study the implications of closed timelike curves (CTCs) to quantum complexity. In 2008, Aaronson and Watrous published their famous paper on this topic which ...
2
votes
1answer
127 views
Lower bound on alternations needed in $BQP$ versus $PH$ result?
What is the fastest $f(n)$ the relatively new result of oracle separation of $\mathsf{BQP}$ from $\mathsf{PH}$ provides such that ${\#\mathsf{SAT}}\not\subseteq\mathsf{FP}^{\mathsf{PH}[O(f(n))]}$ ...
11
votes
5answers
886 views
List of quantum-inspired algorithms
Advances in quantum computing have led to the development of new classical algorithms. Notable recent examples are quantum-inspired algorithms for linear algebra:
A quantum-inspired classical ...
3
votes
0answers
119 views
What can be some bachelor thesis ideas in Quantum random walks?
Note: Cross-posted on Quantum Computing Stack Exchange.
I am an undergraduate, reading about quantum information and quantum technology. For about some time, I have been interested in the ...
11
votes
2answers
467 views
Notation for a Conditional Hamiltonian Evolution Operator
I am reading Harrow, Hassidim, and Lloyd's paper Quantum algorithms for linear systems of equations. On the third page of that paper, they write
Next we apply the conditional Hamiltonian evolution $...
3
votes
0answers
194 views
In light of Raz and Tal's results, what can we say about whether there's a BQP problem for each level of the polynomial hierarchy?
[cross-posted on QCSE a couple of weeks ago]
Every Venn diagram or Hasse diagram I see illustrating the "standard model" of computational complexity describes a universe of $\mathsf{PSPACE}$ problems,...
3
votes
1answer
178 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 ...
4
votes
0answers
89 views
Is there a universal gate set for classical probabilistic computing?
We know that NAND gates are universal for deterministic classical circuits, Toffoli gates are universal for reversible deterministic classical circuits, and Clifford+T is universal for quantum ...
4
votes
0answers
116 views
Dequantumizability known and unknown?
Dequantumizable problems have been taking some headlines these days (for example https://www.scottaaronson.com/blog/?p=3880 and https://www.quantamagazine.org/teenager-finds-classical-alternative-to-...
1
vote
0answers
21 views
whether two sets of stabilizer generators are related by a Clifford circuit
I have two stabilizer models each specified with a given set of generators. Let's call the two generating sets $S_1$ and $S_2$. By stabilizer model, I mean putting the generators on unit cells of a ...
76
votes
7answers
41k views
What would a very simple quantum program look like?
In light of the announcement of the world's first programmable quantum photonic chip, I was wondering just what software for a computer that uses quantum entanglement would be like. One of the first ...
-1
votes
1answer
56 views
QMA definition of difference between probabilities intuition
I'm reading about the complexity classes related to quantum computation, currently I'm studying QMA class. A language is in QMA(c,s) if there exists a polynomial time verifier and polynomial $p(n)$ ...
1
vote
0answers
701 views
BQNC and Abelian Hidden Subgroup Problem
We know integer factorization is in $BPP^{BQNC}$ from Cleve and Watrous.
Is Abelian Hidden Subgroup Problem also in $BPP^{BQNC}$?
In particular is Discrete Logarithm in $BQNC$ or at least in $BPP^{...
1
vote
0answers
70 views
Complexity of enumerating over promise problems and circuits?
Given an enumeration over all Turing Machine which run with increasing length, is there a ``complexity class'' which describes the complexity of determining whether a given TM satisfies the promise ...
1
vote
3answers
280 views
Why is finding the ground state of a Hamiltonian in QMA?
Why is finding the ground stte of a Hamiltonian in QMA?
It's in QMA to figure out if a hamiltonian has any energy eigenvalue within a certain window range which is at least inverse polynomial in size....
1
vote
0answers
67 views
Complexity class of approximating perfect match count
We know we can approximate perfect matching count of bipartite and approximate volume of convex bodies in randomized polynomial time.
Is there any evidence these approximations could be in Nick's ...
9
votes
0answers
168 views
Relatively low ambitious frontiers
What are some of the current "relatively" low ambitious frontiers for MA/PhD thesis in complexity theory class separations/containment or quantum computing?
For example: In the draft version of Arora ...
6
votes
0answers
96 views
Efficient quantum algorithm for CLASSICAL FFT
Is there a known improvement on the current O(n*log(n)) algorithm for CLASSICAL FFT using quantum computation? 'n' is the number of samples.
I need to find the amplitude and phase of the K dominating ...
1
vote
2answers
207 views
Which cryptographic protocols are secure against quantum computer attacks?
Are there any cryptosystems that we know that would be secure against an attack by a quantum computer?
Are there problems which are known or suspected to be hard for quantum computers, and can these ...
3
votes
0answers
57 views
Hardness of ancilla free quantum circuit extraction from circuit with ancillas
Is there any known result regarding the hardness of the following problem:
Given a quantum circuit with ancillae implementing a unitary, find a quantum circuit that does not use any ancillae that ...
9
votes
1answer
241 views
Is there a candidate for a post-quantum one-way group action?
Is there a known family of group actions with a designated element
in the set that is being acted on, where it is known how to efficiently
$\:$ sample (essentially uniformly) from the groups, ...
10
votes
1answer
223 views
Fast classical simulation of quantum algorithms
Are there examples of cases where the classical simulation of a quantum algorithm for a problem outperforms the best previously known classical algorithm for this problem? "Outperforms" doesn't have ...
6
votes
1answer
740 views
Analytic solutions in semidefinite programming (SDP)
From my experience in the application of semidefinite programming (SDP) to quantum information, I have learnt that the solution to an SDP can sometimes be expressed as an analytic formula. For example,...
1
vote
1answer
82 views
Quantum circuit simulation divergence in results
I'm learning about quantum computing in order to code a simulator. I tried the following circuit in Quirk
And ran the same circuit using OPENQASM 2.0:
Notice that the input is |11> in both cases, ...
5
votes
1answer
367 views
Can one do quantum computing without negative amplitudes?
The typical representation I see of $k$ qubits is a $2^k$ complex numbers $c_i$ for every possible combination of values of those bits, such that the sum of all the squared magnitudes of those numbers ...
19
votes
1answer
532 views
Problems in BQP but conjectured to be outside P
Wikipedia listed four problems that are in $BQP$ but conjectured to be outside $P$: Integer factorization; Discrete logarithm; Simulation of quantum systems; Computing the Jones polynomial at certain ...
1
vote
1answer
136 views
Complement for joint POVMs?
I'm trying to relate some notions of set theory to POVMs. I firstly explain the scenario with set theory and then in the POVM setting.
For some finite $N \in \mathbb{N}$, let $A_i$ and $B_i$ for $i=1,...
3
votes
1answer
141 views
Papers on using resource states to implement QFT efficiently
I recently stumbled onto the idea of using a pre-existing re-usable phase gradient to implement the QFT, instead of having to keep re-applying exponentially precise phase gates. I'm looking for papers ...
9
votes
0answers
231 views
How would proof of the Lindelöf hypothesis improve our understanding of computational complexity classes?
A recent press release from the Viterbi School of Engineering at USC discussed the proof of the Lindelöf hypothesis by Athanassios Fokas, a visiting professor from the Department of Applied ...
18
votes
7answers
25k views
Universities for Quantum Computing / Information?
Which universities have a strong quantum computing curriculum, and offer some type of quantum computing/information courses/research?
The aim here is to collect a useful list for someone considering ...
11
votes
2answers
761 views
Problems with no known quantum advantage
I was wondering what the list of current natural computational problems is for which there is no known complexity advantage in using a quantum computer.
To start things off, I think computation of ...
0
votes
1answer
183 views
What would be a complete QC circuit?
In classical computing NAND is a complete set (functionally complete) of binary operations, namely any Boolean circuit can be expressed using NAND gates.
Is there an equivalent for quantum computing ...
1
vote
1answer
84 views
PromiseBQP and expectation values of operators
This question is regarding The Equivalence of Searching and Sampling by Aaronson. In page 4 he makes the following statement,
... a difficult and unsolved meta-question is whether PromiseBPP = ...
7
votes
2answers
1k views
Applications of Quantum Walks?
Can someone explain to me what real world applications could potentially benefit from the study of quantum random walks?
I have researched a fair amount on how quantum walks operate and their ...
4
votes
6answers
5k views
Ternary (and beyond) computation and quantum computing?
Binary math is at the heart of most computing, in large part because of the ease with which two energy states can be achieved. I have always thought that having more states could improve computing ...
