Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2511.02527

Photonic implementation of quantum hidden subgroup database compression

Qianyi Wang, Feiyang Liu, Teng Hu, Kwok Ho Wan, Jie Xie, M. S. Kim, Huangqiuchen Wang, Lijian Zhang, Oscar Dahlsten

quant-phSubmitted Nov 4, 2025• Announced Nov 5, 2025• 0 citations
arXivHTMLPDF

Abstract

We experimentally demonstrate quantum data compression exploiting hidden subgroup symmetries using a photonic quantum processor. Classical databases containing generalized periodicities-symmetries that are in the worst cases inefficient for known classical algorithms to be detect-can efficiently compressed by quantum hidden subgroup algorithms. We implement a variational quantum autoencoder that autonomously learns both the symmetry type (e.g., $\mathbb{Z}_2 \times \mathbb{Z}_2$ vs. $\mathbb{Z}_4$) and the generalized period from structured data. The system uses single photons encoded in path, polarization, and time-bin degrees of freedom, with electronically controlled waveplates enabling tunable quantum gates. Training via gradient descent successfully identifies the hidden symmetry structure, achieving compression by eliminating redundant database entries. We demonstrate two circuit ansatzes: a parametrized generalized Fourier transform and a less-restricted architecture for Simon's symmetry. Both converge successfully, with the cost function approaching zero as training proceeds. These results provide experimental proof-of-principle that photonic quantum computers can compress classical databases by learning symmetries inaccessible to known efficient classical methods, opening pathways for quantum-enhanced information processing.

Related papers

Information compression via hidden subgroup quantum autoencoders

Feiyang Liu, Kaiming Bian, Fei Meng +2 more

We design a quantum method for classical information compression that exploits the hidden subgroup quantum algorithm. We consider sequence data in a database with a priori unknown symmetries of the hidden subgroup type. We prove that data with a given group structure can be compressed with the same query complexity as the hidden subgroup problem, which is exponentially faster than the best-known classical algorithms. We moreover design a quantum algorithm that variationally finds the group structure and uses it to compress the data. There is an encoder and a decoder, along the paradigm of quantum autoencoders. After the training, the encoder outputs a compressed data string and a description of the hidden subgroup symmetry, from which the input data can be recovered by the decoder. In illustrative examples, our algorithm outperforms the classical autoencoder on the mean squared value of test data. This classical-quantum separation in information compression capability has thermodynamical significance: the free energy assigned by a quantum agent to a system can be much higher than that of a classical agent. Taken together, our results show that a possible application of quantum computers is to efficiently compress certain types of data that cannot be efficiently compressed by current methods using classical computers.

arXiv:2306.08047•npj Quantum Information•Aug 8, 2024•4 citations

Quantum Algorithms for Some Hidden Shift Problems

Wim van Dam, Sean Hallgren, Lawrence Ip

Almost all of the most successful quantum algorithms discovered to date exploit the ability of the Fourier transform to recover subgroup structures of functions, especially periodicity. The fact that Fourier transforms can also be used to capture shift structure has received far less attention in the context of quantum computation. In this paper, we present three examples of “unknown shift” problems that can be solved efficiently on a quantum computer using the quantum Fourier transform. For one of these problems, the shifted Legendre symbol problem, we give evidence that the problem is hard to solve classically, by showing a reduction from breaking algebraically homomorphic cryptosystems. We also define the hidden coset problem, which generalizes the hidden shift problem and the hidden subgroup problem. This framework provides a unified way of viewing the ability of the Fourier transform to capture subgroup and shift structure.

SIAM Journal on Computing•Jan 1, 2006•124 citations

QUANTUM ALGORITHMS FOR SOME HIDDEN SHIFT PROBLEMS

Wim van Dam, Sean Hallgren, Lawrence Ip

Almost all of the most successful quantum algorithms discovered to date exploit the ability of the Fourier transform to recover subgroup structures of functions, especially periodicity. The fact that Fourier transforms can also be used to capture shift structure has received far less attention in the context of quantum computation. In this paper, we present three examples of “unknown shift” problems that can be solved efficiently on a quantum computer using the quantum Fourier transform. For one of these problems, the shifted Legendre symbol problem, we give evidence that the problem is hard to solve classically, by showing a reduction from breaking algebraically homomorphic cryptosystems. We also define the hidden coset problem, which generalizes the hidden shift problem and the hidden subgroup problem. This framework provides a unified way of viewing the ability of the Fourier transform to capture subgroup and shift structure.

•Nov 21, 2002•52 citations

Quantum Algorithms for some Hidden Shift Problems

Wim van Dam, Sean Hallgren, Lawrence Ip

