Questions tagged [quantum-computing]
Quantum computation and computational issues related to quantum mechanics
88
questions with no upvoted or accepted answers
1
vote
0answers
51 views
Does the approximatibility of individual gates together with unitarity imply BPP=BQP
Suppose you can prove upper bounds on errors from approximating an individual quantum gate by randomly hashing the qubits of a circuit to a polylog number of qubits. (So, you prove a bound on how much ...
1
vote
0answers
44 views
Non-rigid isomorphic structures
In many of the problems trying to solve hidden shift over some objects like graphs mainly the rigid classes are considered. For eg. in this and this isomorphism problem restricted over rigid graphs is ...
1
vote
0answers
111 views
Quantum error correction and graph codes
I was reading combinatorial approach towards quantum correction. A lot of work in this is on finding diagonal distance of a graph. Let me add definition of diagonal distance so that this remains self-...
1
vote
0answers
39 views
Oracle separation between coNP and QMA implies oracle separation between NP and QMA
In [this] paper, Aaronson remarks (page 2, footnote) that:
From the BBBV lower bound for quantum search [6], one immediately
obtains an oracle $A$ such that $coNP^{A} \not\subseteq QMA^{A}$ for ...
1
vote
0answers
132 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 ...
1
vote
0answers
22 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 ...
1
vote
0answers
72 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 ...
1
vote
0answers
136 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
67 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
vote
0answers
98 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
131 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 ...
1
vote
0answers
82 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
0answers
122 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_{\...
1
vote
0answers
125 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 ...
1
vote
0answers
150 views
Quantum algorithms for generalizations of determinants
There are a wide variety of determent-like constructions. Some like the permanent or immanents are variations on the ordinary determinant for matrices over fields or commutative rings. Some like ...
1
vote
0answers
56 views
First register in the hidden subgroup representations of Simon's and graph isomorphism problems
The Simon's problem involves a function which takes binary strings as inputs. One seeks to find the period of the function which acts on those inputs. In the standard method, the first register has ...
1
vote
0answers
107 views
Is Logic Done on Superpositional Bit Values Useful?
Let's say I have a way to represent $N$ bits such that those bits are in a superposition of the $2^N$ possible states those bits can have and that I can do XOR and AND on those superpositional bits to ...
1
vote
0answers
36 views
Coset state of $3$-node graph isomorphism problem
The hidden subgroup representation of a $3$-node graph isomorphism problem is defined over the symmetric group, $G = S_6$. So, any hidden subgroup algorithm that wishes to solve the problem should ...
1
vote
0answers
102 views
Non-Transversal Fault Tolerant Gate
I have always heard that transversality is a sufficient, not a necessary condition for fault-tolerance in quantum computation. However, I have never seen any examples of non-transversal fault tolerant ...
1
vote
0answers
93 views
Period of a Multivariable Function using Quantum Computing
consider a function
$$f(x_1,x_2...x_n)$$
I am told it is possible to compute the period of the function as a vector
$$<l_1,l_2...l_n>$$
where each l denotes the period of the function for ...
1
vote
0answers
176 views
Relationship between size of quantum superposition and rate of decoherence
I am new here in StackExchange and this will be my first question to ask. I have a background in Computer Science and I am interested in looking into Distributed Quantum Computing (DQC). I have read ...
1
vote
0answers
149 views
Is there a lower bound for the decisional Grover search problem?
What is known about the decisional version of the search problem? By decisional version of the search problem, I mean the problem in which you wish to determine whether there are $0$, or exactly $t$ ...
1
vote
0answers
260 views
Separating the QIP hierarchy
Background: I'm a CS grad student. I've taken a course on computational complexity.
Question:
Can you suggest an introductory book on quantum computation, especially regarding the details of ...
0
votes
0answers
25 views
Which algorithm for linear programming is suitable for the context of quantum computing?
There are two major types of algorithms for linear programming : extreme point based, interior point based.
Which will be suitable for quantum computing?
0
votes
0answers
11 views
Direct Diffie-Hellman by Shor's algorithm
Shor's algorithm appears to be capable of finding discrete logarithm even if the modulus is composite. Does the algorithm implicitly compute the Carmichael Lambda which goes in the exponent or somehow ...
0
votes
0answers
45 views
generalizations of hidden subgroup problem
Quantum Fourier Sampling tries to solve hidden subgroup problem which is defined via a map $f$ from group $\mathrm{G}$ to some set $X$ that separates cosets of sum unknown subgroup $\mathrm{H}$.
$f(...
0
votes
0answers
50 views
Gate definitions for quantum random access codes
I would like to know how the gates are defined in quantum random access codes? Consider the $2 \to 1$ code described in Lemma 3.1 of this paper.
The section defines the encoding and decoding circuits. ...
0
votes
0answers
40 views
Hardwiring the output in a quantum circuit
In this paper, while using a diagonalization argument in Section $5$, the authors write:
Fix some enumeration over all $poly(n)$-size quantum verifiers $M_{1},
M_{2},...$ which we can do because the ...
0
votes
0answers
34 views
Must the cryptographic test for quantumness in [BCMVV18] use post-quantum Trapdoor Claw-Free Functions?
Brakerski, Christiano, Mahadev, Vazirani, and Vidick propose a scheme for verifiable computational quantumness based on a strengthening of trap-door claw-free functions (TCFs).
In the above scheme:
...
0
votes
0answers
151 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 ...
0
votes
0answers
101 views
What is the relationship between quantum tomography and quantum error correction?
To realize correct quantum computing it seems that both quantum error correction and quantum tomography would be necessary. Is this true? What is the relationship between these two fields?
0
votes
0answers
30 views
Hardness of finding similar (quantum) states
Consider a quantum state $\lvert \psi \rangle$, we know from the no cloning theorem, that it cannot be perfectly cloned. Also, loosely speaking, that it can be imperfectly cloned s.t. one can produce ...
0
votes
0answers
124 views
Determining if a function is constant or not using period finding
Consider an arbitrary boolean function
$$f: {\lbrace 0,1 \rbrace}^n \rightarrow \lbrace 0,1 \rbrace$$
which we write as:
$$f(x_1, x_2 ... x_n) $$
where each $x_i$ is a boolean variable
We note ...
0
votes
0answers
132 views
Computing the period of a function using a quantum computer
Consider a blackbox function
$$f(x): Z \rightarrow \lbrace 0,1 \rbrace $$
Which inputs an integer and outputs 0 or 1 with bit complexity n.
If the period P of this function satisfies
$$P \in O(2^{...
0
votes
0answers
383 views
Is it possible to add quantum physics theory to traditional machine learning algorithms to get more accurate results
Lets suppose your data set includes locations in several dimensions and the kind of entity which is the class of the data set, is there other kind of information you need to add (such as times, ...
0
votes
1answer
187 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 ...
-2
votes
1answer
154 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 ...
