Questions tagged [quantum-computing]
Quantum computation and computational issues related to quantum mechanics
403
questions
1
vote
2
answers
252
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 ...
- 607
10
votes
0
answers
262
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 ...
- 233
4
votes
0
answers
1k
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^{...
- 12.9k
2
votes
1
answer
143
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
1
answer
170
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 = ...
- 141
0
votes
1
answer
194
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 ...
- 463
1
vote
1
answer
158
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,572
2
votes
0
answers
84
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 ...
- 121
1
vote
0
answers
150
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 ...
- 11
1
vote
0
answers
80
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 ...
- 1,572
-2
votes
1
answer
180
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,070
6
votes
1
answer
318
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}}=\...
- 355
-2
votes
2
answers
266
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
0
answers
102
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 ...
- 111
1
vote
0
answers
144
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 ...
- 253
2
votes
0
answers
67
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 ...
- 1,224
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 ...
- 331
1
vote
1
answer
420
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 ...
- 119
4
votes
0
answers
247
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 ...
- 303
4
votes
1
answer
747
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 ...
- 303
1
vote
1
answer
104
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$) ...
- 111
4
votes
2
answers
670
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
1
answer
220
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 ...
- 151
9
votes
1
answer
2k
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 ...
- 303
1
vote
1
answer
101
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/...
- 113
2
votes
1
answer
259
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 ...
- 831
1
vote
0
answers
90
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 ...
1
vote
0
answers
129
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_{\...
- 303
11
votes
1
answer
494
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 ...
- 221
2
votes
0
answers
114
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 ...
- 203
23
votes
1
answer
1k
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 ...
- 541
-4
votes
1
answer
143
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 ...
- 103
-2
votes
1
answer
686
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 ...
5
votes
1
answer
656
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 ...
- 51
1
vote
1
answer
68
views
Iterating over all stabilizer operations on $k$ qubits
Stabilizer circuits, i.e. quantum circuit that only use the $H$, $\sqrt{Z}$, and $CNOT$ gates, can only implement a finite subset of all possible unitary operations.
I want to iterate over all these ...
- 1,518
4
votes
0
answers
107
views
Why primitive rotation is $53.13^\circ$ in the quantum Turing machine used by Vitanyi for Quantum Kolmogrov Complexity?
Right now I am going through Quantum Kolmogorov Complexity Based on Classical Descriptions by Vitanyi.
In the introduction, the author assumed the primitive rotation $\theta = 53.13^\circ$ to have ...
- 831
0
votes
0
answers
158
views
Questions about the definition of the Quantum Turing Machine
I am trying to have a better understanding of the definition of the Quantum Turing Machine.
My questions:
If the output of a quantum program is the eigenvalue of the ground state of a Hamiltonian ...
- 831
44
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 ...
- 827
1
vote
0
answers
184
views
Two definitions of $QMA$
In this question, I am trying to understand the equivalence between the following two definitions of the complexity class QMA.
In Quantum Computational Complexity, John Watrous defines the class QMA ...
- 831
3
votes
1
answer
160
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 ...
- 1,518
2
votes
1
answer
100
views
Why is it impossible to work with polylog length encoding schemes for quantum circuits?
I am going through Quantum Computational Complexity by John Watrous. On page $12$, he said:
The encoding disallows compression: it is not possible to work with
encoding schemes that allow for ...
- 831
2
votes
0
answers
45
views
Non-commutative quantum counting with aggregate constant work per increment
Classically, it's very easy to create an incrementing function that can perform up to $n$ increments with $O(n)$ work:
...
- 1,518
-2
votes
1
answer
1k
views
Addition on a quantum computer
From reading https://arxiv.org/pdf/quant-ph/0008033v1.pdf 3n qubits are required to add two n bit numbers.
For a simple arithmetic operation such as a+b+c+d where ...
- 107
3
votes
2
answers
382
views
When is a non-unitary quantum system only theoretical?
Suppose we construct a non-unitary quantum system α in hilbert space. It entails that this system would have no direct parallel in quantum circuitry as it is a requirement that all quantum gates ...
- 153
0
votes
1
answer
110
views
How are new probabilities computed when simulating measurement on a set of qubits?
Suppose I have a set of 3 qubits and I have the probabilities for their distribution. This could be arbitrarily entangled or pure:
|000> -> a
|001> -> b
|010> -> c
|011> -> d
|100> -> e
|101> -> f
|...
- 153
8
votes
1
answer
1k
views
States and Probability distributions that the 5-qubits IBM computer can produce
Update (January 2018) A new very interesting paper with various experiments on the IBM machine is Five Experimental Tests on the 5-Qubit IBM Quantum Computer by Diego García-Martín, Germán Sierra.
...
- 6,033
1
vote
1
answer
890
views
How do I figure out how to combine simpler quantum gates to create the gate I want?
I want to create other quantum gates from the basic building blocks of a universal quantum gate set. I've been playing with IBM's quantum computing interface for that.
I wanted to create a Toffoli ...
- 121
1
vote
1
answer
138
views
Can a measurement commuting with the stabilizer of a state disturb the state?
In Nielsen and Chuang's "Quantum Computation and Quantum Information", Section 10.5.3, the authors claim the following:
With a system in state $|\psi\rangle$ with stabilizer $g_1,...,g_n$, if a ...
- 111
5
votes
1
answer
765
views
theorems for universal set of quantum gates for SU(d)
It seems that there is a theorem that for prime dimension d, the set of Clifford gates and one non-Clifford gate together forms a universal set of quantum gates for SU(d). It also seems that for a ...
- 63
4
votes
1
answer
75
views
Is it possible to MAC a quantum state with a classical key under reasonable assumption?
Assume that classical one-way functions secure against quantum adversaries exist. Is it possible, given a quantum state $Q$ and classical secret key $k$, produce a quantum state $AuthQ$ such that:
...
- 528