Almost all of the most successful quantum algorithms discovered to date exploit the ability of the Fourier transform to recover subgroup structure of functions, especially periodicity. The fact that Fourier transforms can also be used to capture shift structure has received far less attention in the context of quantum computation. In this paper, we present three examples of ``unknown shift'' problems that can be solved efficiently on a quantum computer using the quantum Fourier transform. We also define the hidden coset problem, which generalizes the hidden shift problem and the hidden subgroup problem. This framework provides a unified way of viewing the ability of the Fourier transform to capture subgroup and shift structure.

arXiv:quant-ph/0211140•Nov 21, 2002•3 citations

Quantum algorithms and the fourier transform

Lawrence Ip, Umesh V. Vazirani

The search for practical problems that can be solved exponentially faster on a quantum computer is one of the primary goals in research into algorithms for quantum computers. It has long been known that such speedups are only possible for highly structured problems. We consider two problems with algebraic structure: (1) the hidden subgroup problem, where we have an unknown subgroup, a function that is constant on cosets of the subgroup, and the task is to find the unknown subgroup; (2) the hidden shift problem, where we have an unknown element of a group, a function that has been shifted by that group element, and the task is to find the unknown group element. We show that the Fourier transform is intimately connected to both these problems. This is because the Fourier transform respects group symmetries. For the hidden subgroup problem, we introduce the idea of using information theoretic techniques to design quantum algorithms. This consists of first finding an optimal set of measurements for distinguishing between different subgroups, followed by attempts to implement this set of measurements. We show that the standard algorithm for the abelian hidden subgroup problem is optimal. For the nonabelian hidden subgroup problem, the optimal measurements respect the Fourier transform in that they can be implemented by first performing a Fourier transform on each coset state, measuring the name of the irreducible representation for each state, followed by a joint measurement over the resulting lower dimensional space. This shows that the “strong standard method” cannot be used to implement the optimal set of measurements. For some instances of the hidden shift problem, we give a quantum algorithms that are exponentially faster than the best known classical algorithm. The algorithms make use of the Fourier transform in a way that may be interpreted as solving a deconvolution problem. As evidence of hardness, we give a reduction from algebraically homomorphic cryptosystems to the shifted Legendre symbol problem. This is an example of a problem which admits an exponential quantum speedup yet is not an instance of the abelian hidden subgroup problem.

•Jan 1, 2004•0 citations

A METHODOLOGY FOR ENCODER USING DATA COMPRESSION AND OBFUSCATION TECHNIQUES IN QUANTUM COMPUTING

Lokesh BS, Hariharan, Chaitanya +3 more

- Classical data are often compressed by using simple procedure which allows a string of data to take up less space during a computer’s memory. But, In Quantum Computing Data Compression is different because Quantum data are different and it's impossible to decide the frequencies of 1’s and 0’s in quantum information. The structure of the underlying autoencoder network is often chosen to represent the information on a smaller dimension, effectively compressing the input. Inspired by this concept, we introduce the model of a quantum autoencoder to perform similar tasks on quantum data. The quantum autoencoder is trained to compress a specific dataset of quantum states, where a classical compression algorithm cannot be employed. Using classical optimization algorithms, the parameters of the quantum autoencoder are trained. We show an example of an easy programmable circuit which will be trained as an efficient autoencoder with and without using dummy swap gates are implemented in IBMQ.

