Questions tagged [quantum-computing]

Quantum computation and computational issues related to quantum mechanics

Filter by
Sorted by
Tagged with
3
votes
1answer
62 views

What is 'circuit problem' mentioned in Kempe-Kitaev-Regev's local hamiltonian problem paper

I have been going through Kempe-Kitaev-Regev's paper The Complexity of the Local Hamiltonian Problem. In the first paragraph of page 3, the authors point out that: To the best of our knowledge, ...
2
votes
0answers
63 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 ...
10
votes
0answers
213 views

Does MIP* = RE algebrize?

Does the MIP* = RE result algebrize? (It doesn’t relativize, as noted here.) If it doesn’t algebrize, is there a more complicated similar notion that it does satisfy?
1
vote
1answer
212 views

Quantum Computing: project ideas

I'm an undergraduate computer science student and I'm currently taking a course in the field of quantum computing requiring projects. I've read already a huge number of articles but still cannot come ...
0
votes
3answers
228 views

What would be the next step after quantum computing? [closed]

Is their anything that would make Quantum computing obsolete in the future? I know a Matrioksha Brain is the most powerful theoretical computer; but it probably won’t ever be realized. Too large and ...
5
votes
1answer
118 views

Complexity of finding automorphism group of code

What is the computational complexity (may be both classical or quantum) for finding automorphism group of a general linear code? Is there better bound on complexity if structure of code is known for ...
4
votes
1answer
213 views

Are there problems that can be solved in time $2^{n-q^c}$ with $q$ qubits?

This is another attempt to formalize my former question on the topic. I'm looking for a problem for which all known classical algorithms take exponential time, but given ANY number of few qubits (...
4
votes
0answers
148 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. ...
7
votes
1answer
383 views

Quantum Money where not even the Bank can counterfeit

The Quantum Money system proposed in "Quantum Copy-Protection and Quantum Money" has the following properties: The bank can produce bank notes in the form of quantum states. Anyone can verify that ...
5
votes
1answer
212 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
119 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 ...
2
votes
0answers
126 views

Quantum advantage beyond the black-box model

Question Aaronson wrote in his thesis that “essentially all quantum algorithms that we know today—from Shor’s algorithm, as discussed previously, to Grover’s algorithm, to the quantum adiabatic ...
8
votes
3answers
522 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 ...
4
votes
1answer
200 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?$$
20
votes
2answers
669 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
42 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
76 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
141 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
326 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
72 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 ...
2
votes
1answer
62 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/...
9
votes
3answers
459 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
130 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))]}$ ...
8
votes
1answer
279 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$. $\...
3
votes
0answers
126 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 ...
3
votes
1answer
193 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
91 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
119 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 ...
11
votes
5answers
1k 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 ...
-1
votes
1answer
63 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
71 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
0answers
69 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
180 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 ...
3
votes
0answers
60 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 ...
10
votes
1answer
233 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 ...
1
vote
1answer
84 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
392 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 ...
1
vote
2answers
209 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 ...
10
votes
0answers
244 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 ...
2
votes
0answers
978 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
1answer
138 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,...
1
vote
1answer
89 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 = ...
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
131 views

Is $CAPP \in P$ known to collapse some quantum complexity classes to classical ones?

Lets define the class $ZBQP = \{ L \mid \exists \textit{P-uniform circuit family } \{C_i\}, \forall n \in \mathbb{N}, |x| = n, |\langle 0|C_n|x \rangle - I(x \in L)| \leq 9/10 \Longleftrightarrow x \...
1
vote
0answers
68 views

Query complexity of quantum search with measuring oracle

Consider the following problem: Let $x\in X$ be a uniformly random value. Let $O$ be an oracle that measures whether the register $Q$ contains $x$. More precisely, $O$ measures $Q$ using the ...
1
vote
0answers
134 views

QUBO formulation of a discrete-variable optimization problem

I am facing a non-linear, discrete optimization problem, which I can formulate in this abstract manner: I have a certain non-analytic non-linear real-valued function $f:S \to \mathbb{R}$ which takes ...
1
vote
0answers
64 views

What is the average sensitivity of a quantum circuit with depth $d$ and size $s$?

We have some quantum circuit $C$ with $k$ ancillae and $n$ input bits of depth $d$ and size $s$, and we can define a function $f$ which, for any $x \in \{0, 1\}^n$, is the random variable which is the ...
-2
votes
1answer
147 views

Complexity class on quantum computation and classic ones

Does the complexity speedup in superpolynomial by quantum computation mean it is possible to find new algorithm on classic Turing Machine which can speedup in classic Turing Machine in ...

1
2 3 4 5
7