# Tag Info

## Hot answers tagged algorithm

13

You might find this analogy helpful: the development of quantum algorithms is still in the Booth's multiplication algorithm stage; we haven't quite reached dynamic programming or backtracking. You'll find that most textbooks explain the Booth's algorithm using the following circuit. That is in fact, the method in which the multiplication logic is ...

6

For complexity theory, Watrous' CSSQI 2012 lectures are the best resource I found so far. Here's the corresponding review paper. He approaches the subject in a fairly rigorous manner which is a great thing if you like clarity. You could also follow Scott Aaronson's undergraduate lectures in parallel for a more intuitive although slightly hand-wavy approach....

6

The point is that free parallel computation or cloning of your existence is a wholesale misinterpretation of the concept of quantum superposition. Quantum states are analogous to probability distributions. If you might wash the dishes or you might wash the floor and you flip a coin to decide which one, then no one takes that to mean that you will wash ...

6

The state of quantum computing technology is still in its infancy, so implementation details are generally important when considering quantum algorithms. Number of gates, number of operations, types of gates (e.g. Clifford vs. non-Clifford) are often necessary information to evaluate the feasibility and value of a quantum algorithm. In many cases quantum ...

6

Let us look at each observation and question in perspective. Before delving deep into the questions, please let me share a few reference architecture diagrams on the components of a quantum computer. We need to review the mentioned observations and understandings from a practical implementation vantage point. When we consider the quantum realm in its ...

5

You specifically ask about qubits, so I'll keep it to that. Imagine you have a state $$|\psi\rangle=\sum_{x\in\{0,1\}^n}a_x|x\rangle.$$ You can choose to look at each qubit. I'll take the first qubit for the sake of simplicity. We have that $$|\psi\rangle=|0\rangle\sum_{y\in\{0,1\}^{n-1}}a_{0y}|y\rangle+|1\rangle\sum_{y\in\{0,1\}^{n-1}}a_{1y}|y\rangle$$ ...

4

In classical computing, both circuit diagrams and pseudo-code are used to explain algorithms. The choice between circuits and pseudo-code depends on the context. If the goal is to explain a highly optimized implementation of an algorithm on FPGA, a circuit diagram is probably more suitable. For example, see this paper on AES implementation on FPGA. ...

4

