8
The setting is that you've got some state $$\sum_{x\in\{0,1\}^n}\alpha_x|x\rangle$$ on a register, you introduce an ancilla in state $|0\rangle$, and you want to create some state
$$
\sum_{x\in\{0,1\}^n}\alpha_x|x\rangle\otimes R_X(f(x))|0\rangle
$$
where $f(x)$ is some angle that you can compute. So, certainly, if you had to build that gate out of the $2^n$ ...
7
You have the definitions in your paper you link page 12.
Simply said, it is a matrix with many 0s.
As an example take N = 16, and the polynomial function is just a simple function like 1.5*X,
then your matrix has at most 1.5*log(16,2)=6 non-zero entries per row.
If you prefer a visual, you have it here:
6
You should know a bound on the eigenvalues (both upper and lower). As you say, you can then normalise $A$ by rescaling $t$. Indeed, you should do this to get the most accurate estimate possible, spreading the values $\lambda t$ over the full $2\pi$ range. Bounding the eigenvalues is not typically a problem. For example, you're probably requiring your matrix $...
6
A couple years ago it was shown in Quantum algorithms and the finite element method by Montanaro and Pallister that the HHL algorithm could be applied to the Finite Element Method (FEM) which is a "technique for efficiently finding numerical approximations to the solutions of boundary value problems (BVPs) for partial differential equations, based on ...
6
This is indeed a correct way to solve linear systems with dimension not equal to a power of 2. Solve the smallest possible system of dimension 2$^n$ that contains the system you want to solve, and pad the matrices and vectors with zeros to make it the right size. This is because the vector $|b\rangle$ in the HHL algorithm, is a quantum state, which means if ...
5
You were correct to seek a new quantum algorithm for this rather than just using HHL to do step 3.
There are separate quantum algorithms to do regressions:
Quantum Algorithm for Data Fitting (same journal and same last author as HHL)
Quantum Algorithm for Linear Regression
Fast quantum algorithms for least squares regression and statistic leverage scores
...
5
I don't know why/how the authors of that paper do what they do. However, here's how I'd go about it for this special case (and it is a very special case):
You can write the Hamiltonian as a Pauli decomposition
$$
A=15\mathbb{I}\otimes\mathbb{I}+9Z\otimes X+5X\otimes Z-3Y\otimes Y.
$$
Update: It should be $+3Y\otimes Y$. But I don't want to redraw all my ...
5
1. Definitions
Names and symbols used in this answer follow the ones defined in Quantum linear systems algorithms: a primer (Dervovic, Herbster, Mountney, Severini, Usher & Wossnig, 2018). A recall is done below.
1.1 Register names
Register names are defined in Figure 5. of Quantum linear systems algorithms: a primer (Dervovic, Herbster, Mountney, ...
5
If $\tilde{\lambda_{k}} < C$, the controlled rotation becomes non-physical since you have coeffecient greater than 1 on your $|1\rangle$ state.
As a result $C < \lambda_{min}$ is a safer choice, and that is $O(1/\kappa)$ according to the 4th paragraph in the intro.
5
The restriction on the eigenvalues is usually given in the form of a condition number. This is the $\kappa$ that you see in all the runtimes in your table. $\kappa = |\lambda_{\rm{max}}/\lambda_{\rm{min}}|$ where $\lambda_{\rm{max}}$ and $\lambda_{\rm{min}}$ are the maximum and minimum eigenvalues respectively.
In all runtimes listed in your table, it is ...
5
It depends on the papers but I saw 2 approaches:
In most of the papers I read about the HHL algorithm and its implementation, the Hamiltonian evolution time $t$ is taken such that this factor disappear, i.e. $t = t_0 = 2\pi$.
The approximate eigenvalue is often written $\tilde \lambda$. In some paper this notation really means "the approximation of the ...
4
Your intuition is correct for a single qubit, in that if I measure $$\alpha\vert 0 \rangle + \beta\vert 1 \rangle$$ I would get either $\vert 0 \rangle$ or $\vert 1 \rangle$. But since the qubits are in a large entangled state, the relevant information stored in the ratios of different probabilities is still held fixed, and the $\frac{C}{\lambda_j}$ factors ...
4
Certainly it is meant as the largest eigenvalue. I have no idea why the linked review paper uses the determinant. I don't see anywhere that they use that property (from an admittedly brief skim).
I presume you could rewrite conditions in terms of the determinant (you would have to alter the time step $t_0$) but it's not clear to me why you would want to. It'...
4
I know that $b$ can be decomposed mathematically as $b= c_1u_1 +
> \cdots + c_nu_n$ since these eigenvectors form an orthonormal basis.
Why only consider the effect on $|u_j \rangle$?
As you say, you know you can decompose $b$ in terms of the $|u_j \rangle$, so by linearity, if we know the effect on one basis state (which is pedagogically easier to ...
4
Note: the graphics have been generated with the LaTeX code available here. Credits to @Niel de Beaudrap.
Yes it is possible!
The HHL algorithm can be schematically depicted as
Let's split down the parts:
The first part aims at computing an approximation of the eigenvalues of $H$, $H = A$ if $A$ is hermitian, else $H = \begin{pmatrix} 0 & A \\ 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
There is actually a nice way to do this in Qiskit, since it has decompositions for single-qubit unitaries built in. The QuantumCircuit.squ method takes a unitary 2x2 matrix $U$ and a qubit and computes the decomposition
$$
U = R_Z(\alpha) R_Y(\beta) R_Z(\gamma)
$$
This is a common decomposition, you can find a proof here https://arxiv.org/pdf/quant-ph/...
4
You want to implement
$$
e^{i3\pi/4}e^{iX\pi/4}.
$$
I would rewrite this as
$$
e^{i3\pi/4}He^{iZ\pi/4}H.
$$
This is the same as
$$
-HS^\dagger H
$$
in standard gate terminology.
If you're only implementing the gate $e^{iAt}$, then you can neglect the global phase and just implement $HS^\dagger H$. Both of these gates are readily implemented in qiskit as sdg ...
3
1) Are we not applying the conditional Hamiltonian evolution to $|\Psi_0 \rangle |b \rangle$?
The operation
$$\sum_{\tau = 0} ^{T - 1} |\tau \rangle \langle \tau| \otimes e^{iA\tau t_0 / T}$$
is a controlled operation. You can read it as:
$\forall \tau \in [0, T-1]$, if the first register is in the state $\vert \tau \rangle$, apply $e^{iA\tau t_0 / T}$. ...
3
The simplest method to implement $e^{iA\theta}$ for a small, Hermitian matrix $A$ is to:
Find the eigenvectors $|\lambda\rangle$ and eigenvalues $\lambda$ of $A$.
Construct the unitary $U=\sum_i|i\rangle\langle\lambda_i|$.
Implement the gate sequence:
$U$
$e^{i\theta\sum_i\lambda_i|i\rangle\langle i|}$
$U^\dagger$
Now, for one qubit, you have the middle ...
3
You are half right, in that the $C$ factor is only kept there for (what I assume being) explanatory purposes.
However, the $1/\lambda_j$ factors definitely stays there after postselection. One way to see this is that you can think of those factors as attached to the other registers, so that the state is equivalently written as
$$
\left(\sum_j\beta_j\sqrt{1-...
3
Disclaimer: I'm the one that wrote the code of the 4x4 HHL.
Controlling a quantum gate $U$ can be achieved by controlling each of the $U_i$ gates that are composing $U$.
For the specific example you are considering, the implementation is available online. Some remarks about the code:
I think the code is not up to date with the last version of Qiskit. I ...
3
I don't see the need for the swap gate either. Although I also don't think you need the set of swap gates that you're wanting. Remember that the standard implementation of the Fourier transform outputs the binary string $j\in\{0,1\}^4$ where the eigenvalues are of the form $2\pi j/16$ but in reverse order, so the least significant bit is at the top, and the ...
3
It's not possible to create the initial states $\left| \Psi_0\right>$ and $\left|b\right>$ on the IBM 16 qubits version. On the other hand, it is possible to approximate them with an arbitrarily low error1 as the gates implemented by the IBM chips offer this possibility.
Here you ask for 2 different quantum states:
$\left| b \right>$ is not ...
3
$\newcommand{\bra}[1]{\left\langle#1\right|}\newcommand{\ket}[1]{\left|#1\right\rangle}\newcommand{\proj}[1]{|#1\rangle\langle#1|}\newcommand{\half}{\frac12}$In answer to your first question, I wrote myself some notes some time ago about my understanding of how it worked. The notation is probably a bit different (I've tried to bring it more into line, but it'...
3
Let's assume that you have a Hermitian matrix
$$
H=\left(\begin{array}{cc} 0 & A^\dagger \\ A & 0 \end{array}\right).
$$
Let $|b\rangle$ be the state that we want to apply $A$ to, extended to work on the space that $H$ acts on. So, our aim is to implement $H|b\rangle$.
Let $X$ be the standard Pauli $X$ matrix. If we implement a unitary evolution
$$
...
3
Define the states
$$
|\psi_t\rangle=\left\{\begin{array}{cc}
|t\rangle\otimes(U_{t-1}U_{t-2}\ldots U_1|\psi\rangle) & t=1,2,\ldots T \\
|t\rangle\otimes(U_{T}U_{T-1}\ldots U_1|\psi\rangle) & t=T+1,T+2,\ldots 2T \\
|t\rangle\otimes(U_{3T+1-t}U_{3T-t}\ldots U_1|\psi\rangle) & t=2T+1,2T+2,\ldots 3T
\end{array}\right.
$$
Now let
$$
U=\frac{2}{T}\sum_{...
3
Be careful! They don't apply $e^{i\pi A}$ and $e^{i\pi A/2}$. They apply
$$
|0\rangle\langle 0|\otimes I\otimes I+|1\rangle\langle 1| \otimes I\otimes e^{i\pi A}
$$
and
$$
I\otimes |0\rangle\langle 0|\otimes I+I\otimes |1\rangle\langle 1|\otimes e^{i\pi A/2},
$$
i.e. controlled versions of the gates, controlled off two different qubits.
So, consider the 4 ...
3
Probably only two qubits constrain set of algorithm you can run on your device, for example HHL algorithm (linear equation solver) seems to impossible work there.
You can however implement algorithms based on uniformly controlled rotation used for preparing arbitrary quantum state. See details in the paper Transformation of quantum states using uniformly ...
3
I have implemented via qiskit two algorithms and posted in github that need only 1-2 qubits. First is Iterative Quantum Phase Estimation (IQPE) that works on two qubits, the second one is Variational Quantum Eigensolver (VQE) that works on only one qubit (one can do also for 2 qubits) in my implementations. Actually they are jupyter notebook tutorials, so I ...
Only top voted, non community-wiki answers of a minimum length are eligible
