⚛️ quantum physics

Public-Key Quantum Money and Fast Real Transforms

This paper proposes a public-key quantum money scheme based on group actions and the Hartley transform that replaces complex amplitudes with real ones to offer potential advantages, supported by a new verification algorithm, an efficient serial number computation method using continuous-time quantum walks, and a recursive quantum Hartley transform with reduced gate complexity.

Original authors: Jake Doliskani, Morteza Mirzaei, Ali Mousavi

Published 2026-03-16

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jake Doliskani, Morteza Mirzaei, Ali Mousavi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a bank trying to issue money that is physically impossible to counterfeit. In the classical world, you can photocopy a dollar bill. In the quantum world, thanks to a rule called the "No-Cloning Theorem," you cannot copy a quantum state without destroying the original. This makes quantum money theoretically perfect.

However, there's a catch: How do you verify it?

In older schemes, the bank had to be involved in every transaction to check the bill. The goal of this paper is to create "Public-Key Quantum Money"—a system where anyone can verify a bill is real, but only the bank can create one.

Here is a breakdown of what the authors did, using simple analogies.

1. The Problem with the "Old" Magic Trick

The authors started with a recent, promising design by a researcher named Zhandry. Think of Zhandry's design as a magic trick where the bank creates a bill using a specific mathematical tool called the Fourier Transform.

The Analogy: Imagine the Fourier Transform is like a prism. When you shine a beam of light (the money) through it, it splits into a rainbow of complex colors (complex numbers).
The Issue: While this works, the "rainbow" is made of complex numbers (involving imaginary numbers like $i$ ). The authors realized that if you try to verify these bills using a specific method, the math gets messy. Specifically, the verification process sometimes gets confused between two very similar-looking bills, like mistaking a left-handed glove for a right-handed one.

2. The Solution: The "Hartley" Prism

The authors decided to swap the Fourier prism for a different tool called the Hartley Transform.

The Analogy: If the Fourier prism creates a rainbow of complex colors, the Hartley prism creates a rainbow of real, tangible colors (just standard numbers, no imaginary parts).
Why it matters: Real numbers are easier to work with on a computer and theoretically "cleaner." It's like switching from a hologram that requires special glasses to a high-definition 3D image you can see with your naked eye.

But there was a new problem:
Because they switched to this "real" prism, the old verification trick stopped working. The bank could create the bill, but the public couldn't tell if it was real or a fake that looked almost identical.

3. The Fix: "Twisting" the Bill

To fix the verification issue, the authors introduced a new concept called Group Action Twists.

The Analogy: Imagine the money is a spinning top. The old verification method tried to read the label on the top while it was spinning. But because of the "real number" switch, the top looked the same whether it was spinning clockwise or counter-clockwise.
The Twist: The authors added a special "twist" mechanism. They realized that if you apply a specific "twist" to the bill (a mathematical operation that flips the direction of the spin), you can tell the difference between a real bill and a fake one.
The Result: They built a new verification algorithm. It's like a security guard who doesn't just look at the bill; they give it a gentle spin (the twist). If the bill reacts in a specific way, it's real. If it doesn't, it's a fake.

4. Finding the Serial Number (The "Serial Number Hunt")

Every bill has a serial number. In the old system, you could just read it off the bill. In this new "real number" system, the serial number is hidden inside the quantum state.

The Analogy: Imagine the bill is a locked safe, and the serial number is the combination. You can't just look at the safe to see the numbers; you have to shake it to hear the tumblers click.
The Method: The authors used Quantum Walks.
- Classical Walk: Imagine a drunk person stumbling randomly down a hallway. It takes a long time to find a specific door.
- Quantum Walk: Imagine a ghost that can be in all parts of the hallway at once, interfering with itself to find the right door instantly.
The Result: They created an algorithm that uses this "ghost walk" to explore the quantum state and extract the serial number efficiently. This allows the bank to issue bills and the public to verify them without needing the bank to be present.

