Skip to main contentIBM Quantum Documentation

hidden_linear_function

class qiskit.circuit.library.hidden_linear_function(adjacency_matrix)

GitHub

Bases:

Circuit to solve the hidden linear function problem.

The 2D Hidden Linear Function problem is determined by a 2D adjacency matrix A, where only elements that are nearest-neighbor on a grid have non-zero entries. Each row/column corresponds to one binary variable xix_i.

The hidden linear function problem is as follows:

Consider the quadratic form

q(x)=i,j=1nxixj (mod 4)q(x) = \sum_{i,j=1}^{n}{x_i x_j} ~(\mathrm{mod}~ 4)

and restrict q(x)q(x) onto the nullspace of A. This results in a linear function.

2i=1nzixi (mod 4)xKer(A)2 \sum_{i=1}^{n}{z_i x_i} ~(\mathrm{mod}~ 4) \forall x \in \mathrm{Ker}(A)

and the goal is to recover this linear function (equivalently a vector [z0,...,zn1][z_0, ..., z_{n-1}]). There can be multiple solutions.

In [1] it is shown that the present circuit solves this problem on a quantum computer in constant depth, whereas any corresponding solution on a classical computer would require circuits that grow logarithmically with nn. Thus this circuit is an example of quantum advantage with shallow circuits.

Reference Circuit:

from qiskit.circuit.library import hidden_linear_function
A = [[1, 1, 0], [1, 0, 1], [0, 1, 1]]
circuit = hidden_linear_function(A)
circuit.draw('mpl')
../_images/qiskit-circuit-library-hidden_linear_function-1.png

Parameters

adjacency_matrix (list | np.ndarray) – a symmetric n-by-n list of 0-1 lists. n will be the number of qubits.

Raises

CircuitError – If A is not symmetric.

Return type

QuantumCircuit

Reference:

[1] S. Bravyi, D. Gosset, R. Koenig, Quantum Advantage with Shallow Circuits, 2017. arXiv:1704.00690

Was this page helpful?
Report a bug or request content on GitHub.