Questions tagged [quantum-computing]
Quantum computation and computational issues related to quantum mechanics
-1
votes
0answers
76 views
4
votes
0answers
73 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 ...
-1
votes
0answers
27 views
Power of one step transition of a QTM
So in defining a quantum Turing machine, we have transition as below:
$$
\delta:Q\times \Gamma\rightarrow \mathbb{C'}^{Q\times \Gamma\times\{L,R,0\}}
$$
Where $\mathbb{C}'\subseteq\mathbb{C}$ is a ...
3
votes
0answers
106 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 ...
8
votes
4answers
353 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
44 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
68 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
62 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
153 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
95 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
52 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
205 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
79 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
336 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
202 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 ...
9
votes
0answers
206 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 ...
1
vote
0answers
218 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
132 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
77 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
178 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
123 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
65 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
110 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
56 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
136 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 ...
6
votes
1answer
194 views
Quantum polynomial hierarchy vs counting hierarchy
First of all, I'm kinda surprised that I couldn't find any paper/article defining such hierarchy.
It can be defined as follows:
$\Delta_0^{\mathsf{BQP}}=\Sigma_0^{\mathsf{BQP}}=\Pi_0^{\mathsf{BQP}}=\...
-2
votes
2answers
243 views
How can I get $\sum_n e^{i a_n} |n\rangle$ from $\sum_n a_n |n\rangle$?
Suppose that I have a normalized quantum state $\sum_n a_n |n\rangle$, is there a quantum operation/circuit so that I can get $\frac{1}{N} \sum_n e^{i a_n} |n\rangle$ at output? How?
1
vote
0answers
95 views
Is there a way to extract the mean from a quantum superposition?
Given the superposed output of some quantum computation, suppose I want to know the mean state, i.e. the mean probability of each qubit sampled over all states.
The most obvious way to get this is ...
1
vote
0answers
114 views
Connection between diamond norm and output purity norm
Setting of the problem: Given a quantum channel $\mathcal{E}: \mathcal{H}_A\rightarrow \mathcal{H}_B$ (where $\mathcal{H}$ refers to a Hilbert space and subscript refers to the quantum register ...
2
votes
0answers
59 views
A random ensemble of sparse boundary operators
The following question arises from the study of quantum error correction, and high-dimensional expanders:
Is there an algorithm that for given numbers $n>0,d≤n,r≤n$ samples uniformly a linear ...
10
votes
1answer
3k 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
vote
1answer
366 views
What would a quantum computer architecture look like? [closed]
More specifically, assuming we manage to make an efficient quantum switch, some kind of "quansistor"(quantum transistor) and manage to resolve the problem of joining a bunch of them together without ...
3
votes
0answers
220 views
Convexity argument in QMA Amplification
I'm interested in the basic amplification procedure for QMA: the prover sends $O(r)$ copies of his witness to the verifier, which decreases the error probability to $2^{-O(r)}$ (Chernoff bound). The ...
2
votes
1answer
259 views
Simulating quantum measurements by unitaries
I have seen many papers in which quantum measurements are assumed to be replaced by unitaries. See this quotation from [KW00] for instance:
Often we will describe quantum circuits in a high-level ...
1
vote
1answer
75 views
Finding a basis for quantum measurement with maximum distinguishability
I wish to find a basis state for the quantum measurement of two states which provides the maximum possible distinguishability. In this example let's say we wish to find the best basis ($|\psi\rangle$) ...
3
votes
2answers
398 views
Numerical accuracy of superpositions in quantum computers
I am new to the topic of quantum computers (though I am very familiar with both quantum and computers, and I have studied Shor's paper about his eponymous algorithm at some point). Still, I have the ...
5
votes
1answer
168 views
general statement what kinds of problems can be solved more efficiently
is there a general statement what kinds of problems can be solved more efficiently using quantum computers (quantum gate model only)? do the problems for which an algorithm is known today have a ...
5
votes
1answer
713 views
When can be used the “uncompute garbage” trick in quantum computing?
As far as I have understood, "uncomputation" in quantum computing is a way to restore the working memory to its initial state, while keeping the result of the computation in another register. This ...
1
vote
1answer
83 views
Running multiple rounds of a BQP computation, without multiple measurements? [closed]
BQP as usually defined is: the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances.
Just like BPP, the choice of 1/...
2
votes
1answer
146 views
Is graph automorphism Karp-reducible to graph isomorphism under hidden subgroup representation?
The classical representations of the graph automorphism problem is Karp-reducible to the classical representation of the graph isomorphism problem. The sketch of proof for this can be written as ...
1
vote
0answers
75 views
How to simulate the quantum measurement of a quantum state in Quantum Image
I'm trying to implement (simulate) the Novel Enhanced Quantum Representation (NEQR), which is one of the quantum image representation models, but i'm stuck in the measurement part. In other words i ...
2
votes
0answers
147 views
Computational Complexity of cycle double cover
Let $\mathcal{G}$ be the set of all finite simple graphs. Let graph $G\in \mathcal{G}$ and $C_G=\left <C_1,...,C_m \right >$ be a sequence of cycles of $G$ for some $m$. For every edge $e$ of $G$...
1
vote
0answers
117 views
Quantum polynomial method and L2-norm
Consider a quantum query algorithm that takes as input $x \in \{0,1\}^n$. Denote by $X_i$ the variable that evaluates to $1$ on input $x$ if the $i$-th bit of $x$ is 1, and $-1$ otherwise. Let $X_{\...
11
votes
1answer
355 views
What does a tangible Quantum-Gate look like?
I'v read published books, articles and papers about Quantum-Computing.
I found that all the materials I've seen are, instead of describing quantum gate from basic physics to abstraction, trying hard ...
3
votes
0answers
95 views
Cutting edge of quantum error correction
Often I find myself needing to know the best error correcting code for a certain quantum scenario. For example, suppose my logical systems are 3-dimensional; then what's the most efficient encoding to ...
23
votes
1answer
974 views
Is the 2016 implementation of Shor's algorithm really scalable?
In the 2016 Science paper "Realization of a scalable Shor algorithm" [1], the authors factor 15 with only 5 qubits, which is fewer than the 8 qubits "required" according to Table 1 of [2] and Table 5 ...
-4
votes
1answer
123 views
Can a computer generated organism be self aware? [closed]
Imagine that a computer generating a small universe similar to our own. Same table of elements, same physics, ect. Starting from the very beginning, with the creation of all the atoms in the ...
-3
votes
1answer
174 views
The factoring problem reduces to order finding or is it the other way around? [closed]
initially i was not at all equipped in theoretical computer science and knew only basics of number of theory.
I started working from scratch on the age old problem of primality testing which led me to ...
6
votes
1answer
251 views
Which areas of computer science have lots of overlap with physics?
I'm an undergrad in computer science but I've always loved physics and its ability to constantly amaze and surprise us about our world. I am wondering if there are areas in graduate level computer ...