International Journal of Engineering Applied Sciences and Technology•Oct 1, 2021•0 citations
We experimentally demonstrate quantum data compression exploiting hidden subgroup symmetries using a photonic quantum processor. Classical databases containing generalized periodicities-symmetries that are in the worst cases inefficient for known classical algorithms to be detect-can efficiently compressed by quantum hidden subgroup algorithms. We implement a variational quantum autoencoder that autonomously learns both the symmetry type (e.g., Z2×Z2\mathbb{Z}_2 \times \mathbb{Z}_2Z2​×Z2​ vs. Z4\mathbb{Z}_4Z4​) and the generalized period from structured data. The system uses single photons encoded in path, polarization, and time-bin degrees of freedom, with electronically controlled waveplates enabling tunable quantum gates. Training via gradient descent successfully identifies the hidden symmetry structure, achieving compression by eliminating redundant database entries. We demonstrate two circuit ansatzes: a parametrized generalized Fourier transform and a less-restricted architecture for Simon's symmetry. Both converge successfully, with the cost function approaching zero as training proceeds. These results provide experimental proof-of-principle that photonic quantum computers can compress classical databases by learning symmetries inaccessible to known efficient classical methods, opening pathways for quantum-enhanced information processing.
We design a quantum method for classical information compression that exploits the hidden subgroup quantum algorithm. We consider sequence data in a database with a priori unknown symmetries of the hidden subgroup type. We prove that data with a given group structure can be compressed with the same query complexity as the hidden subgroup problem, which is exponentially faster than the best-known classical algorithms. We moreover design a quantum algorithm that variationally finds the group structure and uses it to compress the data. There is an encoder and a decoder, along the paradigm of quantum autoencoders. After the training, the encoder outputs a compressed data string and a description of the hidden subgroup symmetry, from which the input data can be recovered by the decoder. In illustrative examples, our algorithm outperforms the classical autoencoder on the mean squared value of test data. This classical-quantum separation in information compression capability has thermodynamical significance: the free energy assigned by a quantum agent to a system can be much higher than that of a classical agent. Taken together, our results show that a possible application of quantum computers is to efficiently compress certain types of data that cannot be efficiently compressed by current methods using classical computers.
Almost all of the most successful quantum algorithms discovered to date exploit the ability of the Fourier transform to recover subgroup structures of functions, especially periodicity. The fact that Fourier transforms can also be used to capture shift structure has received far less attention in the context of quantum computation. In this paper, we present three examples of “unknown shift” problems that can be solved efficiently on a quantum computer using the quantum Fourier transform. For one of these problems, the shifted Legendre symbol problem, we give evidence that the problem is hard to solve classically, by showing a reduction from breaking algebraically homomorphic cryptosystems. We also define the hidden coset problem, which generalizes the hidden shift problem and the hidden subgroup problem. This framework provides a unified way of viewing the ability of the Fourier transform to capture subgroup and shift structure.
Almost all of the most successful quantum algorithms discovered to date exploit the ability of the Fourier transform to recover subgroup structures of functions, especially periodicity. The fact that Fourier transforms can also be used to capture shift structure has received far less attention in the context of quantum computation. In this paper, we present three examples of “unknown shift” problems that can be solved efficiently on a quantum computer using the quantum Fourier transform. For one of these problems, the shifted Legendre symbol problem, we give evidence that the problem is hard to solve classically, by showing a reduction from breaking algebraically homomorphic cryptosystems. We also define the hidden coset problem, which generalizes the hidden shift problem and the hidden subgroup problem. This framework provides a unified way of viewing the ability of the Fourier transform to capture subgroup and shift structure.
Almost all of the most successful quantum algorithms discovered to date exploit the ability of the Fourier transform to recover subgroup structure of functions, especially periodicity. The fact that Fourier transforms can also be used to capture shift structure has received far less attention in the context of quantum computation. In this paper, we present three examples of ``unknown shift'' problems that can be solved efficiently on a quantum computer using the quantum Fourier transform. We also define the hidden coset problem, which generalizes the hidden shift problem and the hidden subgroup problem. This framework provides a unified way of viewing the ability of the Fourier transform to capture subgroup and shift structure.
The search for practical problems that can be solved exponentially faster on a quantum computer is one of the primary goals in research into algorithms for quantum computers. It has long been known that such speedups are only possible for highly structured problems. We consider two problems with algebraic structure: (1) the hidden subgroup problem, where we have an unknown subgroup, a function that is constant on cosets of the subgroup, and the task is to find the unknown subgroup; (2) the hidden shift problem, where we have an unknown element of a group, a function that has been shifted by that group element, and the task is to find the unknown group element. We show that the Fourier transform is intimately connected to both these problems. This is because the Fourier transform respects group symmetries. For the hidden subgroup problem, we introduce the idea of using information theoretic techniques to design quantum algorithms. This consists of first finding an optimal set of measurements for distinguishing between different subgroups, followed by attempts to implement this set of measurements. We show that the standard algorithm for the abelian hidden subgroup problem is optimal. For the nonabelian hidden subgroup problem, the optimal measurements respect the Fourier transform in that they can be implemented by first performing a Fourier transform on each coset state, measuring the name of the irreducible representation for each state, followed by a joint measurement over the resulting lower dimensional space. This shows that the “strong standard method” cannot be used to implement the optimal set of measurements. For some instances of the hidden shift problem, we give a quantum algorithms that are exponentially faster than the best known classical algorithm. The algorithms make use of the Fourier transform in a way that may be interpreted as solving a deconvolution problem. As evidence of hardness, we give a reduction from algebraically homomorphic cryptosystems to the shifted Legendre symbol problem. This is an example of a problem which admits an exponential quantum speedup yet is not an instance of the abelian hidden subgroup problem.
- Classical data are often compressed by using simple procedure which allows a string of data to take up less space during a computer’s memory. But, In Quantum Computing Data Compression is different because Quantum data are different and it's impossible to decide the frequencies of 1’s and 0’s in quantum information. The structure of the underlying autoencoder network is often chosen to represent the information on a smaller dimension, effectively compressing the input. Inspired by this concept, we introduce the model of a quantum autoencoder to perform similar tasks on quantum data. The quantum autoencoder is trained to compress a specific dataset of quantum states, where a classical compression algorithm cannot be employed. Using classical optimization algorithms, the parameters of the quantum autoencoder are trained. We show an example of an easy programmable circuit which will be trained as an efficient autoencoder with and without using dummy swap gates are implemented in IBMQ.