Source-linked AI summary
Universal expressiveness of variational quantum classifiers and quantum kernels for support vector machines
Jonas Jäger, Roman V. Krems
TL;DR
Quantum machine learning needs evidence of computational advantage for it to become a new computational paradigm. This paper applies variational quantum classifiers and quantum-kernel support vector machines to k-Forrelation classification, showing PromiseBQP-complete expressive power and implications for solving BQP problems efficiently.
Problem
Computational advantage for machine-learning models based on quantum circuits must be proved and demonstrated for quantum machine learning to become a new computational paradigm.
Source: INTRODUCTION · p. 1Method
The authors encode k-Forrelation instances with a feature map and use it for variational quantum classifiers and quantum-kernel support vector machines.
Source: k-Forrelation classification data set · p. 3, Universal expressiveness of VQC · p. 3Results
Both classifiers solve the k-Forrelation classification problem efficiently with arbitrary accuracy, demonstrating PromiseBQP-complete expressive power.
Source: RESULTS · p. 2Takeaways & Limitations
The results imply that suitable feature maps and quantum kernels can make these models efficient solvers for any problem with BQP complexity.
Source: INTRODUCTION · p. 2
Abstract
from arXiv · showhide
Machine learning is considered to be one of the most promising applications of quantum computing. Therefore, the search for quantum advantage of the quantum analogues of machine learning models is a key research goal. Here, we show that variational quantum classifiers and support vector machines with quantum kernels can solve a classification problem based on the $k$-Forrelation problem, which is known to be PromiseBQP-complete. Because the PromiseBQP complexity class includes all Bounded-Error Quantum Polynomial-Time (BQP) decision problems, our results imply that there exists a feature map and a quantum kernel that make variational quantum classifiers and quantum kernel support vector machines efficient solvers for any BQP problem. Hence, this work implies that their feature map and quantum kernel, respectively, can be designed to have a quantum advantage for any classification problem that cannot be classically solved in polynomial time but contrariwise by a quantum computer.
INTRODUCTION
The paper shows that VQC and QSVM can efficiently solve a k-Forrelation classification task with arbitrary accuracy, establishing PromiseBQP-complete expressive power and implying suitable feature maps or quantum kernels can support efficient solutions to any BQP problem.
INTRODUCTION
- Quantum data embeddings can produce measurement-based kernels for QSVM, while variational quantum circuits enable VQC; demonstrating computational advantage remains necessary for QML as a paradigm.Source: INTRODUCTION · p. 1
- A problem is complete for a complexity class when every problem in that class efficiently reduces to it; hardness means it is at least as difficult as every problem in the class.The passage describes hardness as stronger than completeness because a hard problem may belong to a hierarchically higher class.Source: INTRODUCTION · p. 1
- BQP comprises decision problems solvable by polynomial-time quantum computation with at most 1/3 error; it includes P and is assumed to include problems outside P.The passage states that BQP-complete problems are therefore believed not to be solvable in polynomial time on classical computers.Source: INTRODUCTION · pp. 1–2
- Liu et al. used the presumed-NP DLP1/2 problem to demonstrate QSVM separation, but that result cannot be generalized to arbitrary BQP problems.DLP1/2 is based on computing the most significant bit of a discrete logarithm for a specified fraction of inputs; the passage argues that its presumed NP membership prevents it from being BQP-complete.Source: INTRODUCTION · p. 2
- Because k-Forrelation is PromiseBQP-complete, the results imply that a quantum kernel or feature map can make QSVM or VQC efficient for any BQP problem.Source: INTRODUCTION · p. 2, RESULTS · p. 2
RESULTS
- VQC and QSVM solve the k-Forrelation classification task efficiently and with arbitrary accuracy, giving both PromiseBQP-complete expressive power.The task uses a compact data encoding, and correctly classifying its dataset requires PromiseBQP-complete complexity.Source: RESULTS · p. 2
k-Forrelation classification data set
A restricted-function encoding gives k-Forrelation instances a polynomial-dimensional representation, and a feature map built from the encoded instance enables VQCs and quantum-kernel SVMs to classify it correctly.
- Restricting each function to at most three input bits, with at least one using exactly three, preserves PromiseBQP-completeness and enables a multi-hot instance encoding of dimension kn rather than k2^n.Each function is represented by an n-bit vector marking the input bits in its product; the constant function is encoded as the zero vector.Source: k-Forrelation classification data set · p. 2
- The feature-map circuit encodes each Boolean function as a diagonal unitary and applies the functions successively with Hadamard gates; the k-Forrelation value is the final state's all-zero amplitude.Measurements in the computational basis estimate that amplitude to decide the k-Forrelation problem.Source: k-Forrelation classification data set · pp. 2–3
- VQCs and quantum-kernel SVMs using the proposed feature map predict the correct class, with accuracy arbitrarily improved by more measurements and perfect classification at the exact measurement probability.The feature map is |Φ(x)⟩ = U_F(x)|0⟩^⊗n, with U_F(x) defined by the k Boolean functions encoded in sample x.Source: k-Forrelation classification data set · p. 3
k-Forrelation training data
The section constructs k-Forrelation samples whose encoded states represent the two classes, then shows that VQCs and QSVMs can classify them with PromiseBQP-complete expressive power.
k-Forrelation training data
- Odd-k explicit k-Forrelation remains PromiseBQP-complete, with positive samples preserving |0^n> and negative samples mapping it to a nonzero basis state.For positive samples, choosing f1 and f3 as the same three-bit Boolean function makes their effects cancel; for negative samples, a single-bit function induces a qubit flip while subsequent gates preserve the nonzero state.Source: k-Forrelation training data · p. 3
Universal expressiveness of VQC
- A polynomial-time reduction makes the VQC decision rule solve k-Forrelation, establishing PromiseBQP-complete expressive power when the bias satisfies both class bounds.The positive-class condition is b > -7/25, while the negative-class condition is b < 4999/5000.Source: Universal expressiveness of VQC · pp. 3–4
Universal expressiveness of QSVM
- The QSVM reduction uses two opposite-label training samples, and its test prediction depends on probabilities of observing 0^n and a nonzero basis state.The dual optimization reduces to one-dimensional optimization over 0 ≤ α ≤ C, with the optimal α determined by the kernel evaluated on the two training samples.Source: Universal expressiveness of QSVM · p. 4
- The QSVM’s two-class bounds admit a bias that guarantees correct predictions, establishing PromiseBQP-complete expressive power.For positive test inputs, the probability of observing 0^n is at least 9/25 and any nonzero z has probability at most 16/25; for negative inputs, the respective bounds are at most 1/10000 and at least 9999/10000.Source: Universal expressiveness of QSVM · p. 4
k-Forrelation fixed ansatz
The k-Forrelation expressiveness result can be implemented with a fixed-ansatz parameterized circuit using O(kn^3) gates, polynomial in n when k = poly(n); direct data encoding instead yields depth O(k).
k-Forrelation fixed ansatz
- O(kn^3) gates suffice for a fixed ansatz that achieves the proven VQC and QSVM expressiveness, while direct data encoding gives shallower circuits of depth O(k).The fixed ansatz uses controlled Z-axis rotations, with the sample setting rotation angles to 0 or π; for k = poly(n), its depth is polynomial.Source: k-Forrelation fixed ansatz · p. 5
DISCUSSION
- Because k-Forrelation is PromiseBQP-complete, VQC feature maps and QSVM quantum kernels can be designed for classification problems derived from any BQP decision problem.The paper further states that if BQP ≠ BPP, VQC and QSVM must have quantum advantage over classical classifiers.Source: DISCUSSION · p. 5
- QSVM is guaranteed to find solutions at least as good as VQC, and both have equivalent universal expressiveness from a computational-complexity perspective.The passage attributes this to QSVM's optimal measurement interpretation and optimization over kernel values for training-data pairs.Source: DISCUSSION · p. 5
Quantum-enhanced classification algorithms
- VQC encodes inputs into quantum states, then learns circuit parameters and a bias classically; QSVM estimates quantum-kernel values and solves the dual optimization classically.The VQC classifies using a quantum measurement, while the QSVM obtains its kernel from the probability of measuring the all-zero bit string.Source: Quantum-enhanced classification… · pp. 5–6
Forrelation
- A quantum algorithm solves Forrelation with constant query complexity and error probability at most 1/3, placing it in PromiseBQP.Its query-implementing circuit remains polynomial.Source: Forrelation · p. 6
extension
- For explicitly described Boolean functions with k = poly(n), k-Forrelation is PromiseBQP-complete.The cited result also holds for functions depending on at most three input bits, provided at least one depends on exactly three bits.Source: extension · p. 6
odd-k-Forrelation
The paper establishes that explicit k-Forrelation remains PromiseBQP-complete when k is odd and at least 3. Its reduction from arbitrary k-Forrelation instances preserves the forrelation value Φ.
odd-k-Forrelation
- Explicit k-Forrelation remains PromiseBQP-complete for odd k ≥3.The proof establishes membership in PromiseBQP and hardness by a polynomial mapping from every k-Forrelation instance that preserves Φ.Source: odd-k-Forrelation · p. 7
- For even k, the reduction adds 4⌈n/2⌉−1 Boolean functions to produce odd k while preserving Φ.The added functions are constants or f(x) = (−1)^x_ix_j, and the resulting circuit is equivalent under SWAP operations.Source: odd-k-Forrelation · p. 7
- When n is odd, an ancilla initialized to |0⟩ enables pairwise gadget application and ends in |0⟩, leaving the result unaffected.The extra qubit is therefore not entangled.Source: odd-k-Forrelation · p. 7