Questions tagged [quantum-computing]

Quantum computation and computational issues related to quantum mechanics

76 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
1
vote
0answers
96 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
123 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
80 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
119 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
110 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
122 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
142 views

Quantum computer versus Random 3-SAT?

It seems to be commonly believed that quantum computer cannot efficiently solve NP-hard problems. What about the challenging problems in average-case, such as Planted Clique and Random 3-SAT?
1
vote
0answers
54 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
34 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
93 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
90 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
173 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
144 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
256 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
40 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 ...
0
votes
0answers
149 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
97 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
29 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
126 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
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
votes
0answers
49 views

Conjuagate operation solution

Let A,B two matrices over binary field that are similar. So there exists a solution to equation of type $$B=XAX^{-1} $$ Is there an algorithm to find all X's? If not classical, may be a quantum ...
-2
votes
0answers
99 views

Can the aliens hustle us with Chaitin's constant?

Premise Suppose you are an alien and want to fool Earthlings you have extracted the value of Chaitin's Constant. Does the strategy below work? If so, any explicit(/basic ideas for) algorithm? If not, ...
-2
votes
1answer
144 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 ...