how can you compare the result of your algorithm with an ideal evolution? You cannot and you do not need to. As you said, computing $e^{-iHt}$ is intractable for most of the interesting cases. If it was not, chemistry simulations would be easy, solving the Schrödinger equation too. The thing you can do though is to prove that your algorithm will, for a (...

4

You can draw the circuit using construct_circuit().draw(). In the tutorial you are talking about, if you scroll down to the 4x4 randomly generated section that uses params5 you can run print(hhl.construct_circuit()), after the line hhl = HHL.init_params(params5, algo_input). This may take a little while to complete but it should eventually print out ASCII ...

4

Your circuit does not measure $q_2$ qubit after teleportation; I guess that is why teleportation of $|1\rangle$ qubit is shown incorrectly.

4

I think you would benefit from realizing that quantum gates are an abstraction of the actual operations that we perform on qubits. Just as a qubit is an abstraction (a mathematical model to describe the state of a two-level quantum mechanical system) a quantum (logical) gate is a mathematical construct that we use in the study of quantum algorithms & ...

4

Hadamard Gates together with Quantum Bloom Filters and a Verifiable Random Functions can prove to be a simple but elegant implementation of Quantum Algorithmic Randomness. This technique can be seen as a way to reduce the dimensionality of high-dimensional data; high-dimensional input items can be reduced to low-dimensional versions while preserving ...

3

Two classical texts for the representation theory of finite groups are the books of Hamermesh and Serre. These books however lack chapters on Fourier analysis needed for the quantum computation applications. For a more modern text for finite group representations which includes a chapter on Fourier analysis, please see the lecture notes by: Steinberg. ...

3

I found this overview of quantum algorithms and their implementation (for majority of them) on IBM Q Experience quite useful: https://arxiv.org/abs/1804.03719.

3

I would like to add some more sources: Perhaps the most well-known source is the book "Quantum Computation and Quantum Information" by Nielsen & Chuang. Even though the scope of the book is broader than just quantum algorithms, it is well-structured so there is no need to dig through unrelated topics. Another source is Ronald de Wolf's lecture notes, ...

3

Any quantum algorithm to approximate Chaitin's constant (or any other number) will also yield a classical algorithm to approximate that same number, just by simulating the quantum computer. (It won't be a great classical algorithm, but it's still an algorithm.) As Chaitin's constant provably doesn't admit such a classical algorithm, it also doesn't admit a ...

3

Yes, it will depend on $n$ because sampling with replacement is assumed in the proof, which doesn't make sense if $n$ is finite. Intuitively, if a function $f$ really is balanced, and first output corresponding to certain random input is $0$ or $1$, then the probability that the second output corresponding to some other random input will be the same is less ...

2

The comment made by arriopolis is correct. The output registers of these compiled circuits are important for synthesizing the circuit, but not particularly interesting to measure. As you saw already, those measurements just match the truth tables they were designed to match. The QFT and measurements intended for this circuit are which gives the ...

2

If I understand you correctly, your goal is: To choose some quantum algorithm (your question is: which algorithm would be good?) Instead of running the quantum algorithm on a real quantum computer, you want to run a simulation of a quantum computer on a classical computer to simulate the execution of the quantum algorithm. You want to optimize your ...

2

Consider an arbitrary vector $\boldsymbol v\equiv(v_i)_{i=1}^N\in\mathbb C^{nm}$ of length $n m$ (if you care only about qubits, just fix $n=m=2$). For $\boldsymbol v$ to have an $(n,m)$ partition means that we can write it as $\boldsymbol v=\boldsymbol u\otimes \boldsymbol w$ for some $\boldsymbol u\in\mathbb C^n$ and $\boldsymbol w\in\mathbb C^m$. If this ...

2

Let's define the kets, ket0 = {{1},{0}};ket1 = {{0},{1}}; This function produces input from a string, f[x_?StringQ] := ToExpression[StringJoin["ket",x]]; This function produces the diagonal matrix corresponding to a string "000", matrixFunc[x_]:= KroneckerProduct@@ f/@ StringPartition[x,1] . ConjugateTranspose[KroneckerProduct@@ f/@ StringPartition[x,...

2

The most recent quantum machine learning textbook is Schuld and Petruccione (2018). Supervised Learning with Quantum Computers while a nice companion to Nielsen and Chuang for introductory quantum maths is Marinescu and Marinescu (2011). Classical and Quantum Information, Chapter 1: Preliminaries

2

The credit for this answer goes to met927 in the previous post. So please upvote that answer instead of this one. met927's response answered my question. Not setting up some of the parameters to make system draw faster was my error. So thank you met927 for responding quickly and answering my question! Below is a snippet that one can run quite quickly (...

2

There is a textbook that starts from scratch and teaches you all the fundamental concepts of quantum computing, including quantum algorithms. I would also recommend the tutorials as these are written in python so should accessible to Computer Scientists. There are also further tutorials on things such as Shor's. When learning I also found there were lots of ...

2

Yes, when you run an algorithm, often specified as a sequence of gates, you get different results according to some probability distribution. Assuming we are talking about an error-free computation (this is where, in this field, we use the terminology "noise" which is distinct from the "noise" of "signal to noise ratio"), then most algorithms that you will ...

2

Related threads: Good introductory material on quantum computational complexity classes Does a study guide exist that starts from a "purely CS background" and advances towards "making a new quantum programming language"? Programming quantum computers for non-physics majors Resources for quantum algorithm basics What are the basics needed ...

2

You can create the unitary gate for operator $U(\theta)=e^{-i\frac{\theta}{2}Z_{0}Z{1}}$ using two $CNOT$ operations and single rotation gate $R_z$: For operators which contain different tensor products of Pauli matrices beside the product of $Z$ you have to change basis using appropriate unitary transformation: $R_y(-\frac{\pi}{2})$ changes $X$ basis to $Z$...

1

With Q# you can generate random numbers in two ways: Using a classical pseudorandom number generator, which is exactly the same that a classical language like Python does when you use the library random. As Mariia Mykhailova says in the comments, Q# has a built-in operation RandomInt that does exactly this: RandomInt Using a quantum operation that uses ...

1

Based on what I've understood from your question, I think the interpretation of the noisy channel as the quantum algorithm may be causing unnecessary confusion. QEC should be present in the fault tolerant computing paradigm as a background operation capable of guaranteeing that qubits retain coherence of their quantum states for practical amounts of time. As ...

1

Yes. The tensor product of two linear maps $S: V \to X$ and $T: W \to Y$ is the linear map $$S \otimes T: V \otimes W \to X \otimes Y \ni (v \otimes w) \mapsto S(v) \otimes T(w).$$

Only top voted, non community-wiki answers of a minimum length are eligible