5. Building Better Tools (The Recursive Algorithm)

Finally, the paper isn't just about money; it's also about building better tools for quantum computers.

The Analogy: To build the Hartley prism, you need a machine to manufacture it. Previous machines were big, clunky, and used a lot of energy (gates).
The Innovation: The authors designed a new, smaller, and more efficient machine (a recursive algorithm) to build the Hartley transform.
The Benefit: This new machine uses fewer steps and less energy than previous designs. Furthermore, they showed that once you have this machine, you can easily build other useful tools (like Sine and Cosine transforms) by just plugging them into the Hartley machine.

Summary

The authors took a promising but slightly flawed idea for unforgeable digital cash, swapped out the complex mathematical engine for a simpler, "real-number" engine, and then invented a clever new way to verify the cash using "twists" and "quantum ghost walks."

Why should you care?

Security: It brings us closer to a future where digital money cannot be copied.
Efficiency: It proves that "real number" math can be just as powerful as "complex number" math in quantum computing, potentially making quantum computers easier to build and program.
Innovation: It introduces new, faster ways to perform mathematical calculations that will be useful for many other quantum applications beyond just money.

1. Problem Statement

The paper addresses two interconnected challenges in quantum cryptography and quantum computing:

Public-Key Quantum Money Security and Verification: Existing schemes, such as Zhandry's (2024) proposal based on abelian group actions and the Quantum Fourier Transform (QFT), rely on complex amplitudes. While secure in the generic group action model, the authors identify a theoretical gap: the original scheme fails to prove security as a "quantum lightning" scheme (a stronger security notion) because certain identities regarding real orthonormal bases do not hold for complex bases. Furthermore, simply replacing the QFT with the Quantum Hartley Transform (QHT) to obtain real amplitudes breaks the standard verification algorithm, as it fails to distinguish between legitimate banknotes and specific counterfeit states.
Efficiency of Real Quantum Transforms: While the QFT is well-studied, efficient algorithms for real-valued quantum transforms (like the Hartley, Sine, and Cosine transforms) are less optimized. Existing recursive algorithms for the Quantum Hartley Transform (QHT) have higher gate complexity or are more difficult to implement than necessary.

2. Methodology

The authors propose a comprehensive framework that integrates new transform algorithms with a modified quantum money protocol.

A. Theoretical Foundation: Real Amplitudes

The core motivation is to replace the Quantum Fourier Transform (QFT) with the Quantum Hartley Transform (QHT).

Hartley Transform: Defined using the cas function ( $\text{cas}(x) = \cos(x) + \sin(x)$ ), it maps real functions to real functions.
Advantage: Banknotes generated via QHT have real amplitudes. This allows the application of specific mathematical identities (e.g., $\sum |\phi_j\rangle|\phi_j\rangle = \sum |\psi_j\rangle|\psi_j\rangle$ for real bases) that fail for complex bases, potentially offering theoretical advantages in proving security against specific attacks.

B. Algorithmic Contributions

Recursive Quantum Hartley Transform (QHT):
- The authors propose a new recursive algorithm for QHT inspired by the structure of the QFT.
- Optimization: Unlike previous recursive approaches (e.g., in [3]) that rely on complex decompositions, this algorithm uses a specific sequence of Hadamard gates, controlled negations, and conditional rotations.
- Complexity: The gate complexity is derived as $2 \log^2 N + O(\log N)$ , which is approximately 1.25 times lower than previous algorithms ([3] and [22]).
Real Transform Subroutines:
- The paper demonstrates how to efficiently implement the Quantum Sine Transform and Quantum Cosine Transform using the QHT as a subroutine.
- This is achieved by adapting the unitary transformation $T_N$ (previously used with QFT) to work with QHT, requiring only one call to QHT and elementary operations.
New Verification Algorithm (Twists):
- The Problem: Directly applying the standard verification (using cmpIndex) to QHT-based money states results in a superposition of the serial number $h$ and $-h$ (specifically $|h+\rangle|Z(h)\rangle + |h-\rangle|Z(-h)\rangle$ ), making it impossible to distinguish a valid note from a counterfeit $|Z(-h)\rangle$ .
- The Solution: The authors introduce a verification algorithm utilizing Group Action Twists.
  - A "twist" is an efficient map $g \ast x \to (-g) \ast x$ .
  - The new algorithm uses a phase estimation-like procedure combined with the twist operation to distinguish between $|Z(h)\rangle$ and $|Z(-h)\rangle$ based on their eigenvalues under the twist unitary.
  - This ensures that only the correct serial number $h$ is accepted with high probability.
Serial Number Extraction via Quantum Walks:
- The paper presents an algorithm to compute the serial number $h$ from a money state $|Z(h)\rangle$ without the bank's private key.
- Method: It utilizes Continuous-Time Quantum Walks (CTQW) on Cayley graphs associated with the group action.
- By simulating the walk $e^{-iAt}$ (where $A$ is the adjacency matrix) and using Phase Estimation, the algorithm extracts the eigenvalue $\lambda_h = 2\cos(2\pi uh/N)$ .
- By choosing different generators $u$ , the algorithm recovers the full serial number $h$ . This demonstrates that serial numbers are efficiently computable, a necessary property for the scheme's functionality.

3. Key Contributions

New Public-Key Quantum Money Scheme: A secure instantiation of Zhandry's scheme using the Hartley transform, ensuring real amplitudes.
Novel Verification Protocol: A verification algorithm that overcomes the ambiguity of real amplitudes using group action twists, proving that the scheme remains secure and verifiable.
Optimized QHT Algorithm: A recursive algorithm for the Quantum Hartley Transform with gate complexity $O(\log^2 N)$ , outperforming existing methods.
Unified Real Transform Framework: A method to compute Sine and Cosine transforms efficiently using QHT, expanding the toolkit for real-valued quantum algorithms.
Serial Number Recovery: A proof-of-concept algorithm using continuous-time quantum walks to extract serial numbers, validating the practicality of the scheme.

4. Results

Gate Complexity: The proposed QHT algorithm achieves a gate complexity of $2 \log^2 N + O(\log N)$ , compared to $2.5 \log^2 N + O(\log N)$ for prior recursive methods and $2.5 \log^2 N + O(\log N)$ for methods relying on QFT subroutines.
Verification Correctness: The new verification algorithm (Algorithm 2) is proven to accept genuine banknotes with probability 1 and reject counterfeit states (specifically those with flipped serial numbers) with high probability, provided the group action supports efficient twists.
Security Implications: The use of real amplitudes opens new theoretical avenues for proving security (specifically regarding the "quantum lightning" property) that were inaccessible with complex amplitudes.

5. Significance

Theoretical Advancement: This work is the first to successfully integrate the Quantum Hartley Transform into a significant cryptographic construction (quantum money). It challenges the dominance of the Fourier transform in quantum money schemes and suggests that real-valued quantum states may offer distinct theoretical benefits.
Practical Efficiency: By reducing the gate complexity of the Hartley transform, the paper makes real-valued quantum algorithms more feasible for near-term quantum hardware, which often struggles with complex phase rotations.
Cryptographic Robustness: The introduction of "twists" to resolve verification failures provides a new tool for designing quantum money schemes based on group actions, potentially leading to more robust protocols that are less susceptible to specific algebraic attacks.
Broader Impact: The techniques developed for Sine and Cosine transforms via QHT could be applied to other areas of quantum signal processing and machine learning where real-valued transforms are preferred.

In summary, the paper successfully bridges the gap between real-valued quantum transforms and public-key quantum money, offering a more efficient algorithmic foundation and a novel verification mechanism that leverages the unique properties of real amplitudes.